• ### Testing the anisotropy of the Universe with the distance duality relation(1707.00390)

Nov. 19, 2018 gr-qc
The distance duality relation (DDR) is valid in Riemannian spacetime. The astronomical data hint that the universe may have certain preferred direction. If the universe is described by anisotropic cosmological models based on Riemannian spacetime, then DDR still valid. If the anisotropy universe is described by other models which are not based on Riemannian spacetime, then DDR is violated. Thus, DDR could be used to test the validity of these anisotropic cosmological models. In this paper, we perform anisotropic DDR parametrization with the dipolar structures. The DDR is tested by comparing the luminosity distance from type-Ia supernovae (Union 2.1 and JLA compilations) and the angular diameter distance from strong gravitational lensing (SL) systems at the same redshift. It is shown that, the DDR is valid with the Union2.1 compilation, while is violated more than 1$\sigma$ confidence level with the JLA compilation. Additionally, we verify the statistical signification of our method with Monte Carlo simulations. Due to the large uncertainty of available data, no strong evidence is found to violate the DDR in the anisotropic models.
• ### Cross-scale predictive dictionaries(1511.05174)

Sept. 4, 2018 cs.CV, stat.ML
Sparse representations using data dictionaries provide an efficient model particularly for signals that do not enjoy alternate analytic sparsifying transformations. However, solving inverse problems with sparsifying dictionaries can be computationally expensive, especially when the dictionary under consideration has a large number of atoms. In this paper, we incorporate additional structure on to dictionary-based sparse representations for visual signals to enable speedups when solving sparse approximation problems. The specific structure that we endow onto sparse models is that of a multi-scale modeling where the sparse representation at each scale is constrained by the sparse representation at coarser scales. We show that this cross-scale predictive model delivers significant speedups, often in the range of 10-60$\times$, with little loss in accuracy for linear inverse problems associated with images, videos, and light fields.
• ### Randomness Extraction in AC0 and with Small Locality(1602.01530)

June 9, 2018 cs.CC
Randomness extractors, which extract high quality (almost-uniform) random bits from biased random sources, are important objects both in theory and in practice. While there have been significant progress in obtaining near optimal constructions of randomness extractors in various settings, the computational complexity of randomness extractors is still much less studied. In particular, it is not clear whether randomness extractors with good parameters can be computed in several interesting complexity classes that are much weaker than P. In this paper we study randomness extractors in the following two models of computation: (1) constant-depth circuits (AC0), and (2) the local computation model. Previous work in these models, such as [Vio05a], [GVW15] and [BG13], only achieve constructions with weak parameters. In this work we give explicit constructions of randomness extractors with much better parameters. As an application, we use our AC0 extractors to study pseudorandom generators in AC0, and show that we can construct both cryptographic pseudorandom generators (under reasonable computational assumptions) and unconditional pseudorandom generators for space bounded computation with very good parameters. Our constructions combine several previous techniques in randomness extractors, as well as introduce new techniques to reduce or preserve the complexity of extractors, which may be of independent interest. These include (1) a general way to reduce the error of strong seeded extractors while preserving the AC0 property and small locality, and (2) a seeded randomness condenser with small locality.
• ### On Improving Deep Reinforcement Learning for POMDPs(1704.07978)

May 24, 2018 cs.LG
Deep Reinforcement Learning (RL) recently emerged as one of the most competitive approaches for learning in sequential decision making problems with fully observable environments, e.g., computer Go. However, very little work has been done in deep RL to handle partially observable environments. We propose a new architecture called Action-specific Deep Recurrent Q-Network (ADRQN) to enhance learning performance in partially observable domains. Actions are encoded by a fully connected layer and coupled with a convolutional observation to form an action-observation pair. The time series of action-observation pairs are then integrated by an LSTM layer that learns latent states based on which a fully connected layer computes Q-values as in conventional Deep Q-Networks (DQNs). We demonstrate the effectiveness of our new architecture in several partially observable domains, including flickering Atari games.
• ### Exact solution of vacuum field equation in Finsler spacetime(1401.6363)

