54
54
Sep 23, 2013
09/13
by
Nicholas Ruozzi; Sekhar Tatikonda
texts
eye 54
favorite 0
comment 0
Gaussian belief propagation (GaBP) is an iterative algorithm for computing the mean of a multivariate Gaussian distribution, or equivalently, the minimum of a multivariate positive definite quadratic function. Sufficient conditions, such as walk-summability, that guarantee the convergence and correctness of GaBP are known, but GaBP may fail to converge to the correct solution given an arbitrary positive definite quadratic function. As was observed in previous work, the GaBP algorithm fails to...
Source: http://arxiv.org/abs/1212.0171v1
7
7.0
Jun 29, 2018
06/18
by
Patrick Rebeschini; Sekhar Tatikonda
texts
eye 7
favorite 0
comment 0
This paper investigates message-passing algorithms for solving systems of linear equations in the Laplacian matrices of graphs and to compute electric flows. These two problems are fundamental primitives that arise in several domains such as computer science, electrical engineering, operations research, and machine learning. Despite the extensive literature on approximately solving these problems in quasi-linear time, the algorithms that have been proposed are typically centralized and involve...
Topics: Data Structures and Algorithms, Machine Learning, Mathematics, Optimization and Control,...
Source: http://arxiv.org/abs/1611.07138
77
77
Sep 20, 2013
09/13
by
Nicholas Ruozzi; Sekhar Tatikonda
texts
eye 77
favorite 0
comment 0
The max-product algorithm, a local message-passing scheme that attempts to compute the most probable assignment (MAP) of a given probability distribution, has been successfully employed as a method of approximate inference for applications arising in coding theory, computer vision, and machine learning. However, the max-product algorithm is not guaranteed to converge to the MAP assignment, and if it does, is not guaranteed to recover the MAP assignment. Alternative convergent message-passing...
Source: http://arxiv.org/abs/1002.3239v3
60
60
Sep 18, 2013
09/13
by
Jian Ni; Sekhar Tatikonda
texts
eye 60
favorite 0
comment 0
Inference of the network structure (e.g., routing topology) and dynamics (e.g., link performance) is an essential component in many network design and management tasks. In this paper we propose a new, general framework for analyzing and designing routing topology and link performance inference algorithms using ideas and tools from phylogenetic inference in evolutionary biology. The framework is applicable to a variety of measurement techniques. Based on the framework we introduce and develop...
Source: http://arxiv.org/abs/0809.0158v1
115
115
Jul 20, 2013
07/13
by
Sekhar Tatikonda; Sanjoy Mitter
texts
eye 115
favorite 0
comment 0
We introduce a general framework for treating channels with memory and feedback. First, we generalize Massey's concept of directed information and use it to characterize the feedback capacity of general channels. Second, we present coding results for Markov channels. This requires determining appropriate sufficient statistics at the encoder and decoder. Third, a dynamic programming framework for computing the capacity of Markov channels is presented. Fourth, it is shown that the average cost...
Source: http://arxiv.org/abs/cs/0609139v1
48
48
Sep 23, 2013
09/13
by
Ramji Venkataramanan; Sekhar Tatikonda
texts
eye 48
favorite 0
comment 0
We study a new class of codes for Gaussian multi-terminal source and channel coding. These codes are designed using the statistical framework of high-dimensional linear regression and are called Sparse Superposition or Sparse Regression codes. Codewords are linear combinations of subsets of columns of a design matrix. These codes were recently introduced by Barron and Joseph and shown to achieve the channel capacity of AWGN channels with computationally feasible decoding. They have also...
Source: http://arxiv.org/abs/1212.2125v1
12
12
Aug 11, 2020
08/20
by
Nicholas Ruozzi; Sekhar Tatikonda
data
eye 12
favorite 0
comment 0
Source: http://academictorrents.com/details/264e2cd52f86ee907b6b4f3d433b2c5e21cb6c9c
44
44
Sep 23, 2013
09/13
by
Ramji Venkataramanan; Tuhin Sarkar; Sekhar Tatikonda
texts
eye 44
favorite 0
comment 0
We propose computationally efficient encoders and decoders for lossy compression using a Sparse Regression Code. The codebook is defined by a design matrix and codewords are structured linear combinations of columns of this matrix. The proposed encoding algorithm sequentially chooses columns of the design matrix to successively approximate the source sequence. The algorithm is shown to achieve the optimal distortion-rate function for i.i.d Gaussian sources under the squared-error distortion...
Source: http://arxiv.org/abs/1212.1707v1
50
50
Jul 20, 2013
07/13
by
John Hartigan; David Pollard; Sekhar Tatikonda
texts
eye 50
favorite 0
comment 0
The paper provides a simpler method for proving a delicate inequality that was used by Achlioptis and Naor to establish asymptotic concentration for chromatic numbers of Erdos-Renyi random graphs. The simplifications come from two new ideas. The first involves a sharpened form of a piece of statistical folklore regarding goodness-of-fit tests for two-way tables of Poisson counts under linear conditioning constraints. The second idea takes the form of a new inequality that controls the extreme...
Source: http://arxiv.org/abs/1107.3818v1
50
50
Sep 19, 2013
09/13
by
Shaohua Yang; Aleksandar Kavcic; Sekhar Tatikonda
texts
eye 50
favorite 0
comment 0
For a stationary additive Gaussian-noise channel with a rational noise power spectrum of a finite-order $L$, we derive two new results for the feedback capacity under an average channel input power constraint. First, we show that a very simple feedback-dependent Gauss-Markov source achieves the feedback capacity, and that Kalman-Bucy filtering is optimal for processing the feedback. Based on these results, we develop a new method for optimizing the channel inputs for achieving the Cover-Pombra...
Source: http://arxiv.org/abs/cs/0701099v1
64
64
Sep 18, 2013
09/13
by
Giacomo Como; Serdar Yuksel; Sekhar Tatikonda
texts
eye 64
favorite 0
comment 0
The error exponent of Markov channels with feedback is studied in the variable-length block-coding setting. Burnashev's classic result is extended and a single letter characterization for the reliability function of finite-state Markov channels is presented, under the assumption that the channel state is causally observed both at the transmitter and at the receiver side. Tools from stochastic control theory are used in order to treat channels with intersymbol interference. In particular the...
Source: http://arxiv.org/abs/0707.2014v1
46
46
Sep 18, 2013
09/13
by
Ramji Venkataramanan; Sekhar Tatikonda; Kannan Ramchandran
texts
eye 46
favorite 0
comment 0
This paper considers a binary channel with deletions and insertions, where each input bit is transformed in one of the following ways: it is deleted with probability d, or an extra bit is added after it with probability i, or it is transmitted unmodified with probability 1-d-i. A computable lower bound on the capacity of this channel is derived. The transformation of the input sequence by the channel may be viewed in terms of runs as follows: some runs of the input sequence get shorter/longer,...
Source: http://arxiv.org/abs/1102.5112v4
48
48
Sep 21, 2013
09/13
by
Jialing Liu; Nicola Elia; Sekhar Tatikonda
texts
eye 48
favorite 0
comment 0
In this paper, we propose capacity-achieving communication schemes for Gaussian finite-state Markov channels (FSMCs) subject to an average channel input power constraint, under the assumption that the transmitters can have access to delayed noiseless output feedback as well as instantaneous or delayed channel state information (CSI). We show that the proposed schemes reveals connections between feedback communication and feedback control.
Source: http://arxiv.org/abs/0808.2089v2
59
59
Sep 23, 2013
09/13
by
Ramji Venkataramanan; Antony Joseph; Sekhar Tatikonda
texts
eye 59
favorite 0
comment 0
We study a new class of codes for lossy compression with the squared-error distortion criterion, designed using the statistical framework of high-dimensional linear regression. Codewords are linear combinations of subsets of columns of a design matrix. Called a Sparse Superposition or Sparse Regression codebook, this structure is motivated by an analogous construction proposed recently by Barron and Joseph for communication over an AWGN channel. For i.i.d Gaussian sources and minimum-distance...
Source: http://arxiv.org/abs/1202.0840v2
15
15
Jun 28, 2018
06/18
by
Michael J. Kane; Bryan Lewis; Sekhar Tatikonda; Simon Urbanek
texts
eye 15
favorite 0
comment 0
Linear regression models depend directly on the design matrix and its properties. Techniques that efficiently estimate model coefficients by partitioning rows of the design matrix are increasingly popular for large-scale problems because they fit well with modern parallel computing architectures. We propose a simple measure of {\em concordance} between a design matrix and a subset of its rows that estimates how well a subset captures the variance-covariance structure of a larger data set. We...
Topics: Statistics, Machine Learning
Source: http://arxiv.org/abs/1507.03285
