OpenRaiser/Intern-Atlas huggingface dataset:
$M$-QAM Precoder Design for MIMO Directional Modulation Transceivers
Venue: arXiv cs.IT 2018
Year: 2018

Spectrally efficient multi-antenna wireless communication systems are a key challenge as service demands continue to increase. At the same time, powering up radio access networks is facing environmental and regulation limitations. In order to achieve more power efficiency, we design a directional modulation precoder by considering an $M$-QAM constellation, particularly with $M=4,8,16,32$. First, extended detection regions are defined for desired constellations using analytical geometry. Then, constellation points are placed in the optimal positions of these regions while the minimum Euclidean distance to adjacent constellation points and detection region boundaries is kept as in the conventional $M$-QAM modulation. For further power efficiency and symbol error rate similar to that of fixed design in high SNR, relaxed detection regions are modeled for inner points of $M=16,32$ constellations. The modeled extended and relaxed detection regions as well as the modulation characteristics are utilized to formulate symbol-level precoder design problems for directional modulation to minimize the transmission power while preserving the minimum required SNR at the destination. In addition, the extended and relaxed detection regions are used for precoder design to minimize the output of each power amplifier. We transform the design problems into convex ones and devise an interior point path-following iterative algorithm to solve the mentioned problems and provide details on finding the initial values of the parameters and the starting point. Results show that compared to the benchmark schemes, the proposed method performs better in terms of power and peak power reduction as well as symbol error rate reduction for a wide range of SNRs.
Continuous-Time Visual-Inertial Odometry for Event Cameras
Venue: arXiv cs.RO 2018
Year: 2018

Event cameras are bio-inspired vision sensors that output pixel-level brightness changes instead of standard intensity frames. They offer significant advantages over standard cameras, namely a very high dynamic range, no motion blur, and a latency in the order of microseconds. However, due to the fundamentally different structure of the sensor's output, new algorithms that exploit the high temporal resolution and the asynchronous nature of the sensor are required. Recent work has shown that a continuous-time representation of the event camera pose can deal with the high temporal resolution and asynchronous nature of this sensor in a principled way. In this paper, we leverage such a continuous-time representation to perform visual-inertial odometry with an event camera. This representation allows direct integration of the asynchronous events with micro-second accuracy and the inertial measurements at high frequency. The event camera trajectory is approximated by a smooth curve in the space of rigid-body motions using cubic splines. This formulation significantly reduces the number of variables in trajectory estimation problems. We evaluate our method on real data from several scenes and compare the results against ground truth from a motion-capture system. We show that our method provides improved accuracy over the result of a state-of-the-art visual odometry method for event cameras. We also show that both the map orientation and scale can be recovered accurately by fusing events and inertial data. To the best of our knowledge, this is the first work on visual-inertial fusion with event cameras using a continuous-time framework.
Analyzing and Exploiting NARX Recurrent Neural Networks for Long-Term Dependencies
Venue: arXiv cs.NE 2018
Year: 2018

Recurrent neural networks (RNNs) have achieved state-of-the-art performance on many diverse tasks, from machine translation to surgical activity recognition, yet training RNNs to capture long-term dependencies remains difficult. To date, the vast majority of successful RNN architectures alleviate this problem using nearly-additive connections between states, as introduced by long short-term memory (LSTM). We take an orthogonal approach and introduce MIST RNNs, a NARX RNN architecture that allows direct connections from the very distant past. We show that MIST RNNs 1) exhibit superior vanishing-gradient properties in comparison to LSTM and previously-proposed NARX RNNs; 2) are far more efficient than previously-proposed NARX RNN architectures, requiring even fewer computations than LSTM; and 3) improve performance substantially over LSTM and Clockwork RNNs on tasks requiring very long-term dependencies.
Global Optimality in Low-rank Matrix Optimization
Venue: arXiv cs.IT 2018
Year: 2018

This paper considers the minimization of a general objective function $f(X)$ over the set of rectangular $n\times m$ matrices that have rank at most $r$. To reduce the computational burden, we factorize the variable $X$ into a product of two smaller matrices and optimize over these two matrices instead of $X$. Despite the resulting nonconvexity, recent studies in matrix completion and sensing have shown that the factored problem has no spurious local minima and obeys the so-called strict saddle property (the function has a directional negative curvature at all critical points but local minima). We analyze the global geometry for a general and yet well-conditioned objective function $f(X)$ whose restricted strong convexity and restricted strong smoothness constants are comparable. In particular, we show that the reformulated objective function has no spurious local minima and obeys the strict saddle property. These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) can provably solve the factored problem with global convergence.
On the KZ Reduction
Venue: arXiv cs.IT 2018
Year: 2018

