Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing

Abstract

Performance of regularized least-squares estimation in noisy compressed sensing is analyzed in the limit when the dimensions of the measurement matrix grow large. The sensing matrix is considered to be from a class of random ensembles that encloses as special cases standard Gaussian, row-orthogonal, geometric and so-called T-orthogonal constructions. Source vectors that have non-uniform sparsity are included in the system model. Regularization based on l1-norm and leading to LASSO estimation, or basis pursuit denoising, is given the main emphasis in the analysis. Extensions to l2-norm and "zero-norm" regularization are also briefly discussed. The analysis is carried out using the replica method in conjunction with some novel matrix integration results. Numerical experiments for LASSO are provided to verify the accuracy of the analytical results. The numerical experiments show that for noisy compressed sensing, the standard Gaussian ensemble is a suboptimal choice for the measurement matrix. Orthogonal constructions provide a superior performance in all considered scenarios and are easier to implement in practical applications. It is also discovered that for non-uniform sparsity patterns the T-orthogonal matrices can further improve the mean square error behavior of the reconstruction when the noise level is not too high. However, as the additive noise becomes more prominent in the system, the simple row-orthogonal measurement matrix appears to be the best choice out of the considered ensembles.

revised version accepted for publication in IEEE Trans. Inform. Theory; 25 pages, 5 figures

References in corpus (31)

• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• The Thermodynamic Limit in Mean Field Spin Glass Models
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• 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
• Tight bounds for LDPC and LDGM codes under MAP decoding
• Analysis of CDMA systems that are characterized by eigenvalue spectrum
• Quadratic replica coupling in the Sherrington-Kirkpatrick mean field spin glass model
• A Theory of Solving TAP Equations for Ising Models with General Invariant Random Matrices
• On the Performance of Turbo Signal Recovery with Partial DFT Sensing Matrices
• Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels
• Sharp Bounds for Optimal Decoding of Low Density Parity Check Codes
• The Effect of Spatial Coupling on Compressive Sensing
• Optimal incorporation of sparsity information by weighted ${\ell }_1$ optimization
• Typical $l_1$-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices
• Statistical Mechanics Approach to Sparse Noise Denoising
• On Sparse Vector Recovery Performance in Structurally Orthogonal Matrices via LASSO
• Analysis of Sparse Representations Using Bi-Orthogonal Dictionaries

Cited by in corpus (15)

• Image Compressed Sensing Using Non-local Neural Network
• On the Performance of Turbo Signal Recovery with Partial DFT Sensing Matrices
• Asymptotic errors for convex penalized linear regression beyond Gaussian matrices
• Asymptotic Analysis of SU-MIMO Channels With Transmitter Noise and Mismatched Joint Decoding
• A statistical mechanics approach to de-biasing and uncertainty estimation in LASSO for random measurements
• Phase diagram of matrix compressed sensing
• SSFN -- Self Size-estimating Feed-forward Network with Low Complexity, Limited Need for Human Intervention, and Consistent Behaviour across Trials
• Self-Averaging Expectation Propagation
• Spectral Method for Phase Retrieval: an Expectation Propagation Perspective
• On Sparse Vector Recovery Performance in Structurally Orthogonal Matrices via LASSO
• Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery
• Matrix Infinitely Divisible Series: Tail Inequalities and Their Applications
• Towards Designing Optimal Sensing Matrices for Generalized Linear Inverse Problems
• Replica Analysis for Generalized Linear Regression with IID Row Prior
• Design and Analysis of a Greedy Pursuit for Distributed Compressed Sensing