OpenRaiser/Intern-Atlas huggingface dataset:
Improving compressed sensing with the diamond norm
Venue: arXiv cs.IT 2017
Year: 2017

In low-rank matrix recovery, one aims to reconstruct a low-rank matrix from a minimal number of linear measurements. Within the paradigm of compressed sensing, this is made computationally efficient by minimizing the nuclear norm as a convex surrogate for rank. In this work, we identify an improved regularizer based on the so-called diamond norm, a concept imported from quantum information theory. We show that -for a class of matrices saturating a certain norm inequality- the descent cone of the diamond norm is contained in that of the nuclear norm. This suggests superior reconstruction properties for these matrices. We explicitly characterize this set of matrices. Moreover, we demonstrate numerically that the diamond norm indeed outperforms the nuclear norm in a number of relevant applications: These include signal analysis tasks such as blind matrix deconvolution or the retrieval of certain unitary basis changes, as well as the quantum information problem of process tomography with random measurements. The diamond norm is defined for matrices that can be interpreted as order-4 tensors and it turns out that the above condition depends crucially on that tensorial structure. In this sense, this work touches on an aspect of the notoriously difficult tensor completion problem.
How does mobility affect the connectivity of interference-limited ad-hoc networks?
Venue: arXiv cs.NI 2017
Year: 2017

One limiting factor to the performance of mobile ad-hoc networks is the amount of interference that is experienced by each node. In this paper we use the Random Waypoint Mobility Model (RWPM) to represent such a network of mobile devices, and show that the connectivity of a receiver at different parts of the network domain varies significantly. This is a result of a large portion of the nodes in the RWPM being located near the centre of the domain resulting in increased levels of interference between neighbouring devices. A non-trivial trade-off therefore exists between the spatial intensity of interfering signals and non-interfering (useful) ones. Using tools from stochastic geometry, we derive closed form expressions for the spatial distribution of nodes in a rectangle and the connection probability for an interference limited network indicating the impact an inhomogeneous distribution of nodes has on a network's performance. Our novel results can be used to analyse this trade-off and optimize network performance.
(Yet) Another Theoretical Model of Thinking
Venue: arXiv cs.AI 2017
Year: 2017

This paper presents a theoretical, idealized model of the thinking process with the following characteristics: 1) the model can produce complex thought sequences and can be generalized to new inputs, 2) it can receive and maintain input information indefinitely for the generation of thoughts and later use, and 3) it supports learning while executing. The crux of the model lies within the concept of internal consistency, or the generated thoughts should always be consistent with the inputs from which they are created. Its merit, apart from the capability to generate new creative thoughts from an internal mechanism, depends on the potential to help training to generalize better. This is consequently enabled by separating input information into several parts to be handled by different processing components with a focus mechanism to fetch information for each. This modularized view with the focus binds the model with the computationally capable Turing machines. And as a final remark, this paper constructively shows that the computational complexity of the model is at least, if not surpass, that of a universal Turing machine.
Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals
Venue: arXiv cs.GT 2017
Year: 2017

We prove that the two-dimensional Schelling segregation model yields monochromatic regions of size exponential in the area of individuals' neighborhoods, provided that the tolerance parameter is a constant strictly less than 1/2 but sufficiently close to it. Our analysis makes use of a connection with the first-passage percolation model from the theory of stochastic processes.
Online Action Recognition based on Incremental Learning of Weighted Covariance Descriptors
Venue: arXiv cs.CV 2017
Year: 2017

