On the Universality of Noiseless Linear Estimation with Respect to the Measurement Matrix

Abstract

In a noiseless linear estimation problem, one aims to reconstruct a vector x* from the knowledge of its linear projections y=Phi x*. There have been many theoretical works concentrating on the case where the matrix Phi is a random i.i.d. one, but a number of heuristic evidence suggests that many of these results are universal and extend well beyond this restricted case. Here we revisit this problematic through the prism of development of message passing methods, and consider not only the universality of the l1 transition, as previously addressed, but also the one of the optimal Bayesian reconstruction. We observed that the universality extends to the Bayes-optimal minimum mean-squared (MMSE) error, and to a range of structured matrices.

arXiv comment13 pages, 4 figures

References in corpus (13)

• Message Passing Algorithms for Compressed Sensing
• Expectation Propagation for approximate Bayesian inference
• The Convex Geometry of Linear Inverse Problems
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Universality in polytope phase transitions and message passing algorithms
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Statistical physics-based reconstruction in compressed sensing
• A typical reconstruction limit of compressed sensing based on Lp-norm minimization
• Analysis of CDMA systems that are characterized by eigenvalue spectrum
• The Mutual Information in Random Linear Estimation
• The Mutual Information in Random Linear Estimation Beyond i.i.d. Matrices