OpenRaiser/Intern-Atlas huggingface dataset:
Massive MIMO for Drone Communications: Case Studies and Future Directions
Venue: arXiv cs.IT 2019
Year: 2019

Unmanned aerial vehicles (UAVs), also known as drones, are proliferating. Applications, such as surveillance, disaster management, and drone racing, place high requirements on the communication with the drones in terms of throughput, reliability, and latency. The existing wireless technologies, notably Wi-Fi, that are currently used for drone connectivity are limited to short ranges and low-mobility situations. New, scalable technology is needed to meet future demands on long connectivity ranges, support for fast-moving drones, and the possibility to simultaneously communicate with entire swarms of drones. Massive multiple-input and multiple-output (MIMO), the main technology component of emerging 5G standards, has the potential to meet these requirements.
Structural Characteristics of Two-Sender Index Coding
Venue: arXiv cs.IT 2019
Year: 2019

This paper studies index coding with two senders. In this setup, source messages are distributed among the senders possibly with common messages. In addition, there are multiple receivers, with each receiver having some messages a priori, known as side-information, and requesting one unique message such that each message is requested by only one receiver. Index coding in this setup is called two-sender unicast index coding (TSUIC). The main goal is to find the shortest aggregate normalized codelength, which is expressed as the optimal broadcast rate. In this work, firstly, for a given TSUIC problem, we form three independent sub-problems each consisting of the only subset of the messages, based on whether the messages are available only in one of the senders or in both senders. Then we express the optimal broadcast rate of the TSUIC problem as a function of the optimal broadcast rates of those independent sub-problems. In this way, we discover the structural characteristics of TSUIC. For the proofs of our results, we utilize confusion graphs and coding techniques used in single-sender index coding. To adapt the confusion graph technique in TSUIC, we introduce a new graph-coloring approach that is different from the normal graph coloring, which we call two-sender graph coloring, and propose a way of grouping the vertices to analyze the number of colors used. We further determine a class of TSUIC instances where a certain type of side-information can be removed without affecting their optimal broadcast rates. Finally, we generalize the results of a class of TSUIC problems to multiple senders.
Stochastic Dependence in Wireless Channel Capacity: A Hidden Resource
Venue: arXiv cs.IT 2019
Year: 2019

This paper dedicates to exploring and exploiting the hidden resource in wireless channel. We discover that the stochastic dependence in wireless channel capacity is a hidden resource, specifically, if the wireless channel capacity bears negative dependence, the wireless channel attains a better performance with a smaller capacity. We find that the dependence in wireless channel is determined by both uncontrollable and controllable parameters in the wireless system, by inducing negative dependence through the controllable parameters, we achieve dependence control. We model the wireless channel capacity as a Markov additive process, i.e., an additive process defined on a Markov process, and we use copula to represent the dependence structure of the underlying Markov process. Based on a priori information of the temporal dependence of the uncontrollable parameters and the spatial dependence between the uncontrollable and controllable parameters, we construct a sequence of temporal copulas of the Markov process, given the initial distributions, we obtain a sequence of transition matrices of the controllable parameters satisfying the expected dependence properties of the wireless channel capacity. The goal of this paper is to show the improvement of wireless channel performance from transforming the dependence structures of the capacity.
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
Venue: arXiv cs.LG 2019
Year: 2019

Recent years have seen a flurry of activities in designing provably efficient nonconvex procedures for solving statistical estimation problems. Due to the highly nonconvex nature of the empirical loss, state-of-the-art procedures often require proper regularization (e.g. trimming, regularized cost, projection) in order to guarantee fast convergence. For vanilla procedures such as gradient descent, however, prior theory either recommends highly conservative learning rates to avoid overshooting, or completely lacks performance guarantees. This paper uncovers a striking phenomenon in nonconvex optimization: even in the absence of explicit regularization, gradient descent enforces proper regularization implicitly under various statistical models. In fact, gradient descent follows a trajectory staying within a basin that enjoys nice geometry, consisting of points incoherent with the sampling mechanism. This "implicit regularization" feature allows gradient descent to proceed in a far more aggressive fashion without overshooting, which in turn results in substantial computational savings. Focusing on three fundamental statistical estimation problems, i.e. phase retrieval, low-rank matrix completion, and blind deconvolution, we establish that gradient descent achieves near-optimal statistical and computational guarantees without explicit regularization. In particular, by marrying statistical modeling with generic optimization theory, we develop a general recipe for analyzing the trajectories of iterative algorithms via a leave-one-out perturbation argument. As a byproduct, for noisy matrix completion, we demonstrate that gradient descent achieves near-optimal error control --- measured entrywise and by the spectral norm --- which might be of independent interest.
Automatic Generation of Constrained Furniture Layouts
Venue: arXiv cs.CV 2019
Year: 2019