Different from traditional action recognition based on video segments, online action recognition aims to recognize actions from unsegmented streams of data in a continuous manner. One way for online recognition is based on the evidence accumulation over time to make predictions from stream videos. This paper presents a fast yet effective method to recognize actions from stream of noisy skeleton data, and a novel weighted covariance descriptor is adopted to accumulate evidence. In particular, a fast incremental updating method for the weighted covariance descriptor is developed for accumulation of temporal information and online prediction. The weighted covariance descriptor takes the following principles into consideration: past frames have less contribution for recognition and recent and informative frames such as key frames contribute more to the recognition. The online recognition is achieved using a simple nearest neighbor search against a set of offline trained action models. Experimental results on MSC-12 Kinect Gesture dataset and our newly constructed online action recognition dataset have demonstrated the efficacy of the proposed method.
Unified Analytical Modeling of the Error Rates and the Ergodic Channel Capacity in $η$-$μ$ Generalized Fading Channels with Integer $μ$ and Maximal Ratio Combining Receiver
Venue: arXiv cs.IT 2017
Year: 2017

In this paper we introduce a novel performance analysis of the $η$-$μ$ generalized radio fading channels with integer value of the $μ$ fading parameter, i.e. with even number of multipath clusters. This fading model includes other fading models as special cases such as the Nakagami-m, the Hoyt, and the Rayleigh. We obtain novel unified and generic simple closed-form expressions for the average bit error rates and ergodic channel capacity in the additive white generalized Gaussian noise (AWGGN), which includes the additive Gaussian, the gamma, the Laplacian, and the impulsive noise as special cases. The receiver is assumed to be an L-branch maximal ratio combiner where we study the effect of having more deployed receiver antenna. Numerical evaluation as well as results from technical wireless literature validate the generality and the accuracy of the derived unified expressions under the studied test cases.
Grounding of Textual Phrases in Images by Reconstruction
Venue: arXiv cs.CV 2017
Year: 2017

Grounding (i.e. localizing) arbitrary, free-form textual phrases in visual content is a challenging problem with many applications for human-computer interaction and image-text reference resolution. Few datasets provide the ground truth spatial localization of phrases, thus it is desirable to learn from data with no or little grounding supervision. We propose a novel approach which learns grounding by reconstructing a given phrase using an attention mechanism, which can be either latent or optimized directly. During training our approach encodes the phrase using a recurrent network language model and then learns to attend to the relevant image region in order to reconstruct the input phrase. At test time, the correct attention, i.e., the grounding, is evaluated. If grounding supervision is available it can be directly applied via a loss over the attention mechanism. We demonstrate the effectiveness of our approach on the Flickr 30k Entities and ReferItGame datasets with different levels of supervision, ranging from no supervision over partial supervision to full supervision. Our supervised variant improves by a large margin over the state-of-the-art on both datasets.
Symbol Grounding Association in Multimodal Sequences with Missing Elements
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we extend a symbolic association framework for being able to handle missing elements in multimodal sequences. The general scope of the work is the symbolic associations of object-word mappings as it happens in language development in infants. In other words, two different representations of the same abstract concepts can associate in both directions. This scenario has been long interested in Artificial Intelligence, Psychology, and Neuroscience. In this work, we extend a recent approach for multimodal sequences (visual and audio) to also cope with missing elements in one or both modalities. Our method uses two parallel Long Short-Term Memories (LSTMs) with a learning rule based on EM-algorithm. It aligns both LSTM outputs via Dynamic Time Warping (DTW). We propose to include an extra step for the combination with the max operation for exploiting the common elements between both sequences. The motivation behind is that the combination acts as a condition selector for choosing the best representation from both LSTMs. We evaluated the proposed extension in the following scenarios: missing elements in one modality (visual or audio) and missing elements in both modalities (visual and sound). The performance of our extension reaches better results than the original model and similar results to individual LSTM trained in each modality.
Learning Fine-grained Features via a CNN Tree for Large-scale Classification
Venue: arXiv cs.CV 2017
Year: 2017

We propose a novel approach to enhance the discriminability of Convolutional Neural Networks (CNN). The key idea is to build a tree structure that could progressively learn fine-grained features to distinguish a subset of classes, by learning features only among these classes. Such features are expected to be more discriminative, compared to features learned for all the classes. We develop a new algorithm to effectively learn the tree structure from a large number of classes. Experiments on large-scale image classification tasks demonstrate that our method could boost the performance of a given basic CNN model. Our method is quite general, hence it can potentially be used in combination with many other deep learning models.
Depth, Highness and DNR degrees
Venue: arXiv cs.CC 2017
Year: 2017

