High-Quality Recovery of Non-Sparse Signals from Compressed Sensing — Beyond l1 Norm Minimization —


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A   No.9   pp.1880-1887
Publication Date: 2015/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.1880
Type of Manuscript: Special Section PAPER (Special Section on Signal Processing for Sensing and Diagnosis)
sparse signals,  compressible signals,  compressed sensing,  l1-norm minimization,  lasso,  

Full Text: PDF(1.6MB)>>
Buy this Article

We propose a novel algorithm for the recovery of non-sparse, but compressible signals from linear undersampled measurements. The algorithm proposed in this paper consists of two steps. The first step recovers the signal by the l1-norm minimization. Then, the second step decomposes the l1 reconstruction into major and minor components. By using the major components, measurements for the minor components of the target signal are estimated. The minor components are further estimated using the estimated measurements exploiting a maximum a posterior (MAP) estimation, which leads to a ridge regression with the regularization parameter determined using the error bound for the estimated measurements. After a slight modification to the major components, the final estimate is obtained by combining the two estimates. Computational cost of the proposed algorithm is mostly the same as the l1-nom minimization. Simulation results for one-dimensional computer generated signals show that the proposed algorithm gives 11.8% better results on average than the l1-norm minimization and the lasso estimator. Simulations using standard images also show that the proposed algorithm outperforms those conventional methods.