Efficient authoring of vast virtual environments hinges on algorithms that are able to automatically generate content while also being controllable. We propose a method to automatically generate furniture layouts for indoor environments. Our method is simple, efficient, human-interpretable and amenable to a wide variety of constraints. We model the composition of rooms into classes of objects and learn joint (co-occurrence) statistics from a database of training layouts. We generate new layouts by performing a sequence of conditional sampling steps, exploiting the statistics learned from the database. The generated layouts are specified as 3D object models, along with their positions and orientations. We show they are of equivalent perceived quality to the training layouts, and compare favorably to a state-of-the-art method. We incorporate constraints using a general mechanism -- rejection sampling -- which provides great flexibility at the cost of extra computation. We demonstrate the versatility of our method by applying a wide variety of constraints relevant to real-world applications.
Auxiliary Guided Autoregressive Variational Autoencoders
Venue: arXiv cs.CV 2019
Year: 2019

Generative modeling of high-dimensional data is a key problem in machine learning. Successful approaches include latent variable models and autoregressive models. The complementary strengths of these approaches, to model global and local image statistics respectively, suggest hybrid models that encode global image structure into latent variables while autoregressively modeling low level detail. Previous approaches to such hybrid models restrict the capacity of the autoregressive decoder to prevent degenerate models that ignore the latent variables and only rely on autoregressive modeling. Our contribution is a training procedure relying on an auxiliary loss function that controls which information is captured by the latent variables and what is left to the autoregressive decoder. Our approach can leverage arbitrarily powerful autoregressive decoders, achieves state-of-the art quantitative performance among models with latent variables, and generates qualitatively convincing samples.
Unsupervised Learning for Color Constancy
Venue: arXiv cs.CV 2019
Year: 2019

Most digital camera pipelines use color constancy methods to reduce the influence of illumination and camera sensor on the colors of scene objects. The highest accuracy of color correction is obtained with learning-based color constancy methods, but they require a significant amount of calibrated training images with known ground-truth illumination. Such calibration is time consuming, preferably done for each sensor individually, and therefore a major bottleneck in acquiring high color constancy accuracy. Statistics-based methods do not require calibrated training images, but they are less accurate. In this paper an unsupervised learning-based method is proposed that learns its parameter values after approximating the unknown ground-truth illumination of the training images, thus avoiding calibration. In terms of accuracy the proposed method outperforms all statistics-based and many learning-based methods. An extension of the method is also proposed, which learns the needed parameters from non-calibrated images taken with one sensor and which can then be successfully applied to images taken with another sensor. This effectively enables inter-camera unsupervised learning for color constancy. Additionally, a new high quality color constancy benchmark dataset with 1707 calibrated images is created, used for testing, and made publicly available. The results are presented and discussed. The source code and the dataset are available at http://www.fer.unizg.hr/ipg/resources/color_constancy/.
Learning General Latent-Variable Graphical Models with Predictive Belief Propagation
Venue: arXiv cs.LG 2019
Year: 2019

Learning general latent-variable probabilistic graphical models is a key theoretical challenge in machine learning and artificial intelligence. All previous methods, including the EM algorithm and the spectral algorithms, face severe limitations that largely restrict their applicability and affect their performance. In order to overcome these limitations, in this paper we introduce a novel formulation of message-passing inference over junction trees named predictive belief propagation, and propose a new learning and inference algorithm for general latent-variable graphical models based on this formulation. Our proposed algorithm reduces the hard parameter learning problem into a sequence of supervised learning problems, and unifies the learning of different kinds of latent graphical models into a single learning framework, which is local-optima-free and statistically consistent. We then give a proof of the correctness of our algorithm and show in experiments on both synthetic and real datasets that our algorithm significantly outperforms both the EM algorithm and the spectral algorithm while also being orders of magnitude faster to compute.
MoDL: Model Based Deep Learning Architecture for Inverse Problems
Venue: arXiv cs.CV 2019
Year: 2019

We introduce a model-based image reconstruction framework with a convolution neural network (CNN) based regularization prior. The proposed formulation provides a systematic approach for deriving deep architectures for inverse problems with the arbitrary structure. Since the forward model is explicitly accounted for, a smaller network with fewer parameters is sufficient to capture the image information compared to black-box deep learning approaches, thus reducing the demand for training data and training time. Since we rely on end-to-end training, the CNN weights are customized to the forward model, thus offering improved performance over approaches that rely on pre-trained denoisers. The main difference of the framework from existing end-to-end training strategies is the sharing of the network weights across iterations and channels. Our experiments show that the decoupling of the number of iterations from the network complexity offered by this approach provides benefits including lower demand for training data, reduced risk of overfitting, and implementations with significantly reduced memory footprint. We propose to enforce data-consistency by using numerical optimization blocks such as conjugate gradients algorithm within the network; this approach offers faster convergence per iteration, compared to methods that rely on proximal gradients steps to enforce data consistency. Our experiments show that the faster convergence translates to improved performance, especially when the available GPU memory restricts the number of iterations.
Ulam Sphere Size Analysis for Permutation and Multipermutation Codes Correcting Translocation Errors
Venue: arXiv cs.IT 2019
Year: 2019