We study Bennett deep sequences in the context of recursion theory; in particular we investigate the notions of O(1)-deepK, O(1)-deepC , order-deep K and order-deep C sequences. Our main results are that Martin-Loef random sets are not order-deepC , that every many-one degree contains a set which is not O(1)-deepC , that O(1)-deepC sets and order-deepK sets have high or DNR Turing degree and that no K-trival set is O(1)-deepK.
Modeling the Temporal Nature of Human Behavior for Demographics Prediction
Venue: arXiv cs.LG 2017
Year: 2017

Mobile phone metadata is increasingly used for humanitarian purposes in developing countries as traditional data is scarce. Basic demographic information is however often absent from mobile phone datasets, limiting the operational impact of the datasets. For these reasons, there has been a growing interest in predicting demographic information from mobile phone metadata. Previous work focused on creating increasingly advanced features to be modeled with standard machine learning algorithms. We here instead model the raw mobile phone metadata directly using deep learning, exploiting the temporal nature of the patterns in the data. From high-level assumptions we design a data representation and convolutional network architecture for modeling patterns within a week. We then examine three strategies for aggregating patterns across weeks and show that our method reaches state-of-the-art accuracy on both age and gender prediction using only the temporal modality in mobile metadata. We finally validate our method on low activity users and evaluate the modeling assumptions.
Online Sequence Training of Recurrent Neural Networks with Connectionist Temporal Classification
Venue: arXiv cs.LG 2017
Year: 2017

Connectionist temporal classification (CTC) based supervised sequence training of recurrent neural networks (RNNs) has shown great success in many machine learning areas including end-to-end speech and handwritten character recognition. For the CTC training, however, it is required to unroll (or unfold) the RNN by the length of an input sequence. This unrolling requires a lot of memory and hinders a small footprint implementation of online learning or adaptation. Furthermore, the length of training sequences is usually not uniform, which makes parallel training with multiple sequences inefficient on shared memory models such as graphics processing units (GPUs). In this work, we introduce an expectation-maximization (EM) based online CTC algorithm that enables unidirectional RNNs to learn sequences that are longer than the amount of unrolling. The RNNs can also be trained to process an infinitely long input sequence without pre-segmentation or external reset. Moreover, the proposed approach allows efficient parallel training on GPUs. For evaluation, phoneme recognition and end-to-end speech recognition examples are presented on the TIMIT and Wall Street Journal (WSJ) corpora, respectively. Our online model achieves 20.7% phoneme error rate (PER) on the very long input sequence that is generated by concatenating all 192 utterances in the TIMIT core test set. On WSJ, a network can be trained with only 64 times of unrolling while sacrificing 4.5% relative word error rate (WER).
Fine-Grain Annotation of Cricket Videos
Venue: arXiv cs.MM 2017
Year: 2017

The recognition of human activities is one of the key problems in video understanding. Action recognition is challenging even for specific categories of videos, such as sports, that contain only a small set of actions. Interestingly, sports videos are accompanied by detailed commentaries available online, which could be used to perform action annotation in a weakly-supervised setting. For the specific case of Cricket videos, we address the challenge of temporal segmentation and annotation of ctions with semantic descriptions. Our solution consists of two stages. In the first stage, the video is segmented into "scenes", by utilizing the scene category information extracted from text-commentary. The second stage consists of classifying video-shots as well as the phrases in the textual description into various categories. The relevant phrases are then suitably mapped to the video-shots. The novel aspect of this work is the fine temporal scale at which semantic information is assigned to the video. As a result of our approach, we enable retrieval of specific actions that last only a few seconds, from several hours of video. This solution yields a large number of labeled exemplars, with no manual effort, that could be used by machine learning algorithms to learn complex actions.
The Mechanism of Additive Composition
Venue: arXiv cs.CL 2017
Year: 2017