The Korkine-Zolotareff (KZ) reduction is one of the often used reduction strategies for lattice decoding. In this paper, we first investigate some important properties of KZ reduced matrices. Specifically, we present a linear upper bound on the Hermit constant which is around $\frac{7}{8}$ times of the existing sharpest linear upper bound, and an upper bound on the KZ constant which is {\em polynomially} smaller than the existing sharpest one. We also propose upper bounds on the lengths of the columns of KZ reduced matrices, and an upper bound on the orthogonality defect of KZ reduced matrices which are even {\em polynomially and exponentially} smaller than those of boosted KZ reduced matrices, respectively. Then, we derive upper bounds on the magnitudes of the entries of any solution of a shortest vector problem (SVP) when its basis matrix is LLL reduced. These upper bounds are useful for analyzing the complexity and understanding numerical stability of the basis expansion in a KZ reduction algorithm. Finally, we propose a new KZ reduction algorithm by modifying the commonly used Schnorr-Euchner search strategy for solving SVPs and the basis expansion method proposed by Zhang {\em et al.} Simulation results show that the new KZ reduction algorithm is much faster and more numerically reliable than the KZ reduction algorithm proposed by Zhang {\em et al.}, especially when the basis matrix is ill conditioned.
The Active Atlas: Combining 3D Anatomical Models with Texture Detectors
Venue: arXiv cs.CV 2018
Year: 2018

While modern imaging technologies such as fMRI have opened exciting new possibilities for studying the brain in vivo, histological sections remain the best way to study the anatomy of the brain at the level of single neurons. The histological atlas changed little since 1909 and localizing brain regions is a still a labor intensive process performed only by experienced neuro-anatomists. Existing digital atlases such as the Allen Brain atlas are limited to low resolution images which cannot identify the detailed structure of the neurons. We have developed a digital atlas methodology that combines information about the 3D organization of the brain and the detailed texture of neurons in different structures. Using the methodology we developed an atlas for the mouse brainstem and mid-brain, two regions for which there are currently no good atlases. Our atlas is "active" in that it can be used to automatically align a histological stack to the atlas, thus reducing the work of the neuroanatomist.
Model-Independent Online Learning for Influence Maximization
Venue: arXiv cs.LG 2018
Year: 2018

We consider influence maximization (IM) in social networks, which is the problem of maximizing the number of users that become aware of a product by selecting a set of "seed" users to expose the product to. While prior work assumes a known model of information diffusion, we propose a novel parametrization that not only makes our framework agnostic to the underlying diffusion model, but also statistically efficient to learn from data. We give a corresponding monotone, submodular surrogate function, and show that it is a good approximation to the original IM objective. We also consider the case of a new marketer looking to exploit an existing social network, while simultaneously learning the factors governing information propagation. For this, we propose a pairwise-influence semi-bandit feedback model and develop a LinUCB-based bandit algorithm. Our model-independent analysis shows that our regret bound has a better (as compared to previous work) dependence on the size of the network. Experimental evaluation suggests that our framework is robust to the underlying diffusion model and can efficiently learn a near-optimal solution.
Exact algorithms for the order picking problem
Venue: arXiv cs.DS 2018
Year: 2018

Order picking is the problem of collecting a set of products in a warehouse in a minimum amount of time. It is currently a major bottleneck in supply-chain because of its cost in time and labor force. This article presents two exact and effective algorithms for this problem. Firstly, a sparse formulation in mixed-integer programming is strengthened by preprocessing and valid inequalities. Secondly, a dynamic programming approach generalizing known algorithms for two or three cross-aisles is proposed and evaluated experimentally. Performances of these algorithms are reported and compared with the Traveling Salesman Problem (TSP) solver Concorde.
Toward Controlled Generation of Text
Venue: arXiv cs.LG 2018
Year: 2018

Generic generation and manipulation of text is challenging and has limited success compared to recent deep generative modeling in visual domain. This paper aims at generating plausible natural language sentences, whose attributes are dynamically controlled by learning disentangled latent representations with designated semantics. We propose a new neural generative model which combines variational auto-encoders and holistic attribute discriminators for effective imposition of semantic structures. With differentiable approximation to discrete text samples, explicit constraints on independent attribute controls, and efficient collaborative learning of generator and discriminators, our model learns highly interpretable representations from even only word annotations, and produces realistic sentences with desired attributes. Quantitative evaluation validates the accuracy of sentence and attribute generation.
End-to-End Task-Completion Neural Dialogue Systems
Venue: arXiv cs.CL 2018
Year: 2018