Permutation and multipermutation codes in the Ulam metric have been suggested for use in non-volatile memory storage systems such as flash memory devices. In this paper we introduce a new method to calculate permutation sphere sizes in the Ulam metric using Young Tableaux and prove the non-existence of non-trivial perfect permutation codes in the Ulam metric. We then extend the study to multipermutations, providing tight upper and lower bounds on multipermutation Ulam sphere sizes and resulting upper and lower bounds on the maximal size of multipermutation codes in the Ulam metric.
A Novel Document Generation Process for Topic Detection based on Hierarchical Latent Tree Models
Venue: arXiv cs.CL 2019
Year: 2019

We propose a novel document generation process based on hierarchical latent tree models (HLTMs) learned from data. An HLTM has a layer of observed word variables at the bottom and multiple layers of latent variables on top. For each document, we first sample values for the latent variables layer by layer via logic sampling, then draw relative frequencies for the words conditioned on the values of the latent variables, and finally generate words for the document using the relative word frequencies. The motivation for the work is to take word counts into consideration with HLTMs. In comparison with LDA-based hierarchical document generation processes, the new process achieves drastically better model fit with much fewer parameters. It also yields more meaningful topics and topic hierarchies. It is the new state-of-the-art for the hierarchical topic detection.
Block-Krylov techniques in the context of sparse-FGLM algorithms
Venue: arXiv cs.SC 2019
Year: 2019

Consider a zero-dimensional ideal $I$ in $\mathbb{K}[X_1,\dots,X_n]$. Inspired by Faugère and Mou's Sparse FGLM algorithm, we use Krylov sequences based on multiplication matrices of $I$ in order to compute a description of its zero set by means of univariate polynomials. Steel recently showed how to use Coppersmith's block-Wiedemann algorithm in this context; he describes an algorithm that can be easily parallelized, but only computes parts of the output in this manner. Using generating series expressions going back to work of Bostan, Salvy, and Schost, we show how to compute the entire output for a small overhead, without making any assumption on the ideal $I$ other than it having dimension zero. We then propose a refinement of this idea that partially avoids the introduction of a generic linear form. We comment on experimental results obtained by an implementation based on the C++ libraries Eigen, LinBox and NTL.
An Enhanced Hybrid MobileNet
Venue: arXiv cs.CV 2019
Year: 2019

Complicated and deep neural network models can achieve high accuracy for image recognition. However, they require a huge amount of computations and model parameters, which are not suitable for mobile and embedded devices. Therefore, MobileNet was proposed, which can reduce the number of parameters and computational cost dramatically. The main idea of MobileNet is to use a depthwise separable convolution. Two hyper-parameters, a width multiplier and a resolution multiplier are used to the trade-off between the accuracy and the latency. In this paper, we propose a new architecture to improve the MobileNet. Instead of using the resolution multiplier, we use a depth multiplier and combine with either Fractional Max Pooling or the max pooling. Experimental results on CIFAR database show that the proposed architecture can reduce the amount of computational cost and increase the accuracy simultaneously.
Self-organization and the Maximum Empower Principle in the Framework of max-plus Algebra
Venue: arXiv cs.FL 2019
Year: 2019

Self-organization is a process where order of a whole system arises out of local interactions between small components of a system. Emergy, spelled with an 'm', defined as the amount of (solar) energy used to make a product or service, is becoming an important ecological indicator. The Maximum Empower Principle (MEP) was proposed as the fourth law of thermodynamics by the ecologist Odum in the 90's to explain observed self-organization of energy driven systems. But this principle suffers a lack of mathematical formulation due to an insufficiency of details about the underlying computation of empower (i.e. emergy per time). For empower computation in steady-state an axiomatic basis has been developed recently by Le Corre and the second author of this paper. In this axiomatic basis emergy is defined as a recursive max-plus linear function. Using this axiomatic basis and a correspondance between ecological theory and dynamic systems theory, we prove the MEP. In particular, we show that the empower computation in steady-state is equivalent to a combinatorial optimization problem.
Behavior Revealed in Mobile Phone Usage Predicts Loan Repayment
Venue: arXiv cs.CY 2019
Year: 2019

