OpenRaiser/Intern-Atlas huggingface dataset:
Attention and Anticipation in Fast Visual-Inertial Navigation
Venue: arXiv cs.RO 2018
Year: 2018

We study a Visual-Inertial Navigation (VIN) problem in which a robot needs to estimate its state using an on-board camera and an inertial sensor, without any prior knowledge of the external environment. We consider the case in which the robot can allocate limited resources to VIN, due to tight computational constraints. Therefore, we answer the following question: under limited resources, what are the most relevant visual cues to maximize the performance of visual-inertial navigation? Our approach has four key ingredients. First, it is task-driven, in that the selection of the visual cues is guided by a metric quantifying the VIN performance. Second, it exploits the notion of anticipation, since it uses a simplified model for forward-simulation of robot dynamics, predicting the utility of a set of visual cues over a future time horizon. Third, it is efficient and easy to implement, since it leads to a greedy algorithm for the selection of the most relevant visual cues. Fourth, it provides formal performance guarantees: we leverage submodularity to prove that the greedy selection cannot be far from the optimal (combinatorial) selection. Simulations and real experiments on agile drones show that our approach ensures state-of-the-art VIN performance while maintaining a lean processing time. In the easy scenarios, our approach outperforms appearance-based feature selection in terms of localization errors. In the most challenging scenarios, it enables accurate visual-inertial navigation while appearance-based feature selection fails to track robot's motion during aggressive maneuvers.
Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovasz Local Lemma
Venue: arXiv cs.DS 2018
Year: 2018

Many randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low (almost-) independence. A series of papers, beginning with Luby (1993) and continuing with Berger & Rompel (1991) and Chari et al. (2000), showed that these techniques can be combined to give deterministic parallel algorithms for combinatorial optimization problems involving sums of $w$-juntas. We improve these algorithms through derandomized variable partitioning and a new code construction for fooling Fourier characters over $GF(2)$. This reduces the processor complexity to essentially independent of $w$ while the running time is reduced from exponential in $w$ to linear in $w$. As a key subroutine, we give a new algorithm to generate a probability space which can fool a given set of neighborhoods. Schulman (1992) gave an NC algorithm to do so for neighborhoods of size $w \leq O(\log n)$. Our new algorithm is NC1, with essentially optimal time and processor complexity, when $w = O(\log n)$; it remains NC up to $w = \text{polylog}(n)$. This answers an open problem of Schulman. One major application of these algorithms is an NC algorithm for the Lovász Local Lemma. Previous NC algorithms, including the seminal algorithm of Moser & Tardos (2010) and the work of Chandrasekaran et. al (2013), required that (essentially) the bad-events could span only $O(\log n)$ variables; we relax this to $\text{polylog}(n)$ variables. We use this for an $\text{NC}^2$ algorithm for defective vertex coloring, which works for arbitrary degree graphs.
Image Based Camera Localization: an Overview
Venue: arXiv cs.CV 2018
Year: 2018

Recently, virtual reality, augmented reality, robotics, autonomous driving et al attract much attention of both academic and industrial community, in which image based camera localization is a key task. However, there has not been a complete review on image-based camera localization. It is urgent to map this topic to help people enter the field quickly. In this paper, an overview of image based camera localization is presented. A new and complete kind of classifications for image based camera localization is provided and the related techniques are introduced. Trends for the future development are also discussed. It will be useful to not only researchers but also engineers and other people interested.
Improved bounds for sparse recovery from subsampled random convolutions
Venue: arXiv cs.IT 2018
Year: 2018