Additive composition (Foltz et al, 1998; Landauer and Dumais, 1997; Mitchell and Lapata, 2010) is a widely used method for computing meanings of phrases, which takes the average of vector representations of the constituent words. In this article, we prove an upper bound for the bias of additive composition, which is the first theoretical analysis on compositional frameworks from a machine learning point of view. The bound is written in terms of collocation strength; we prove that the more exclusively two successive words tend to occur together, the more accurate one can guarantee their additive composition as an approximation to the natural phrase vector. Our proof relies on properties of natural language data that are empirically verified, and can be theoretically derived from an assumption that the data is generated from a Hierarchical Pitman-Yor Process. The theory endorses additive composition as a reasonable operation for calculating meanings of phrases, and suggests ways to improve additive compositionality, including: transforming entries of distributional word vectors by a function that meets a specific condition, constructing a novel type of vector representations to make additive composition sensitive to word order, and utilizing singular value decomposition to train word vectors.
Wilkinson's Inertia-Revealing Factorization and Its Application to Sparse Matrices
Venue: arXiv cs.NA 2017
Year: 2017

We propose a new inertia-revealing factorization for sparse symmetric matrices. The factorization scheme and the method for extracting the inertia from it were proposed in the 1960s for dense, banded, or tridiagonal matrices, but they have been abandoned in favor of faster methods. We show that this scheme can be applied to any sparse symmetric matrix and that the fill in the factorization is bounded by the fill in the sparse QR factorization of the same matrix (but is usually much smaller). We describe our serial proof-of-concept implementation, and present experimental results, studying the method's numerical stability and performance.
Predecessor problem on smooth distributions
Venue: arXiv cs.DS 2017
Year: 2017

We follow a research thread studying the predecessor problem on "smooth" distribution families. We propose a conceptually simpler solution utilizing well-known results from much better studied variant of the problem that assumes nothing about the input. As a side effect, we are able to extend the range of handled input distributions for the most studied case needing expected $\mathcal O(\log \log n)$ time, and we provide better insight into why the related methods are faster on smooth inputs.
Tight Bounds for Gomory-Hu-like Cut Counting
Venue: arXiv cs.DS 2017
Year: 2017

By a classical result of Gomory and Hu (1961), in every edge-weighted graph $G=(V,E,w)$, the minimum $st$-cut values, when ranging over all $s,t\in V$, take at most $|V|-1$ distinct values. That is, these $\binom{|V|}{2}$ instances exhibit redundancy factor $Ω(|V|)$. They further showed how to construct from $G$ a tree $(V,E',w')$ that stores all minimum $st$-cut values. Motivated by this result, we obtain tight bounds for the redundancy factor of several generalizations of the minimum $st$-cut problem. 1. Group-Cut: Consider the minimum $(A,B)$-cut, ranging over all subsets $A,B\subseteq V$ of given sizes $|A|=α$ and $|B|=β$. The redundancy factor is $Ω_{α,β}(|V|)$. 2. Multiway-Cut: Consider the minimum cut separating every two vertices of $S\subseteq V$, ranging over all subsets of a given size $|S|=k$. The redundancy factor is $Ω_{k}(|V|)$. 3. Multicut: Consider the minimum cut separating every demand-pair in $D\subseteq V\times V$, ranging over collections of $|D|=k$ demand pairs. The redundancy factor is $Ω_{k}(|V|^k)$. This result is a bit surprising, as the redundancy factor is much larger than in the first two problems. A natural application of these bounds is to construct small data structures that stores all relevant cut values, like the Gomory-Hu tree. We initiate this direction by giving some upper and lower bounds.
Efficient Sum of Outer Products Dictionary Learning (SOUP-DIL) - The $\ell_0$ Method
Venue: arXiv cs.LG 2017
Year: 2017

The sparsity of natural signals and images in a transform domain or dictionary has been extensively exploited in several applications such as compression, denoising and inverse problems. More recently, data-driven adaptation of synthesis dictionaries has shown promise in many applications compared to fixed or analytical dictionary models. However, dictionary learning problems are typically non-convex and NP-hard, and the usual alternating minimization approaches for these problems are often computationally expensive, with the computations dominated by the NP-hard synthesis sparse coding step. In this work, we investigate an efficient method for $\ell_{0}$ "norm"-based dictionary learning by first approximating the training data set with a sum of sparse rank-one matrices and then using a block coordinate descent approach to estimate the unknowns. The proposed block coordinate descent algorithm involves efficient closed-form solutions. In particular, the sparse coding step involves a simple form of thresholding. We provide a convergence analysis for the proposed block coordinate descent approach. Our numerical experiments show the promising performance and significant speed-ups provided by our method over the classical K-SVD scheme in sparse signal representation and image denoising.
Scalable Uplink Signal Detection in C-RANs via Randomized Gaussian Message Passing
Venue: arXiv cs.IT 2017
Year: 2017

Cloud Radio Access Network (C-RAN) is a promising architecture for unprecedented capacity enhancement in next-generation wireless networks thanks to the centralization and virtualization of base station processing. However, centralized signal processing in C-RANs involves high computational complexity that quickly becomes unaffordable when the network grows to a huge size. Among the first, this paper endeavours to design a scalable uplink signal detection algorithm, in the sense that both the complexity per unit network area and the total computation time remain constant when the network size grows. To this end, we formulate the signal detection in C-RAN as an inference problem over a bipartite random geometric graph. By passing messages among neighboring nodes, message passing (a.k.a. belief propagation) provides an efficient way to solve the inference problem over a sparse graph. However, the traditional message-passing algorithm is not guaranteed to converge, because the corresponding bipartite random geometric graph is locally dense and contains many short loops. As a major contribution of this paper, we propose a randomized Gaussian message passing (RGMP) algorithm to improve the convergence. Instead of exchanging messages simultaneously or in a fixed order, we propose to exchange messages asynchronously in a random order. The proposed RGMP algorithm demonstrates significantly better convergence performance than conventional message passing. The randomness of the message update schedule also simplifies the analysis, and allows the derivation of the convergence conditions for the RGMP algorithm. In addition, we propose a blockwise RGMP (B-RGMP) algorithm for practical implementation. The average computation time of B-RGMP remains constant when the network size increases.
Toward A Collection of Cloud Integration Patterns
Venue: arXiv cs.SE 2017
Year: 2017

Cloud computing is one of the most exciting IT trends nowadays. It poses several challenges on application integration with respect to, for example, security. In this work we collect and categorize several new integration patterns and pattern solutions with a focus on cloud integration requirements. Their evidence and examples are based on extensive literature and system reviews.
Fractals for Kernelization Lower Bounds
Venue: arXiv cs.CC 2017
Year: 2017

The composition technique is a popular method for excluding polynomial-size problem kernels for NP-hard parameterized problems. We present a new technique exploiting triangle-based fractal structures for extending the range of applicability of compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of problems dealing with length-bounded cuts. In particular, answering an open question of Golovach and Thilikos [Discrete Optim. 2011], we show that, unless NP $\subseteq$ coNP / poly, the NP-hard Length-Bounded Edge-Cut (LBEC) problem (delete at most $k$ edges such that the resulting graph has no $s$-$t$ path of length shorter than $\ell$) parameterized by the combination of $k$ and $\ell$ has no polynomial-size problem kernel. Our framework applies to planar as well as directed variants of the basic problems and also applies to both edge and vertex deletion problems. Along the way, we show that LBEC remains NP-hard on planar graphs, a result which we believe is interesting in its own right.