Many households in developing countries lack formal financial histories, making it difficult for firms to extend credit, and for potential borrowers to receive it. However, many of these households have mobile phones, which generate rich data about behavior. This article shows that behavioral signatures in mobile phone data predict default, using call records matched to repayment outcomes for credit extended by a South American telecom. On a sample of individuals with (thin) financial histories, our method actually outperforms models using credit bureau information, both within time and when tested on a different time period. But our method also attains similar performance on those without financial histories, who cannot be scored using traditional methods. Individuals in the highest quintile of risk by our measure are 2.8 times more likely to default than those in the lowest quintile. The method forms the basis for new forms of credit that reach the unbanked.
Size-Independent Sample Complexity of Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

We study the sample complexity of learning neural networks, by providing new bounds on their Rademacher complexity assuming norm constraints on the parameter matrix of each layer. Compared to previous work, these complexity bounds have improved dependence on the network depth, and under some additional assumptions, are fully independent of the network size (both depth and width). These results are derived using some novel techniques, which may be of independent interest.
A generalization of Schönemann's theorem via a graph theoretic method
Venue: arXiv cs.DM 2019
Year: 2019

Recently, Grynkiewicz et al. [{\it Israel J. Math.} {\bf 193} (2013), 359--398], using tools from additive combinatorics and group theory, proved necessary and sufficient conditions under which the linear congruence $a_1x_1+\cdots +a_kx_k\equiv b \pmod{n}$, where $a_1,\ldots,a_k,b,n$ ($n\geq 1$) are arbitrary integers, has a solution $\langle x_1,\ldots,x_k \rangle \in \Z_{n}^k$ with all $x_i$ distinct. So, it would be an interesting problem to give an explicit formula for the number of such solutions. Quite surprisingly, this problem was first considered, in a special case, by Schönemann almost two centuries ago(!) but his result seems to have been forgotten. Schönemann [{\it J. Reine Angew. Math.} {\bf 1839} (1839), 231--243] proved an explicit formula for the number of such solutions when $b=0$, $n=p$ a prime, and $\sum_{i=1}^k a_i \equiv 0 \pmod{p}$ but $\sum_{i \in I} a_i \not\equiv 0 \pmod{p}$ for all $\emptyset \not= I\varsubsetneq \lbrace 1, \ldots, k\rbrace$. In this paper, we generalize Schönemann's theorem using a result on the number of solutions of linear congruences due to D. N. Lehmer and also a result on graph enumeration. This seems to be a rather uncommon method in the area; besides, our proof technique or its modifications may be useful for dealing with other cases of this problem (or even the general case) or other relevant problems.
Text Indexing and Searching in Sublinear Time
Venue: arXiv cs.DS 2019
Year: 2019

We introduce the first index that can be built in $o(n)$ time for a text of length $n$, and can also be queried in $o(q)$ time for a pattern of length $q$. On an alphabet of size $σ$, our index uses $O(n\sqrt{\log n\logσ})$ bits, is built in $O(n((\log\log n)^2+\sqrt{\logσ})/\sqrt{\log_σn})$ deterministic time, and computes the number $\mathrm{occ}$ of occurrences of the pattern in time $O(q/\log_σn+\log n)$. Each such occurrence can then be found in $O(\sqrt{\log n\logσ})$ time. By slightly increasing the space and construction time, to $O(n(\sqrt{\log n\logσ}+ \logσ\log^\varepsilon n))$ and $O(n\log^{3/2}σ/\log^{1/2-\varepsilon} n)$, respectively, for any constant $0<\varepsilon<1/2$, we can find the $\mathrm{occ}$ pattern occurrences in time $O(q/\log_σn + \sqrt{\log_σn}\log\log n + \mathrm{occ})$. We build on a novel text sampling based on difference covers, which enjoys properties that allow us efficiently computing longest common prefixes in constant time. We extend our results to the secondary memory model as well, where we give the first construction in $o(\mathit{Sort}(n))$ I/Os of a data structure with suffix array functionality; this data structure supports pattern matching queries with optimal or nearly-optimal cost.
Self-Supervised Damage-Avoiding Manipulation Strategy Optimization via Mental Simulation
Venue: arXiv cs.RO 2019
Year: 2019

Everyday robotics are challenged to deal with autonomous product handling in applications like logistics or retail, possibly causing damage on the items during manipulation. Traditionally, most approaches try to minimize physical interaction with goods. However, this paper proposes to take into account any unintended object motion and to learn damage-minimizing manipulation strategies in a self-supervised way. The presented approach consists of a simulation-based planning method for an optimal manipulation sequence with respect to possible damage. The planned manipulation sequences are generalized to new, unseen scenes in the same application scenario using machine learning. This learned manipulation strategy is continuously refined in a self-supervised, simulation-in-the-loop optimization cycle during load-free times of the system, commonly known as mental simulation. In parallel, the generated manipulation strategies can be deployed in near-real time in an anytime fashion. The approach is validated on an industrial container-unloading scenario and on a retail shelf-replenishment scenario.