One of the major drawbacks of modularized task-completion dialogue systems is that each module is trained individually, which presents several challenges. For example, downstream modules are affected by earlier modules, and the performance of the entire system is not robust to the accumulated errors. This paper presents a novel end-to-end learning framework for task-completion dialogue systems to tackle such issues. Our neural dialogue system can directly interact with a structured database to assist users in accessing information and accomplishing certain tasks. The reinforcement learning based dialogue manager offers robust capabilities to handle noises caused by other components of the dialogue system. Our experiments in a movie-ticket booking domain show that our end-to-end system not only outperforms modularized dialogue system baselines for both objective and subjective evaluation, but also is robust to noises as demonstrated by several systematic experiments with different error granularity and rates specific to the language understanding module.
Give Me Some Slack: Efficient Network Measurements
Venue: arXiv cs.DS 2018
Year: 2018

Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing \emph{slack} in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between $W$ and $W(1+τ)$ where $τ$ is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as MAX and GENERAL-SUM that require $Ω(W)$ bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as BASIC-SUMMING and COUNT-DISTINCT, the slack model enables a further asymptotic improvement.
Denoising Adversarial Autoencoders
Venue: arXiv cs.CV 2018
Year: 2018

Unsupervised learning is of growing interest because it unlocks the potential held in vast amounts of unlabelled data to learn useful representations for inference. Autoencoders, a form of generative model, may be trained by learning to reconstruct unlabelled input data from a latent representation space. More robust representations may be produced by an autoencoder if it learns to recover clean input samples from corrupted ones. Representations may be further improved by introducing regularisation during training to shape the distribution of the encoded data in latent space. We suggest denoising adversarial autoencoders, which combine denoising and regularisation, shaping the distribution of latent space using adversarial training. We introduce a novel analysis that shows how denoising may be incorporated into the training and sampling of adversarial autoencoders. Experiments are performed to assess the contributions that denoising makes to the learning of representations for classification and sample synthesis. Our results suggest that autoencoders trained using a denoising criterion achieve higher classification performance, and can synthesise samples that are more consistent with the input data than those trained without a corruption process.
On the MISO Channel with Feedback: Can Infinitely Massive Antennas Achieve Infinite Capacity?
Venue: arXiv cs.IT 2018
Year: 2018

We consider communication over a multiple-input single-output (MISO) block fading channel in the presence of an independent noiseless feedback link. We assume that the transmitter and receiver have no prior knowledge of the channel state realizations, but the transmitter and receiver can acquire the channel state information (CSIT/CSIR) via downlink training and feedback. For this channel, we show that increasing the number of transmit antennas to infinity will not achieve an infinite capacity, for a finite channel coherence length and a finite input constraint on the second or fourth moment. This insight follows from our new capacity bounds that hold for any linear and nonlinear coding strategies, and any channel training schemes. In addition to the channel capacity bounds, we also provide a characterization on the beamforming gain that is also known as array gain or power gain, at the regime with a large number of antennas.
First and Second Order Asymptotics in Covert Communication
Venue: arXiv cs.IT 2018
Year: 2018

We study the first- and second-order asymptotics of covert communication over binary-input DMC for three different covertness metrics and under maximum probability of error constraint. When covertness is measured in terms of the relative entropy between the channel output distributions induced with and without communication, we characterize the exact first- and second-order asymptotics of the number of bits that can be reliably transmitted with a maximum probability of error less than $ε$ and a relative entropy less than $δ$. When covertness is measured in terms of the variational distance between the channel output distributions or in terms of the probability of missed detection for fixed probability of false alarm, we establish the exact first-order asymptotics and bound the second-order asymptotics. PPM achieves the optimal first-order asymptotics for all three metrics, as well as the optimal second-order asymptotics for relative entropy. The main conceptual contribution of this paper is to clarify how the choice of a covertness metric impacts the information-theoretic limits of covert communications. The main technical contribution underlying our results is a detailed expurgation argument to show the existence of a code satisfying the reliability and covertness criteria.
Doing Things Twice (Or Differently): Strategies to Identify Studies for Targeted Validation
Venue: arXiv cs.CY 2018
Year: 2018

