On Sparse Vector Recovery Performance in Structurally Orthogonal Matrices via LASSO

Abstract

In this paper, we consider a compressed sensing problem of reconstructing a sparse signal from an undersampled set of noisy linear measurements. The regularized least squares or least absolute shrinkage and selection operator (LASSO) formulation is used for signal estimation. The measurement matrix is assumed to be constructed by concatenating several randomly orthogonal bases, referred to as structurally orthogonal matrices. Such measurement matrix is highly relevant to large-scale compressive sensing applications because it facilitates fast computation and also supports parallel processing. Using the replica method from statistical physics, we derive the mean-squared-error (MSE) formula of reconstruction over the structurally orthogonal matrix in the large-system regime. Extensive numerical experiments are provided to verify the analytical result. We then use the analytical result to study the MSE behaviors of LASSO over the structurally orthogonal matrix, with a particular focus on performance comparisons to matrices with independent and identically distributed (i.i.d.) Gaussian entries. We demonstrate that the structurally orthogonal matrices are at least as well performed as their i.i.d. Gaussian counterparts, and therefore the use of structurally orthogonal matrices is highly motivated in practical applications.

39 pages, 8 figures, 4 tables, minor corrections

References in corpus (9)

• Message Passing Algorithms for 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
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• Turbo Compressed Sensing with Partial DFT Sensing Matrix
• Analysis of CDMA systems that are characterized by eigenvalue spectrum
• Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing
• On an Achievable Rate of Large Rayleigh Block-Fading MIMO Channels with No CSI
• Optimal incorporation of sparsity information by weighted ${\ell }_1$ optimization

Cited by in corpus (2)

• On the Performance of Turbo Signal Recovery with Partial DFT Sensing Matrices
• Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing