OpenRaiser/Intern-Atlas huggingface dataset:
On the Feedback Capacity of the Fully Connected $K$-User Interference Channel
Venue: arXiv cs.IT 2012
Year: 2012

The symmetric K user interference channel with fully connected topology is considered, in which (a) each receiver suffers interference from all other (K-1) transmitters, and (b) each transmitter has causal and noiseless feedback from its respective receiver. The number of generalized degrees of freedom (GDoF) is characterized in terms of α, where the interference-to-noise ratio (INR) is given by INR=SNR^α. It is shown that the per-user GDoF of this network is the same as that of the 2-user interference channel with feedback, except for α=1, for which existence of feedback does not help in terms of GDoF. The coding scheme proposed for this network, termed cooperative interference alignment, is based on two key ingredients, namely, interference alignment and interference decoding. Moreover, an approximate characterization is provided for the symmetric feedback capacity of the network, when the SNR and INR are far apart from each other.
Distributed Lossy Source Coding Using Real-Number Codes
Venue: arXiv cs.IT 2012
Year: 2012

We show how real-number codes can be used to compress correlated sources, and establish a new framework for lossy distributed source coding, in which we quantize compressed sources instead of compressing quantized sources. This change in the order of binning and quantization blocks makes it possible to model correlation between continuous-valued sources more realistically and correct quantization error when the sources are completely correlated. The encoding and decoding procedures are described in detail, for discrete Fourier transform (DFT) codes. Reconstructed signal, in the mean squared error sense, is seen to be better than that in the conventional approach.
Stochastic Belief Propagation: A Low-Complexity Alternative to the Sum-Product Algorithm
Venue: arXiv cs.IT 2012
Year: 2012

The sum-product or belief propagation (BP) algorithm is a widely-used message-passing algorithm for computing marginal distributions in graphical models with discrete variables. At the core of the BP message updates, when applied to a graphical model with pairwise interactions, lies a matrix-vector product with complexity that is quadratic in the state dimension $d$, and requires transmission of a $(d-1)$-dimensional vector of real numbers (messages) to its neighbors. Since various applications involve very large state dimensions, such computation and communication complexities can be prohibitively complex. In this paper, we propose a low-complexity variant of BP, referred to as stochastic belief propagation (SBP). As suggested by the name, it is an adaptively randomized version of the BP message updates in which each node passes randomly chosen information to each of its neighbors. The SBP message updates reduce the computational complexity (per iteration) from quadratic to linear in $d$, without assuming any particular structure of the potentials, and also reduce the communication complexity significantly, requiring only $\log{d}$ bits transmission per edge. Moreover, we establish a number of theoretical guarantees for the performance of SBP, showing that it converges almost surely to the BP fixed point for any tree-structured graph, and for graphs with cycles satisfying a contractivity condition. In addition, for these graphical models, we provide non-asymptotic upper bounds on the convergence rate, showing that the $\ell_{\infty}$ norm of the error vector decays no slower than $O(1/\sqrt{t})$ with the number of iterations $t$ on trees and the mean square error decays as $O(1/t)$ for general graphs. These analysis show that SBP can provably yield reductions in computational and communication complexities for various classes of graphical models.
Quantization via Empirical Divergence Maximization
Venue: arXiv cs.IT 2012
Year: 2012

Empirical divergence maximization (EDM) refers to a recently proposed strategy for estimating f-divergences and likelihood ratio functions. This paper extends the idea to empirical vector quantization where one seeks to empirically derive quantization rules that maximize the Kullback-Leibler divergence between two statistical hypotheses. We analyze the estimator's error convergence rate leveraging Tsybakov's margin condition and show that rates as fast as 1/n are possible, where n equals the number of training samples. We also show that the Flynn and Gray algorithm can be used to efficiently compute EDM estimates and show that they can be efficiently and accurately represented by recursive dyadic partitions. The EDM formulation have several advantages. First, the formulation gives access to the tools and results of empirical process theory that quantify the estimator's error convergence rate. Second, the formulation provides a previously unknown derivation for the Flynn and Gray algorithm. Third, the flexibility it affords allows one to avoid a small-cell assumption common in other approaches. Finally, we illustrate the potential use of the method through an example.
Analysis of Thompson Sampling for the multi-armed bandit problem
Venue: arXiv cs.LG 2012
Year: 2012

The multi-armed bandit problem is a popular model for studying exploration/exploitation trade-off in sequential decision problems. Many algorithms are now available for this well-studied problem. One of the earliest algorithms, given by W. R. Thompson, dates back to 1933. This algorithm, referred to as Thompson Sampling, is a natural Bayesian algorithm. The basic idea is to choose an arm to play according to its probability of being the best arm. Thompson Sampling algorithm has experimentally been shown to be close to optimal. In addition, it is efficient to implement and exhibits several desirable properties such as small regret for delayed feedback. However, theoretical understanding of this algorithm was quite limited. In this paper, for the first time, we show that Thompson Sampling algorithm achieves logarithmic expected regret for the multi-armed bandit problem. More precisely, for the two-armed bandit problem, the expected regret in time $T$ is $O(\frac{\ln T}Δ + \frac{1}{Δ^3})$. And, for the $N$-armed bandit problem, the expected regret in time $T$ is $O([(\sum_{i=2}^N \frac{1}{Δ_i^2})^2] \ln T)$. Our bounds are optimal but for the dependence on $Δ_i$ and the constant factors in big-Oh.
On Concentration and Revisited Large Deviations Analysis of Binary Hypothesis Testing
Venue: arXiv cs.IT 2012
Year: 2012

This paper first introduces a refined version of the Azuma-Hoeffding inequality for discrete-parameter martingales with uniformly bounded jumps. The refined inequality is used to revisit the large deviations analysis of binary hypothesis testing.
Moderate Deviations Analysis of Binary Hypothesis Testing
Venue: arXiv cs.IT 2012
Year: 2012

This paper is focused on the moderate-deviations analysis of binary hypothesis testing. The analysis relies on a concentration inequality for discrete-parameter martingales with bounded jumps, where this inequality forms a refinement to the Azuma-Hoeffding inequality. Relations of the analysis to the moderate deviations principle for i.i.d. random variables and to the relative entropy are considered.
Localized Geometric Query Problems
Venue: arXiv cs.CG 2012
Year: 2012

A new class of geometric query problems are studied in this paper. We are required to preprocess a set of geometric objects $P$ in the plane, so that for any arbitrary query point $q$, the largest circle that contains $q$ but does not contain any member of $P$, can be reported efficiently. The geometric sets that we consider are point sets and boundaries of simple polygons.
Formal approaches to information hiding: An analysis of interactive systems, statistical disclosure control, and refinement of specifications
Venue: arXiv cs.CR 2012
Year: 2012

In this thesis we consider the problem of information hiding in the scenarios of interactive systems, statistical disclosure control, and refinement of specifications. We apply quantitative approaches to information flow in the first two cases, and we propose improvements for the usual solutions based on process equivalences for the third case. In the first scenario we consider the problem of defining the information leakage in interactive systems where secrets and observables can alternate during the computation and influence each other. We show that the information-theoretic approach which interprets such systems as (simple) noisy channels is not valid. The principle can be recovered if we consider channels with memory and feedback. We also propose the use of directed information from input to output as the real measure of leakage in interactive systems. In the second scenario we consider the problem of statistical disclosure control, which concerns how to reveal accurate statistics about a set of respondents while preserving the privacy of individuals. We focus on the concept of differential privacy, a notion that has become very popular in the database community. We show how to model the query system in terms of an information-theoretic channel, and we compare the notion of differential privacy with that of min-entropy leakage.In the third scenario we address the problem of using process equivalences to characterize information-hiding properties. We show that, in the presence of nondeterminism, this approach may rely on the assumption that the scheduler "works for the benefit of the protocol", and this is often not a safe assumption. We present a formalism in which we can specify admissible schedulers and, correspondingly, safe versions of complete-trace equivalence and bisimulation, and we show that safe equivalences can be used to establish information-hiding properties.
An Approach using Demisubmartingales for the Stochastic Analysis of Networks
Venue: arXiv cs.NI 2012
Year: 2012

Stochastic network calculus is the probabilistic version of the network calculus, which uses envelopes to perform probabilistic analysis of queueing networks. The accuracy of probabilistic end-to-end delay or backlog bounds computed using network calculus has always been a concern. In this paper, we propose novel end-to-end probabilistic bounds based on demisubmartingale inequalities which improve the existing bounds for the tandem networks of GI/GI/1 queues. In particular, we show that reasonably accurate bounds are achieved by comparing the new bounds with the existing results for a network of M/M/1 queues.
Single-User Beamforming in Large-Scale MISO Systems with Per-Antenna Constant-Envelope Constraints: The Doughnut Channel
Venue: arXiv cs.IT 2012
Year: 2012