We study the recovery of sparse vectors from subsampled random convolutions via $\ell_1$-minimization. We consider the setup in which both the subsampling locations as well as the generating vector are chosen at random. For a subgaussian generator with independent entries, we improve previously known estimates: if the sparsity $s$ is small enough, i.e., $s \lesssim \sqrt{n/\log(n)}$, we show that $m \gtrsim s \log(en/s)$ measurements are sufficient to recover $s$-sparse vectors in dimension $n$ with high probability, matching the well-known condition for recovery from standard Gaussian measurements. If $s$ is larger, then essentially $m \geq s \log^2(s) \log(\log(s)) \log(n)$ measurements are sufficient, again improving over previous estimates. Our results are shown via the so-called robust null space property which is weaker than the standard restricted isometry property. Our method of proof involves a novel combination of small ball estimates with chaining techniques {which should be of independent interest.
Payload-Size and Deadline-Aware Scheduling for Time-critical Cyber Physical Systems
Venue: arXiv cs.NI 2018
Year: 2018

Compared to former mobile networks, Long Term Evolution (LTE) offers higher transfer speeds, significantly lower latencies and a widespread availability, qualifying LTE for a wide range of different applications and services in the field of conventional Human-to-Human (H2H) as well as fast growing Vehicle-To-X (V2X) and Cyber Physical Systems (CPS) communications. As a result, a steady growth of mobile data traffic, which is reflected in an increased interaction between different traffic classes, can be observed. In order to ensure timely transmissions of time-critical data in the future, we propose the novel Payload-Size and Deadline-Aware (PayDA) scheduling approach and compare its performance regarding the compliance for deadlines with those of other common packet scheduling mechanisms. The performance analysis is done with the complex and open-source LTE simulation environment LTE-Sim. The results show that the average latency can be reduced by the factor of 20 and the mean data rates can be enhanced by a factor of about 3.5 for a high miscellaneous data traffic. In the case of a heavy homogeneous and time-critical data traffic the mean Deadline-Miss-Ratio (DMR) can be decreased by about 35%.
Approximate Partial Order Reduction
Venue: arXiv cs.LO 2018
Year: 2018

We present a new partial order reduction method for reachability analysis of nondeterministic labeled transition systems over metric spaces. Nondeterminism arises from both the choice of the initial state and the choice of actions, and the number of executions to be explored grows exponentially with their length. We introduce a notion of $\varepsilon$-independence relation over actions that relate approximately commutative actions; $\varepsilon$-equivalent action sequences are obtained by swapping $\varepsilon$-independent consecutive action pairs. Our reachability algorithm generalizes individual executions to cover sets of executions that start from different, but $δ$-close initial states, and follow different, but $\varepsilon$-independent, action sequences. The constructed over-approximations can be made arbitrarily precise by reducing the $δ,\varepsilon$ parameters. Exploiting both the continuity of actions and their approximate independence, the algorithm can yield an exponential reduction in the number of executions explored. We illustrate this with experiments on consensus, platooning, and distributed control examples.
Performance Analysis of Multi-User Massive MIMO Downlink under Channel Non-Reciprocity and Imperfect CSI
Venue: arXiv cs.IT 2018
Year: 2018

This paper analyzes the performance of linearly precoded time division duplex based multi-user massive MIMO downlink system under joint impacts of channel non-reciprocity (NRC) and imperfect channel state information (CSI). We consider a generic and realistic NRC model that accounts for transceiver frequency-response as well as mutual coupling mismatches at both user equipment (UE) and base station (BS) sides. The analysis covers two most prominent forms of linear precoding schemes, namely, zero-forcing (ZF) and maximum-ratio transmission (MRT), and assumes that only the statistical properties of the beamformed channel are used at the UE side to decode the received signal. Under the approximation of i.i.d. Gaussian channels, closed-form analytical expressions are derived for the effective signal to interference and noise ratios (SINRs) and the corresponding capacity lower bounds. The expressions show that, in moderate to high SNR, the additional interference caused by imperfect NRC calibration can degrade the performance of both precoders significantly. Moreover, ZF is shown to be more sensitive to NRC than MRT. Numerical evaluations with practical NRC levels indicate that this performance loss in the spectral efficiency can be as high as 42% for ZF, whereas it is typically less than 13% for MRT. It is also shown that due to the NRC, the asymptotic large-antenna performance of both precoders saturate to an identical finite level. The derived analytical expressions provide useful tools and valuable technical insight, e.g., into calculating the NRC calibration requirements in BSs and UEs for any given specific performance targets in terms of effective SINR or the system capacity bound.
Optimal In-Place Suffix Sorting
Venue: arXiv cs.DS 2018
Year: 2018

The suffix array is a fundamental data structure for many applications that involve string searching and data compression. Designing time/space-efficient suffix array construction algorithms has attracted significant attention and considerable advances have been made for the past 20 years. We obtain the \emph{first} in-place suffix array construction algorithms that are optimal both in time and space for (read-only) integer alphabets. Concretely, we make the following contributions: 1. For integer alphabets, we obtain the first suffix sorting algorithm which takes linear time and uses only $O(1)$ workspace (the workspace is the total space needed beyond the input string and the output suffix array). The input string may be modified during the execution of the algorithm, but should be restored upon termination of the algorithm. 2. We strengthen the first result by providing the first in-place linear time algorithm for read-only integer alphabets with $|Σ|=O(n)$ (i.e., the input string cannot be modified). This algorithm settles the open problem posed by Franceschini and Muthukrishnan in ICALP 2007. The open problem asked to design in-place algorithms in $o(n\log n)$ time and ultimately, in $O(n)$ time for (read-only) integer alphabets with $|Σ| \leq n$. Our result is in fact slightly stronger since we allow $|Σ|=O(n)$. 3. Besides, for the read-only general alphabets (i.e., only comparisons are allowed), we present an optimal in-place $O(n\log n)$ time suffix sorting algorithm, recovering the result obtained by Franceschini and Muthukrishnan which was an open problem posed by Manzini and Ferragina in ESA 2002.
On Multihop Weibull-Fading Communications: Performance Analysis Framework and Applications
Venue: arXiv cs.IT 2018
Year: 2018

The paper presents a comprehensive closed-form performance analysis framework for multihop communications over Weibull fading channels. The analyzed scheme consists basically of multiple regenerative relays with generalized high-order quadrature amplitude modulation (M-QAM) transmissions. To take into consideration the channel fading in the mmWave range, we adopt the advocated Weibull model for its flexible ability to cover different channel conditions. The end-to-end performance is evaluated in terms of outage probability, bit error probability (BER), symbol error probability (SER), block error rate (BLER), ergodic capacity, and energy efficiency (EE). For all the metrics, we present exact closed-form expressions along with their asymptotic behavior, some in terms of generalized hypergeometric functions. Based on the obtained analytical results, we also present a practical application, we derive two BER- and EE-optimal transmit power allocation strategies, and we discuss the resulting performance gains. The exactness of our analysis is illustrated by numerical examples, and assessed via Monte-Carlo simulations for different system and channel parameters. Finally, as a secondary contribution, noting the increasing popularity of Fox's H and bivariate H functions, we provide new and generalized codes for computing these functions which are of practical utility in different contexts.
Scientific Literature Text Mining and the Case for Open Access
Venue: arXiv cs.CY 2018
Year: 2018

"Open access" has become a central theme of journal reform in academic publishing. In this article, I examine the relationship between open access publishing and an important infrastructural element of a modern research enterprise, scientific literature text mining, or the use of data analytic techniques to conduct meta-analyses and investigations into the scientific corpus. I give a brief history of the open access movement, discuss novel journalistic practices, and an overview of data-driven investigation of the scientific corpus. I argue that particularly in an era where the veracity of many research studies has been called into question, scientific literature text mining should be one of the key motivations for open access publishing, not only in the basic sciences, but in the engineering and applied sciences as well. The enormous benefits of unrestricted access to the research literature should prompt scholars from all disciplines to lend their vocal support to enabling legal, wholesale access to the scientific literature as part of a data science pipeline.
Combining Multiple Cues for Visual Madlibs Question Answering
Venue: arXiv cs.CV 2018
Year: 2018

This paper presents an approach for answering fill-in-the-blank multiple choice questions from the Visual Madlibs dataset. Instead of generic and commonly used representations trained on the ImageNet classification task, our approach employs a combination of networks trained for specialized tasks such as scene recognition, person activity classification, and attribute prediction. We also present a method for localizing phrases from candidate answers in order to provide spatial support for feature extraction. We map each of these features, together with candidate answers, to a joint embedding space through normalized canonical correlation analysis (nCCA). Finally, we solve an optimization problem to learn to combine scores from nCCA models trained on multiple cues to select the best answer. Extensive experimental results show a significant improvement over the previous state of the art and confirm that answering questions from a wide range of types benefits from examining a variety of image cues and carefully choosing the spatial support for feature extraction.
Compositional Reasoning for Shared-variable Concurrent Programs
Venue: arXiv cs.FL 2018
Year: 2018

Scalable and automatic formal verification for concurrent systems is always demanding. In this paper, we propose a verification framework to support automated compositional reasoning for concurrent programs with shared variables. Our framework models concurrent programs as succinct automata and supports the verification of multiple important properties. Safety verification and simulations of succinct automata are parallel compositional, and safety properties of succinct automata are preserved under refinements. We generate succinct automata from infinite state concurrent programs in an automated manner. Furthermore, we propose the first automated approach to checking rely-guarantee based simulations between infinite state concurrent programs. We have prototyped our algorithms and applied our tool to the verification of multiple refinements.
Sum-networks from incidence structures: construction and capacity analysis
Venue: arXiv cs.IT 2018
Year: 2018

A sum-network is an instance of a network coding problem over a directed acyclic network in which each terminal node wants to compute the sum over a finite field of the information observed at all the source nodes. Many characteristics of the well-studied multiple unicast network communication problem also hold for sum-networks due to a known reduction between instances of these two problems. In this work, we describe an algorithm to construct families of sum-network instances using incidence structures. The computation capacity of several of these sum-network families is characterized. We demonstrate that unlike the multiple unicast problem, the computation capacity of sum-networks depends on the characteristic of the finite field over which the sum is computed. This dependence is very strong; we show examples of sum-networks that have a rate-1 solution over one characteristic but a rate close to zero over a different characteristic. Additionally, a sum-network can have an arbitrary different number of computation capacities for different alphabets. This is contrast to the multiple unicast problem where it is known that the capacity is independent of the network coding alphabet.
Domain Adaptation with L2 constraints for classifying images from different endoscope systems
Venue: arXiv cs.CV 2018
Year: 2018

This paper proposes a method for domain adaptation that extends the maximum margin domain transfer (MMDT) proposed by Hoffman et al., by introducing L2 distance constraints between samples of different domains; thus, our method is denoted as MMDTL2. Motivated by the differences between the images taken by narrow band imaging (NBI) endoscopic devices, we utilize different NBI devices as different domains and estimate the transformations between samples of different domains, i.e., image samples taken by different NBI endoscope systems. We first formulate the problem in the primal form, and then derive the dual form with much lesser computational costs as compared to the naive approach. From our experimental results using NBI image datasets from two different NBI endoscopic devices, we find that MMDTL2 is better than MMDT and also support vector machines without adaptation, especially when NBI image features are high-dimensional and the per-class training samples are greater than 20.
Simple Data and Workflow Management with the signac Framework
Venue: arXiv cs.DB 2018
Year: 2018

Researchers in the field of materials science, chemistry, and computational physics are regularly posed with the challenge of managing large and heterogeneous data spaces. The amount of data increases in lockstep with computational efficiency multiplied by the amount of available computational resources, which shifts the bottleneck in the scientific process from data acquisition to data processing and analysis. We present a framework designed to aid in the integration of various specialized data formats, tools and workflows. The signac framework provides all basic components required to create a well-defined and thus collectively accessible and searchable data space, simplifying data access and modification through a homogeneous data interface that is largely agnostic to the data source, i.e., computation or experiment. The framework's data model is designed to not require absolute commitment to the presented implementation, simplifying adaption into existing data sets and workflows. This approach not only increases the efficiency with which scientific results can be produced, but also significantly lowers barriers for collaborations requiring shared data access.
Reinforcement Learning in Rich-Observation MDPs using Spectral Methods
Venue: arXiv cs.AI 2018
Year: 2018

Reinforcement learning (RL) in Markov decision processes (MDPs) with large state spaces is a challenging problem. The performance of standard RL algorithms degrades drastically with the dimensionality of state space. However, in practice, these large MDPs typically incorporate a latent or hidden low-dimensional structure. In this paper, we study the setting of rich-observation Markov decision processes (ROMDP), where there are a small number of hidden states which possess an injective mapping to the observation states. In other words, every observation state is generated through a single hidden state, and this mapping is unknown a priori. We introduce a spectral decomposition method that consistently learns this mapping, and more importantly, achieves it with low regret. The estimated mapping is integrated into an optimistic RL algorithm (UCRL), which operates on the estimated hidden space. We derive finite-time regret bounds for our algorithm with a weak dependence on the dimensionality of the observed space. In fact, our algorithm asymptotically achieves the same average regret as the oracle UCRL algorithm, which has the knowledge of the mapping from hidden to observed spaces. Thus, we derive an efficient spectral RL algorithm for ROMDPs.
Identity Matters in Deep Learning
Venue: arXiv cs.LG 2018
Year: 2018

An emerging design principle in deep learning is that each layer of a deep artificial neural network should be able to easily express the identity transformation. This idea not only motivated various normalization techniques, such as \emph{batch normalization}, but was also key to the immense success of \emph{residual networks}. In this work, we put the principle of \emph{identity parameterization} on a more solid theoretical footing alongside further empirical progress. We first give a strikingly simple proof that arbitrarily deep linear residual networks have no spurious local optima. The same result for linear feed-forward networks in their standard parameterization is substantially more delicate. Second, we show that residual networks with ReLu activations have universal finite-sample expressivity in the sense that the network can represent any function of its sample provided that the model has more parameters than the sample size. Directly inspired by our theory, we experiment with a radically simple residual architecture consisting of only residual convolutional layers and ReLu activations, but no batch normalization, dropout, or max pool. Our model improves significantly on previous all-convolutional networks on the CIFAR10, CIFAR100, and ImageNet classification benchmarks.
Convex Optimization of Distributed Cooperative Detection in Multi-Receiver Molecular Communication
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, the error performance achieved by cooperative detection among K distributed receivers in a diffusion-based molecular communication (MC) system is analyzed and optimized. In this system, the receivers first make local hard decisions on the transmitted symbol and then report these decisions to a fusion center (FC). The FC combines the local hard decisions to make a global decision using an N-out-of-K fusion rule. Two reporting scenarios, namely, perfect reporting and noisy reporting, are considered. Closed-form expressions are derived for the expected global error probability of the system for both reporting scenarios. New approximated expressions are also derived for the expected error probability. Convex constraints are then found to make the approximated expressions jointly convex with respect to the decision thresholds at the receivers and the FC. Based on such constraints, suboptimal convex optimization problems are formulated and solved to determine the optimal decision thresholds which minimize the expected error probability of the system. Numerical and simulation results reveal that the system error performance is greatly improved by combining the detection information of distributed receivers. They also reveal that the solutions to the formulated suboptimal convex optimization problems achieve near-optimal global error performance.