sparse matrices

Streaming Bayesian inference: Theoretical limits and mini-batch approximate message-passing

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 …

Performance Limits for Noisy Multimeasurement Vector Problems

Compressed sensing (CS) demonstrates that sparse signals can be estimated from underdetermined linear systems. Distributed CS (DCS) further reduces the number of measurements by considering joint sparsity within signal ensembles. DCS with jointly …

Phase Transitions and Sample Complexity in Bayes-Optimal Matrix Factorization

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 …

Spectral detection on sparse hypergraphs

We consider the problem of the assignment of nodes into communities from a set of hyperedges, where every hyperedge is a noisy observation of the community assignment of the adjacent nodes. We focus in particular on the sparse regime where the number …

Phase transitions in sparse PCA

We study optimal estimation for sparse principal component analysis when the number of non-zero elements is small but on the same order as the dimension of the data. We employ approximate message passing (AMP) algorithm and its state evolution to …

Phase diagram and approximate message passing for blind calibration and dictionary learning

We consider dictionary learning and blind calibration for signals and matrices created from a random ensemble. We study the mean-squared error in the limit of large signal dimension using the replica method and unveil the appearance of phase …

Non-adaptive pooling strategies for detection of rare faulty items

We study non-adaptive pooling strategies for detection of rare faulty items. Given a binary sparse N dimensional signal x, how to construct a sparse binary M × N pooling matrix F such that the signal can be reconstructed from the smallest possible …

Non-adaptive pooling strategies for detection of rare faulty items

We study non-adaptive pooling strategies for detection of rare faulty items. Given a binary sparse N dimensional signal x, how to construct a sparse binary M × N pooling matrix F such that the signal can be reconstructed from the smallest possible …

Compressed sensing under matrix uncertainty: Optimum thresholds and robust approximate message passing

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 of approximately-sparse signals: Phase transitions and optimal reconstruction

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 …