Large antenna arrays at the base station (BS) has recently been shown to achieve remarkable intra-cell interference suppression at low complexity. However, building large arrays in practice, would require the use of power-efficient RF amplifiers, which generally have poor linearity characteristics and hence would require the use of input signals with a very small peak-to-average power ratio (PAPR). In this paper, we consider the single-user Multiple-Input Single-Output (MISO) downlink channel for the case where the BS antennas are constrained to transmit signals having constant envelope (CE). We show that, with per-antenna CE transmission the effective channel seen by the receiver is a SISO AWGN channel with its input constrained to lie in a doughnut-shaped region. For single-path direct-line-of-sight (DLOS) and general i.i.d. fading channels, analysis of the effective doughnut channel shows that under a per-antenna CE input constraint, i) compared to an average-only total transmit power constrained MISO channel, the extra total transmit power required to achieve a desired information rate is small and bounded, ii) with N base station antennas an O(N) array power gain is achievable, and iii) for a desired information rate, using power-efficient amplifiers with CE inputs would require significantly less total transmit power when compared to using highly linear (power-inefficient) amplifiers with high PAPR inputs.
New noise-based logic representations to avoid some problems with time complexity
Venue: arXiv cs.OH 2012
Year: 2012

Instantaneous noise-based logic can avoid time-averaging, which implies significant potential for low-power parallel operations in beyond-Moore-law-chips. However, the universe (uniform superposition) will be zero with high probability (non-zero with exponentially low probability) in the random-telegraph-wave representation thus the operations with the universe would require exponential time-complexity. To fix this deficiency, we modify the amplitudes of the signals of the L and H states and achieve an exponential speedup compared to the old situation. Another improvement concerns the identification of a single product (hyperspace) state. We introduce a time shifted noise-based logic, which is constructed by shifting each reference signal with a small time delay. This modification implies an exponential speedup of single hyperspace vector identification compared to the former case and it requires the same, O(N) complexity as in quantum computing.
Contextually Guided Semantic Labeling and Search for 3D Point Clouds
Venue: arXiv cs.RO 2012
Year: 2012

RGB-D cameras, which give an RGB image to- gether with depths, are becoming increasingly popular for robotic perception. In this paper, we address the task of detecting commonly found objects in the 3D point cloud of indoor scenes obtained from such cameras. Our method uses a graphical model that captures various features and contextual relations, including the local visual appearance and shape cues, object co-occurence relationships and geometric relationships. With a large number of object classes and relations, the model's parsimony becomes important and we address that by using multiple types of edge potentials. We train the model using a maximum-margin learning approach. In our experiments over a total of 52 3D scenes of homes and offices (composed from about 550 views), we get a performance of 84.06% and 73.38% in labeling office and home scenes respectively for 17 object classes each. We also present a method for a robot to search for an object using the learned model and the contextual information available from the current labelings of the scene. We applied this algorithm successfully on a mobile robot for the task of finding 12 object classes in 10 different offices and achieved a precision of 97.56% with 78.43% recall.
Successful attack on permutation-parity-machine-based neural cryptography
Venue: arXiv cs.CR 2012
Year: 2012

An algorithm is presented which implements a probabilistic attack on the key-exchange protocol based on permutation parity machines. Instead of imitating the synchronization of the communicating partners, the strategy consists of a Monte Carlo method to sample the space of possible weights during inner rounds and an analytic approach to convey the extracted information from one outer round to the next one. The results show that the protocol under attack fails to synchronize faster than an eavesdropper using this algorithm.
Regret Bound by Variation for Online Convex Optimization
Venue: arXiv cs.LG 2012
Year: 2012

In citep{Hazan-2008-extract}, the authors showed that the regret of online linear optimization can be bounded by the total variation of the cost vectors. In this paper, we extend this result to general online convex optimization. We first analyze the limitations of the algorithm in \citep{Hazan-2008-extract} when applied it to online convex optimization. We then present two algorithms for online convex optimization whose regrets are bounded by the variation of cost functions. We finally consider the bandit setting, and present a randomized algorithm for online bandit convex optimization with a variation-based regret bound. We show that the regret bound for online bandit convex optimization is optimal when the variation of cost functions is independent of the number of trials.
Optimal Phase Transitions in Compressed Sensing
Venue: arXiv cs.IT 2012
Year: 2012

Compressed sensing deals with efficient recovery of analog signals from linear encodings. This paper presents a statistical study of compressed sensing by modeling the input signal as an i.i.d. process with known distribution. Three classes of encoders are considered, namely optimal nonlinear, optimal linear and random linear encoders. Focusing on optimal decoders, we investigate the fundamental tradeoff between measurement rate and reconstruction fidelity gauged by error probability and noise sensitivity in the absence and presence of measurement noise, respectively. The optimal phase transition threshold is determined as a functional of the input distribution and compared to suboptimal thresholds achieved by popular reconstruction algorithms. In particular, we show that Gaussian sensing matrices incur no penalty on the phase transition threshold with respect to optimal nonlinear encoding. Our results also provide a rigorous justification of previous results based on replica heuristics in the weak-noise regime.
Understanding the Social Cascading of Geekspeak and the Upshots for Social Cognitive Systems
Venue: arXiv cs.AI 2012
Year: 2012