May 10, 2018 physics.gen-ph
We suggest that the vacuum field equation in Finsler spacetime is equivalent to vanishing of Ricci scalar. Schwarzschild metric can be deduced from a solution of our field equation if the spacetime preserve spherical symmetry. Supposing spacetime to preserve the symmetry of "Finslerian sphere", we find a non-Riemannian exact solution of the Finslerian vacuum field equation. The solution is similar to the Schwarzschild metric. It reduces to Schwarzschild metric while the Finslerian parameter $\epsilon$ vanishes. It is proved that the Finslerian covariant derivative of the geometrical part of the gravitational field equation is conserved. The interior solution is also given. We get solutions of geodesic equation in such a Schwarzschild-like spacetime, and show that the geodesic equation returns to the counterpart in Newton's gravity at weak field approximation. The celestial observations give constraint on the Finslerian parameter $\epsilon<10^{-4}$. And the recent Michelson-Morley experiment requires $\epsilon<10^{-16}$. The counterpart of Birkhoff's theorem exist in Finslerian vacuum. It shows that the Finslerian gravitational field with the symmetry of "Finslerian sphere" in vacuum must be static.
• ### Testing the anisotropy of the universe using the simulated gravitational wave events from advanced LIGO and Virgo(1802.00642)

May 9, 2018 gr-qc, astro-ph.CO
The detection of gravitational waves (GWs) provides a powerful tool to constrain the cosmological parameters. In this paper, we investigate the possibility of using GWs as standard sirens in testing the anisotropy of the universe. We consider the GW signals produced by the coalescence of binary black hole systems and simulate hundreds of GW events from the advanced Laser Interferometer Gravitational-Wave Observatory (LIGO) and Virgo. It is found that the anisotropy of the universe can be tightly constrained if the redshift of the GW source is precisely known. The anisotropic amplitude can be constrained with an accuracy comparable to the Union2.1 complication of type-Ia supernovae if $\gtrsim 400$ GW events are observed. As for the preferred direction, $\gtrsim 800$ GW events are needed in order to achieve the accuracy of Union2.1. With 800 GW events, the probability of pseudo anisotropic signals with an amplitude comparable to Union2.1 is negligible. These results show that GWs can provide a complementary tool to supernovae in testing the anisotropy of the universe.
• ### Finslerian Ressiner-Nordstrom spacetime(1805.03576)

May 8, 2018 math.DG, gr-qc
We have obtained Finslerian Ressiner-Nordstrom solution where it is asymptotic to a Finsler spacetime with constant flag curvature while $r\rightarrow\infty$. The covariant derivative of modified Einstein tensor in Finslerian gravitational field equation for this solution is conserved. The symmetry of the special Finslerian Ressiner-Nordstrom spacetime, namely, Finsler spacetime with constant flag curvature, has been investigated. It admits six independent Killing vectors. The Finslerian Ressiner-Nordstrom solution differs from Ressiner-Nordstrom metric only in two dimensional subspace. And our solution requires that its two dimensional subspace have constant flag curvature. We have obtained eigenfunction of Finslerian Laplace operator of "Finslerian sphere", namely, a special subspace with positive constant flag curvature. The eigenfunction is of the form $\bar{Y}_l^m=Y_l^m+\epsilon^2(C_{l+2}^m Y_{l+2}^m+C_{l-2}^m Y_{l-2}^m)$ in powers of Finslerian parameter $\epsilon$, where $C_{l+2}^m$ and $C_{l-2}^m$ are constant. However, the eigenvalue depends on both $l$ and $m$. The eigenvalues corresponded to $Y_1^0$ remain the same with Riemannian Laplace operator and the eigenvalues corresponded to $Y_1^{\pm1}$ are different. This fact just reflect the symmetry of "Finslerian sphere", which admits a rotational symmetry along $z$-axis and breaks other symmetry of Riemannian sphere. The eigenfunction of Finslerian Laplace operator implies that monopolar and dipolar terms of multipole expansion of gravitational potential are unchanged and other multipole terms are changed.
• ### On Improving Deep Reinforcement Learning for POMDPs(1804.06309)

May 8, 2018 cs.LG, stat.ML
Deep Reinforcement Learning (RL) recently emerged as one of the most competitive approaches for learning in sequential decision making problems with fully observable environments, e.g., computer Go. However, very little work has been done in deep RL to handle partially observable environments. We propose a new architecture called Action-specific Deep Recurrent Q-Network (ADRQN) to enhance learning performance in partially observable domains. Actions are encoded by a fully connected layer and coupled with a convolutional observation to form an action-observation pair. The time series of action-observation pairs are then integrated by an LSTM layer that learns latent states based on which a fully connected layer computes Q-values as in conventional Deep Q-Networks (DQNs). We demonstrate the effectiveness of our new architecture in several partially observable domains, including flickering Atari games.
• ### Perceptually Optimized Generative Adversarial Network for Single Image Dehazing(1805.01084)

