On Sparse Vector Recovery Performance in Structurally Orthogonal   Matrices via LASSO
  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. 
Chao-Kai Wen, Jun Zhang, Kai-Kit Wong, Jung-Chieh Chen, and Chau Yuen
cs.IT math.IT