The "reproducibility crisis" has been a highly visible source of scientific controversy and dispute. Here, I propose and review several avenues for identifying and prioritizing research studies for the purpose of targeted validation. Of the various proposals discussed, I identify scientific data science as being a strategy that merits greater attention among those interested in reproducibility. I argue that the tremendous potential of scientific data science for uncovering high-value research studies is a significant and rarely discussed benefit of the transition to a fully open-access publishing model.
Graph sketching-based Space-efficient Data Clustering
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we address the problem of recovering arbitrary-shaped data clusters from datasets while facing \emph{high space constraints}, as this is for instance the case in many real-world applications when analysis algorithms are directly deployed on resources-limited mobile devices collecting the data. We present DBMSTClu a new space-efficient density-based \emph{non-parametric} method working on a Minimum Spanning Tree (MST) recovered from a limited number of linear measurements i.e. a \emph{sketched} version of the dissimilarity graph $\mathcal{G}$ between the $N$ objects to cluster. Unlike $k$-means, $k$-medians or $k$-medoids algorithms, it does not fail at distinguishing clusters with particular forms thanks to the property of the MST for expressing the underlying structure of a graph. No input parameter is needed contrarily to DBSCAN or the Spectral Clustering method. An approximate MST is retrieved by following the dynamic \emph{semi-streaming} model in handling the dissimilarity graph $\mathcal{G}$ as a stream of edge weight updates which is sketched in one pass over the data into a compact structure requiring $O(N \operatorname{polylog}(N))$ space, far better than the theoretical memory cost $O(N^2)$ of $\mathcal{G}$. The recovered approximate MST $\mathcal{T}$ as input, DBMSTClu then successfully detects the right number of nonconvex clusters by performing relevant cuts on $\mathcal{T}$ in a time linear in $N$. We provide theoretical guarantees on the quality of the clustering partition and also demonstrate its advantage over the existing state-of-the-art on several datasets.
Towards Generalization and Simplicity in Continuous Control
Venue: arXiv cs.LG 2018
Year: 2018

This work shows that policies with simple linear and RBF parameterizations can be trained to solve a variety of continuous control tasks, including the OpenAI gym benchmarks. The performance of these trained policies are competitive with state of the art results, obtained with more elaborate parameterizations such as fully connected neural networks. Furthermore, existing training and testing scenarios are shown to be very limited and prone to over-fitting, thus giving rise to only trajectory-centric policies. Training with a diverse initial state distribution is shown to produce more global policies with better generalization. This allows for interactive control scenarios where the system recovers from large on-line perturbations; as shown in the supplementary video.
Subsumption Algorithms for Three-Valued Geometric Resolution
Venue: arXiv cs.LO 2018
Year: 2018

In our implementation of geometric resolution, the most costly operation is subsumption testing (or matching): One has to decide for a three-valued, geometric formula, if this formula is false in a given interpretation. The formula contains only atoms with variables, equality, and existential quantifiers. The interpretation contains only atoms with constants. Because the atoms have no term structure, matching for geometric resolution is hard. We translate the matching problem into a generalized constraint satisfaction problem, and discuss several approaches for solving it efficiently, one direct algorithm and two translations to propositional SAT. After that, we study filtering techniques based on local consistency checking. Such filtering techniques can a priori refute a large percentage of generalized constraint satisfaction problems. Finally, we adapt the matching algorithms in such a way that they find solutions that use a minimal subset of the interpretation. The adaptation can be combined with every matching algorithm. The techniques presented in this paper may have applications in constraint solving independent of geometric resolution.
A Normalization Model for Analyzing Multi-Tier Millimeter Wave Cellular Networks
Venue: arXiv cs.IT 2018
Year: 2018

Based on the distinguishing features of multi-tier millimeter wave (mmWave) networks such as different transmit powers, different directivity gains from directional beamforming alignment and path loss laws for line-of-sight (LOS) and non-line-of-sight (NLOS) links, we introduce a normalization model to simplify the analysis of multi-tier mmWave cellular networks. The highlight of the model is that we convert a multi-tier mmWave cellular network into a single-tier mmWave network, where all the base stations (BSs) have the same normalized transmit power 1 and the densities of BSs scaled by LOS or NLOS scaling factors respectively follow piecewise constant function which has multiple demarcation points. On this basis, expressions for computing the coverage probability are obtained in general case with beamforming alignment errors and the special case with perfect beamforming alignment in the communication. According to corresponding numerical exploration, we conclude that the normalization model for multi-tier mmWave cellular networks fully meets requirements of network performance analysis, and it is simpler and clearer than the untransformed model. Besides, an unexpected but sensible finding is that there is an optimal beam width that maximizes coverage probability in the case with beamforming alignment errors.
Distinguishing between Communicating Transactions
Venue: arXiv cs.LO 2018
Year: 2018

Communicating transactions is a form of distributed, non-isolated transactions which provides a simple construct for building concurrent systems. In this paper we develop a logical framework to express properties of the observable behaviour of such systems. This comprises three nominal modal logics which share standard communication modalities but have distinct past and future modalities involving transactional commits. All three logics have the same distinguishing power over systems because their associated weak bisimulations coincide with contextual equivalence. Furthermore, they are equally expressive because there are semantics-preserving translations between their formulae. Using the logics we can clearly exhibit subtle example inequivalences. This work presents the first property logics for non-isolated transactions.