In statistical learning for real-world large-scale data problems, one must often resort to “streaming” algorithms which operate sequentially on small batches of data. In this work, we present an analysis of the information-theoretic limits of …
We consider tensor factorizations using a generative model and a Bayesian approach. We compute rigorously the mutual information, the Minimal Mean Square Error (MMSE), and unveil information-theoretic phase transitions. In addition, we study the …
We consider the problem of Gaussian mixture clustering in the high-dimensional limit where the data consists of m points in n dimensions, n,m → ∞ and α = m/n stays finite. Using exact but non-rigorous methods from statistical physics, we determine …
We consider the problem of grouping items into clusters based on few random pairwise comparisons between the items. We introduce three closely related algorithms for this task: a belief propagation algorithm approximating the Bayes optimal solution, …
We analyze the matrix factorization problem. Given a noisy measurement of a product of two matrices, the problem is to estimate back the original matrices. It arises in many applications, such as dictionary learning, blind matrix calibration, sparse …
In this paper, we consider the phase recovery problem, where a complex signal vector has to be estimated from the knowledge of the modulus of its linear projections, from a naive variational Bayesian point of view. In particular, we derive an …
Approximate message passing is an iterative algorithm for compressed sensing and related applications. A solid theory about the performance and convergence of the algorithm exists for measurement matrices having iid entries of zero mean. However, …
Superposition codes are efficient for the additive white gaussian noise channel. We provide here a replica analysis of the performances of these codes for large signals. We also consider a Bayesian approximate message passing decoder based on a …
In compressed sensing one measures sparse signals directly in a compressed form via a linear transform and then reconstructs the original signal. However, it is often the case that the linear transform itself is known only approximately, a situation …
Compressed sensing is designed to measure sparse signals directly in a compressed form. However, most signals of interest are only “approximately sparse”, i.e. even though the signal contains only a small fraction of relevant (large) components the …