May 3, 2018 cs.CV
Existing approaches towards single image dehazing including both model-based and learning-based heavily rely on the estimation of so-called transmission maps. Despite its conceptual simplicity, using transmission maps as an intermediate step often makes it more difficult to optimize the perceptual quality of reconstructed images. To overcome this weakness, we propose a direct deep learning approach toward image dehazing bypassing the step of transmission map estimation and facilitating end-to-end perceptual optimization. Our technical contributions are mainly three-fold. First, based on the analogy between dehazing and denoising, we propose to directly learn a nonlinear mapping from the space of degraded images to that of haze-free ones via recursive deep residual learning; Second, inspired by the success of generative adversarial networks (GAN), we propose to optimize the perceptual quality of dehazed images by introducing a discriminator and a loss function adaptive to hazy conditions; Third, we propose to remove notorious halo-like artifacts at large scene depth discontinuities by a novel application of guided filtering. Extensive experimental results have shown that the subjective qualities of dehazed images by the proposed perceptually optimized GAN (POGAN) are often more favorable than those by existing state-of-the-art approaches especially when hazy condition varies.
• ### Transformation Networks for Target-Oriented Sentiment Classification(1805.01086)

May 3, 2018 cs.CL
Target-oriented sentiment classification aims at classifying sentiment polarities over individual opinion targets in a sentence. RNN with attention seems a good fit for the characteristics of this task, and indeed it achieves the state-of-the-art performance. After re-examining the drawbacks of attention mechanism and the obstacles that block CNN to perform well in this classification task, we propose a new model to overcome these issues. Instead of attention, our model employs a CNN layer to extract salient features from the transformed word representations originated from a bi-directional RNN layer. Between the two layers, we propose a component to generate target-specific representations of words in the sentence, meanwhile incorporate a mechanism for preserving the original contextual information from the RNN layer. Experiments show that our model achieves a new state-of-the-art performance on a few benchmarks.
• ### Aspect Term Extraction with History Attention and Selective Transformation(1805.00760)

May 2, 2018 cs.CL
Aspect Term Extraction (ATE), a key sub-task in Aspect-Based Sentiment Analysis, aims to extract explicit aspect expressions from online user reviews. We present a new framework for tackling ATE. It can exploit two useful clues, namely opinion summary and aspect detection history. Opinion summary is distilled from the whole input sentence, conditioned on each current token for aspect prediction, and thus the tailor-made summary can help aspect prediction on this token. Another clue is the information of aspect detection history, and it is distilled from the previous aspect predictions so as to leverage the coordinate structure and tagging schema constraints to upgrade the aspect prediction. Experimental results over four benchmark datasets clearly demonstrate that our framework can outperform all state-of-the-art methods.
• ### Designing topological interface states in phononic crystals based on the full phase diagrams(1804.10754)

The topological invariants of a periodic system can be used to define the topological phase of each band and determine the existence of topological interface states within a certain bandgap. Here, we propose a scheme based on the full phase diagrams, and design the topological interface states within any specified bandgaps. As an example, here we propose a kind of one-dimensional phononic crystals. By connecting two semi-infinite structures with different topological phases, the interface states within any specific bandgap or their combinations can be achieved in a rational manner. The existence of interface states in a single bandgap, in all odd bandgaps, in all even bandgaps, or in all bandgaps, are verified in simulations and experiments. The scheme of full phase diagrams we introduce here can be extended to other kinds of periodic systems, such as photonic crystals and designer plasmonic crystals.
• ### Constructing Cartan subalgebras in classifiable stably finite C*-algebras(1802.01190)

April 25, 2018 math.OA
We construct Cartan subalgebras in all classifiable stably finite C*-algebras which are unital or stably projectionless with trivial pairing between K-theory and traces.
• ### Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors(1804.05776)

April 20, 2018 cs.DS
We study two basic problems regarding edit error, i.e. document exchange and error correcting codes for edit errors (insdel codes). For message length $n$ and edit error upper bound $k$, it is known that in both problems the optimal sketch size or the optimal number of redundant bits is $\Theta(k \log \frac{n}{k})$. However, known constructions are far from achieving these bounds. We significantly improve previous results on both problems. For document exchange, we give an efficient deterministic protocol with sketch size $O(k\log^2 \frac{n}{k})$. This significantly improves the previous best known deterministic protocol, which has sketch size $O(k^2 + k \log^2 n)$ (Belazzougui15). For binary insdel codes, we obtain the following results: 1. An explicit binary insdel code which encodes an $n$-bit message $x$ against $k$ errors with redundancy $O(k \log^2 \frac{n}{k})$. In particular this implies an explicit family of binary insdel codes that can correct $\varepsilon$ fraction of insertions and deletions with rate $1-O(\varepsilon \log^2 (\frac{1}{\varepsilon}))=1-\widetilde{O}(\varepsilon)$. 2. An explicit binary insdel code which encodes an $n$-bit message $x$ against $k$ errors with redundancy $O(k \log n)$. This is the first explicit construction of binary insdel codes that has optimal redundancy for a wide range of error parameters $k$, and this brings our understanding of binary insdel codes much closer to that of standard binary error correcting codes. In obtaining our results we introduce the notion of \emph{$\varepsilon$-self matching hash functions} and \emph{$\varepsilon$-synchronization hash functions}. We believe our techniques can have further applications in the literature.
• ### Amenability, Reiter's condition and Liouville property(1412.1517)

April 17, 2018 math.PR, math.FA, math.GR
We show that the Liouville property and Reiter's condition are equivalent for semigroupoids. This result applies to semigroups as well as semigroup actions. In the special case of measured groupoids and locally compact groupoids, our result proves Kaimanovich's conjecture of the equivalence of amenability and the Liouville property.
• ### Weighted Low-Rank Approximation of Matrices and Background Modeling(1804.06252)

April 15, 2018 math.NA, cs.NA, cs.CV, math.OC
We primarily study a special a weighted low-rank approximation of matrices and then apply it to solve the background modeling problem. We propose two algorithms for this purpose: one operates in the batch mode on the entire data and the other one operates in the batch-incremental mode on the data and naturally captures more background variations and computationally more effective. Moreover, we propose a robust technique that learns the background frame indices from the data and does not require any training frames. We demonstrate through extensive experiments that by inserting a simple weight in the Frobenius norm, it can be made robust to the outliers similar to the $\ell_1$ norm. Our methods match or outperform several state-of-the-art online and batch background modeling methods in virtually all quantitative and qualitative measures.
• ### Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More(1804.05228)

April 14, 2018 cs.CR
We present explicit constructions of non-malleable codes with respect to the following tampering classes. (i) Linear functions composed with split-state adversaries: In this model, the codeword is first tampered by a split-state adversary, and then the whole tampered codeword is further tampered by a linear function. (ii) Interleaved split-state adversary: Here the codeword is partitioned in an unknown (but fixed) way, and then tampered by a split-state adversary. (iii) Bounded communication split-state model: In this model, the split-state adversaries are allowed to participate in a communication protocol (with bounded communication budget) to tamper the codeword. Our results are the first explicit constructions of non-malleable codes in any of these tampering models. We derive all our non-malleable codes from explicit constructions of seedless non-malleable extractors. We believe that our results on seedless non-malleable extractors and the techniques developed are of independent interest. Using our techniques, we also give an improved extractor for an unknown interleaving of two independent sources.
• ### Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions(1804.04005)

April 9, 2018 math.CO, cs.CR, cs.CC
• ### Joint Demosaicing and Denoising with Perceptual Optimization on a Generative Adversarial Network(1802.04723)

Feb. 13, 2018 cs.CV
Image demosaicing - one of the most important early stages in digital camera pipelines - addressed the problem of reconstructing a full-resolution image from so-called color-filter-arrays. Despite tremendous progress made in the pase decade, a fundamental issue that remains to be addressed is how to assure the visual quality of reconstructed images especially in the presence of noise corruption. Inspired by recent advances in generative adversarial networks (GAN), we present a novel deep learning approach toward joint demosaicing and denoising (JDD) with perceptual optimization in order to ensure the visual quality of reconstructed images. The key contributions of this work include: 1) we have developed a GAN-based approach toward image demosacing in which a discriminator network with both perceptual and adversarial loss functions are used for quality assurance; 2) we propose to optimize the perceptual quality of reconstructed images by the proposed GAN in an end-to-end manner. Such end-to-end optimization of GAN is particularly effective for jointly exploiting the gain brought by each modular component (e.g., residue learning in the generative network and perceptual loss in the discriminator network). Our extensive experimental results have shown convincingly improved performance over existing state-of-the-art methods in terms of both subjective and objective quality metrics with a comparable computational cost.