2.5k citations · 10k across the 171 of their papers we have counts for
37 papers · 1 filter
Compressing Tabular Data via Latent Variable Estimation
Andrea Montanari, Eric Weiner
Data used for analytics and machine learning often take the form of tables with categorical entries. We introduce a family of lossless compression algorithms for such data that pro…
An Information-Theoretic View of Stochastic Localization
Ahmed El Alaoui, Andrea Montanari
Given a probability measure over , it is often useful to approximate it by the convex combination of a small number of probability measures, such that each compo…
State Evolution for Approximate Message Passing with Non-Separable Functions
Raphael Berthier, Andrea Montanari, Phan-Minh Nguyen
Given a high-dimensional data matrix , Approximate Message Passing (AMP) algorithms construct sequences of vectors ${\boldsymbol u}^t\in{…
Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
Yash Deshpande, Emmanuel Abbe, Andrea Montanari
We develop an information-theoretic view of the stochastic block model, a popular statistical model for the large-scale structure of complex networks. A graph from such a model…
A Perspective on Future Research Directions in Information Theory
Jeffrey G. Andrews, Alexandros Dimakis, Lara Dolecek +15
Information theory is rapidly approaching its 70th birthday. What are promising future directions for research in information theory? Where will information theory be having the mo…
Statistical Estimation: From Denoising to Sparse Regression and Hidden Cliques
Eric W. Tramel, Santhosh Kumar, Andrei Giurgiu +1
These notes review six lectures given by Prof. Andrea Montanari on the topic of statistical estimation for linear models. The first two lectures cover the principles of signal reco…
Non-negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics
Andrea Montanari, Emile Richard
Principal component analysis (PCA) aims at estimating the direction of maximal variability of a high-dimensional dataset. A natural question is: does this task become easier, and e…
Information-theoretically Optimal Sparse PCA
Yash Deshpande, Andrea Montanari
Sparse Principal Component Analysis (PCA) is a dimensionality reduction technique wherein one seeks a low-rank representation of a data matrix with additional sparsity constraints…
The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
David L. Donoho, Matan Gavish, Andrea Montanari
Let be an unknown by matrix. In matrix recovery, one takes linear measurements of , where $y_i = \Tr(a_i^T X_0)$ and each is a …
Subsampling at Information Theoretically Optimal Rates
Adel Javanmard, Andrea Montanari
We study the problem of sampling a random signal with sparse support in frequency domain. Shannon famously considered a scheme that instantaneously samples the signal at equispaced…
Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing
David L. Donoho, Adel Javanmard, Andrea Montanari
We study the compressed sensing reconstruction problem for a broad class of random, band-diagonal sensing matrices. This construction is inspired by the idea of spatial coupling in…
Accurate Prediction of Phase Transitions in Compressed Sensing via a Connection to Minimax Denoising
David Donoho, Iain Johnstone, Andrea Montanari
Compressed sensing posits that, within limits, one can undersample a sparse signal and yet reconstruct it accurately. Knowing the precise limits to such undersampling is important…
Optimal coding for the deletion channel with small deletion probability
Yashodhan Kanoria, Andrea Montanari
The deletion channel is the simplest point-to-point communication channel that models lack of synchronization. Input bits are deleted independently with probability d, and when the…
Compressed Sensing over -balls: Minimax Mean Square Error
David Donoho, Iain Johnstone, Arian Maleki +1
We consider the compressed sensing problem, where the object $x_0 \in \bR^N$ is to be recovered from incomplete measurements ; here the sensing matrix is an $n \t…
Information Theoretic Limits on Learning Stochastic Differential Equations
José Bento, Morteza Ibrahimi, Andrea Montanari
Consider the problem of learning the drift coefficient of a stochastic differential equation from a sample path. In this paper, we assume that the drift is parametrized by a high d…
Lossy compression of discrete sources via Viterbi algorithm
Shirin Jalali, Andrea Montanari, Tsachy Weissman
We present a new lossy compressor for discrete-valued sources. For coding a sequence , the encoder starts by assigning a certain cost to each possible reconstruction sequence.…
Graphical Models Concepts in Compressed Sensing
Andrea Montanari
This paper surveys recent work in applying ideas from graphical models and message passing algorithms to solve large scale regularized regression problems. In particular, the focus…
Applications of Lindeberg Principle in Communications and Statistical Learning
Satish Babu Korada, Andrea Montanari
We use a generalization of the Lindeberg principle developed by Sourav Chatterjee to prove universality properties for various problems in communications, statistical learning and…
On the deletion channel with small deletion probability
Yashodhan Kanoria, Andrea Montanari
The deletion channel is the simplest point-to-point communication channel that models lack of synchronization. Despite significant effort, little is known about its capacity, and e…
Message Passing Algorithms for Compressed Sensing: II. Analysis and Validation
David L. Donoho, Arian Maleki, Andrea Montanari
In a recent paper, the authors proposed a new class of low-complexity iterative thresholding algorithms for reconstructing sparse signals from a small set of linear measurements \c…
Message Passing Algorithms for Compressed Sensing: I. Motivation and Construction
David L. Donoho, Arian Maleki, Andrea Montanari
In a recent paper, the authors proposed a new class of low-complexity iterative thresholding algorithms for reconstructing sparse signals from a small set of linear measurements \c…
Message Passing Algorithms for Compressed Sensing
David L. Donoho, Arian Maleki, Andrea Montanari
Compressed sensing aims to undersample certain high-dimensional signals, yet accurately reconstruct them by exploiting signal characteristics. Accurate reconstruction is possible w…
An Implementable Scheme for Universal Lossy Compression of Discrete Markov Sources
Shirin Jalali, Andrea Montanari, Tsachy Weissman
We present a new lossy compressor for discrete sources. For coding a source sequence , the encoder starts by assigning a certain cost to each reconstruction sequence. It then…
Coding for Network Coding
Andrea Montanari, Ruediger Urbanke
We consider communication over a noisy network under randomized linear network coding. Possible error mechanism include node- or link- failures, Byzantine behavior of nodes, or an…