Barring swarm robotics, a substantial share of current machine-human and machine-machine learning and interaction mechanisms are being developed and fed by results of agent-based computer simulations, game-theoretic models, or robotic experiments based on a dyadic communication pattern. Yet, in real life, humans no less frequently communicate in groups, and gain knowledge and take decisions basing on information cumulatively gleaned from more than one single source. These properties should be taken into consideration in the design of autonomous artificial cognitive systems construed to interact with learn from more than one contact or 'neighbour'. To this end, significant practical import can be gleaned from research applying strict science methodology to human and social phenomena, e.g. to discovery of realistic creativity potential spans, or the 'exposure thresholds' after which new information could be accepted by a cognitive agent. The results will be presented of a project analysing the social propagation of neologisms in a microblogging service. From local, low-level interactions and information flows between agents inventing and imitating discrete lexemes we aim to describe the processes of the emergence of more global systemic order and dynamics, using the latest methods of complexity science. Whether in order to mimic them, or to 'enhance' them, parameters gleaned from complexity science approaches to humans' social and humanistic behaviour should subsequently be incorporated as points of reference in the field of robotics and human-machine interaction.
Multivariate information measures: an experimentalist's perspective
Venue: arXiv cs.IT 2012
Year: 2012

Information theory is widely accepted as a powerful tool for analyzing complex systems and it has been applied in many disciplines. Recently, some central components of information theory - multivariate information measures - have found expanded use in the study of several phenomena. These information measures differ in subtle yet significant ways. Here, we will review the information theory behind each measure, as well as examine the differences between these measures by applying them to several simple model systems. In addition to these systems, we will illustrate the usefulness of the information measures by analyzing neural spiking data from a dissociated culture through early stages of its development. We hope that this work will aid other researchers as they seek the best multivariate information measure for their specific research goals and system. Finally, we have made software available online which allows the user to calculate all of the information measures discussed within this paper.
Modelling the Delay Distribution of Binary Spray and Wait Routing Protocol
Venue: arXiv cs.NI 2012
Year: 2012

This article proposes a stochastic model to obtain the end-to-end delay law between two nodes of a Delay Tolerant Network (DTN). We focus on the commonly used Binary Spray and Wait (BSW) routing protocol and propose a model that can be applied to homogeneous or heterogeneous networks (i.e. when the inter-contact law parameter takes one or several values). To the best of our knowledge, this is the first model allowing to estimate the delay distribution of Binary Spray and Wait DTN protocol in heterogeneous networks. We first detail the model and propose a set of simulations to validate the theoretical results.
Developing Embodied Multisensory Dialogue Agents
Venue: arXiv cs.AI 2012
Year: 2012

A few decades of work in the AI field have focused efforts on developing a new generation of systems which can acquire knowledge via interaction with the world. Yet, until very recently, most such attempts were underpinned by research which predominantly regarded linguistic phenomena as separated from the brain and body. This could lead one into believing that to emulate linguistic behaviour, it suffices to develop 'software' operating on abstract representations that will work on any computational machine. This picture is inaccurate for several reasons, which are elucidated in this paper and extend beyond sensorimotor and semantic resonance. Beginning with a review of research, I list several heterogeneous arguments against disembodied language, in an attempt to draw conclusions for developing embodied multisensory agents which communicate verbally and non-verbally with their environment. Without taking into account both the architecture of the human brain, and embodiment, it is unrealistic to replicate accurately the processes which take place during language acquisition, comprehension, production, or during non-linguistic actions. While robots are far from isomorphic with humans, they could benefit from strengthened associative connections in the optimization of their processes and their reactivity and sensitivity to environmental stimuli, and in situated human-machine interaction. The concept of multisensory integration should be extended to cover linguistic input and the complementary information combined from temporally coincident sensory impressions.
Robustly Stable Signal Recovery in Compressed Sensing with Structured Matrix Perturbation
Venue: arXiv cs.IT 2012
Year: 2012

The sparse signal recovery in the standard compressed sensing (CS) problem requires that the sensing matrix be known a priori. Such an ideal assumption may not be met in practical applications where various errors and fluctuations exist in the sensing instruments. This paper considers the problem of compressed sensing subject to a structured perturbation in the sensing matrix. Under mild conditions, it is shown that a sparse signal can be recovered by $\ell_1$ minimization and the recovery error is at most proportional to the measurement noise level, which is similar to the standard CS result. In the special noise free case, the recovery is exact provided that the signal is sufficiently sparse with respect to the perturbation level. The formulated structured sensing matrix perturbation is applicable to the direction of arrival estimation problem, so has practical relevance. Algorithms are proposed to implement the $\ell_1$ minimization problem and numerical simulations are carried out to verify the result obtained.