Home Tsinghua Science and Technology Article
PDF (1.4 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Open Access

A Piecewise Linear Programming Algorithm for Sparse Signal Reconstruction

Department of Automation, Tsinghua National Laboratory for Information Science and Technology (TNList), Tsinghua University, Beijing 100084, China.
College of Science, Air Force Engineering University, Xi’an 710051
Department of Automation, Tsinghua University, Beijing 100084, China.
Show Author Information

Abstract

In order to recover a signal from its compressive measurements, the compressed sensing theory seeks the sparsest signal that agrees with the measurements, which is actually an l0 norm minimization problem. In this paper, we equivalently transform the l0 norm minimization into a concave continuous piecewise linear programming, and propose an optimization algorithm based on a modified interior point method. Numerical experiments demonstrate that our algorithm improves the sufficient number of measurements, relaxes the restrictions of the sensing matrix to some extent, and performs robustly in the noisy scenarios.

Keywords

compressed sensingcontinuous piecewise linear programminginterior point method

References

[1]
Donoho D. L., Compressed sensing, IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289-1306, 2006.
Crossref Google Scholar
[2]
Candès E. J., Romberg J., and Tao T., Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory, vol. 52, no. 2, pp. 489-509, 2006.
Crossref Google Scholar
[3]
Candès E. J. and Tao T., Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Transactions on Information Theory, vol. 52, no. 12, pp. 5406-5425, 2006.
Crossref Google Scholar
[4]
Bajwa W., Haupt J., Sayeed A., and Nowak R., Compressive wireless sensing, in Proceedings of the 5th International Conference on Information Processing in Sensor Networks, 2006, pp. 134-142.
Crossref
[5]
Baron D., Wakin M. B., Duarte M. F., Sarvotham S., and Baraniuk R. G., Distributed compressed sensing, arXiv: 0901.3403v1 [cs.IT], 2009.
Crossref
[6]
Lustig M., Donoho D., and Pauly J. M., Sparse MRI: The application of compressed sensing for rapid MR imaging, Magnetic Resonance in Medicine, vol. 58, no. 6, pp. 1182-1195, 2007.
Crossref Google Scholar
[7]
Tsaig Y. and Donoho D. L., Extensions of compressed sensing, Signal Processing, vol. 86, no. 3, pp. 549-571, 2006.
Crossref Google Scholar
[8]
Kirolos S., Laska J., Wakin M., Duarte M., Baron D., Ragheb T., Massoud Y., and Baraniuk R., Analog-to-information conversion via random demodulation, in 2006 IEEE Dallas/CAS Workshop on Design, Applications, Integration and Software, 2006, pp. 71-74.
Crossref
[9]
Laska J., Kirolos S., Massoud Y., Baraniuk R., Gilbert A., Iwen M., and Strauss M., Random sampling for analog-to-information conversion of wideband signals, in 2006 IEEE Dallas/CAS Workshop on Design, Applications, Integration and Software, 2006, pp. 119-122.
Crossref
[10]
Takhar D., Laska J. N., Wakin M. B., Duarte M. F., Baron D., Sarvotham S., Kelly K. F., and Baraniuk R. G., A new compressive imaging camera architecture using optical-domain compression, in Electronic Imaging 2006, International Society for Optics and Photonics, 2006, pp. 43-52.
Crossref
[11]
Kim S.-J., Koh K., Lustig M., Boyd S., and Gorinevsky D., An interior-point method for large-scale l1-regularized least squares, IEEE Journal of Selected Topics in Signal Processing, vol. 1, no. 4, pp. 606-617, 2007.
Crossref Google Scholar
[12]
Figueiredo M. A., Nowak R. D., and Wright S. J., Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems, IEEE Journal of Selected Topics in Signal Processing, vol. 1, no. 4, pp. 586-597, 2007.
Crossref Google Scholar
[13]
Osher S., Burger M., Goldfarb D., Xu J., and Yin W., An iterative regularization method for total variation-based image restoration, Multiscale Modeling & Simulation, vol. 4, no. 2, pp. 460-489, 2005.
Crossref Google Scholar
[14]
Yin W., Osher S., Goldfarb D., and Darbon J., Bregman iterative algorithms for l1-minimization with applications to compressed sensing, SIAM Journal on Imaging Sciences, vol. 1, no. 1, pp. 143-168, 2008.
Crossref Google Scholar
[15]
Osher S., Mao Y., Dong B., and Yin W., Fast linearized bregman iteration for compressive sensing and sparse denoising, Communications in Mathematical Sciences, vol. 8, no. 1, pp. 93-111, 2010.
Crossref Google Scholar
[16]
Wen Z., Yin W., Goldfarb D., and Zhang Y., A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation, SIAM Journal on Scientific Computing, vol. 32, no. 4, pp. 1832-1857, 2010.
Crossref Google Scholar
[17]
Candès E. J., Wakin M. B., and Boyd S. P., Enhancing sparsity by reweighted l1 minimization, Journal of Fourier Analysis and Applications, vol. 14, nos. 5&6, pp. 877-905, 2008.
Crossref Google Scholar
[18]
Wang Y. and Yin W., Sparse signal reconstruction via iterative support detection, SIAM Journal on Imaging Sciences, vol. 3, no. 3, pp. 462-491, 2010.
Crossref Google Scholar
[19]
Chartrand R., Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Processing Letters, vol. 14, no. 10, pp. 707-710, 2007
Crossref Google Scholar
[20]
Chartrand R. and Yin W., Iteratively reweighted algorithms for compressive sensing, in IEEE International Conference on Acoustics, Speech and Signal Processing, 2008, 2008, pp. 3869-3872.
Crossref
[21]
Saab R., Chartrand R., and Yilmaz Ö., Stable sparse approximations via nonconvex optimization, in IEEE International Conference on Acoustics, Speech and Signal Processing, 2008, 2008, pp. 3885-3888
Crossref
[22]
Chartrand R. and Staneva V., Restricted isometry properties and nonconvex compressive sensing, Inverse Problems, vol. 24, no. 3, pp. 657-682, 2008.
Crossref Google Scholar
[23]
Shen Y. and Li S., Restricted p-isometry property and its application for nonconvex compressive sensing, Advances in Computational Mathematics, vol. 37, no. 3, pp. 441-452, 2012.
Crossref Google Scholar
[24]
Wipf D. and Nagarajan S., Iterative reweighted and methods for finding sparse solutions, IEEE Journal of Selected Topics in Signal Processing, vol. 4, no. 2, pp. 317-329, 2010.
Crossref Google Scholar
[25]
Fang J., Li J., Shen Y., Li H., and Li S., Super-resolution compressed sensing: An iterative reweighted algorithm for joint parameter learning and sparse signal recovery, IEEE Signal Processing Letters, vol. 21, no. 6, pp. 761-765, 2014.
Crossref Google Scholar
[26]
Shen Y., Fang J., and Li H., Exact reconstruction analysis of log-sum minimization for compressed sensing, IEEE Signal Processing Letters, vol. 20, no. 12, pp. 1223-1226, 2013.
Crossref Google Scholar
[27]
Gilbert A. C., Guha S., Indyk P., Muthukrishnan S., and Strauss M., Near-optimal sparse fourier representations via sampling, in Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, 2002, pp. 152-161.
Crossref
[28]
Tropp J. and Gilbert A. C., Signal recovery from random measurements via orthogonal matching pursuit, IEEE Transactions on Information Theory, vol. 53, no. 12, pp. 4655-4666, 2007.
Crossref Google Scholar
[29]
Donoho D. L., Tsaig Y., Drori I., and Starck J.-L., Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit, IEEE Transactions on Information Theory, vol. 58, no. 2, pp. 1094-1121, 2012.
Crossref Google Scholar
[30]
Needell D. and Vershynin R., Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, Foundations of Computational Mathematics, vol. 9, no. 3, pp. 317-334, 2009.
Crossref Google Scholar
[31]
Needell D. and Tropp J. A., Cosamp: Iterative signal recovery from incomplete and inaccurate samples, Applied and Computational Harmonic Analysis, vol. 26, no. 3, pp. 301-321, 2009.
Crossref Google Scholar
[32]
Dai W. and Milenkovic O., Subspace pursuit for compressive sensing signal reconstruction, IEEE Transactions on Information Theory, vol. 55, no. 5, pp. 2230-2249, 2009.
Crossref Google Scholar
[33]
Blumensath T. and Davies M. E., Iterative hard thresholding for compressed sensing, Applied and Computational Harmonic Analysis, vol. 27, no. 3, pp. 265-274, 2009.
Crossref Google Scholar
[34]
Blumensath T., Accelerated iterative hard thresholding, Signal Processing, vol. 92, no. 3, pp. 752-756, 2012.
Crossref Google Scholar
[35]
Cormode G. and Muthukrishnan S., Combinatorial algorithms for compressed sensing, in Structural Information and Communication Complexity. Springer, 2006, pp. 280-294.
Crossref
[36]
Gilbert A. C., Strauss M. J., Tropp J. A., and Vershynin R., Algorithmic linear dimension reduction in the l1 norm for sparse vectors, in 44th Annual Allerton Conference on Communication, Control, and Computing 2006, 2006.
[37]
Gilbert A. C., Strauss M. J., Tropp J. A., and Vershynin R., One sketch for all: Fast algorithms for compressed sensing, in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, 2007, pp. 237-246.
Crossref
[38]
Ji S., Xue Y., and Carin L., Bayesian compressive sensing, IEEE Transactions on Signal Processing, vol. 56, no. 6, pp. 2346-2356, 2008.
Crossref Google Scholar
[39]
Seeger M. W. and Nickisch H., Compressed sensing and Bayesian experimental design, in Proceedings of the 25th International Conference on Machine Learning, 2008, pp. 912-919.
Crossref
[40]
Baron D., Sarvotham S., and Baraniuk R. G., Bayesian compressive sensing via belief propagation, IEEE Transactions on Signal Processing, vol. 58, no. 1, pp. 269-280, 2010.
Crossref Google Scholar
[41]
Schniter P., Potter L. C., and Ziniel J., Fast Bayesian matching pursuit, in Information Theory and Applications Workshop, 2008, 2008, pp. 326-333.
Crossref
[42]
Huang X., Liu Y., Shi L., Van Huffel S., and Suykens J. A., Two-level l1 minimization for compressed sensing, Signal Processing, vol. 108, pp. 459-475, 2015.
Crossref Google Scholar
[43]
Wright S. J., Primal-Dual Interior-Point Methods. Society for Industrial and Applied Mathematics, 1997.
Crossref
Tsinghua Science and Technology
Volume 22 Issue 1,
February 2017
Pages 29-41
DOI: 10.1109/TST.2017.7830893
Cite this article:
Liu K, Xi X, Xu Z, et al. A Piecewise Linear Programming Algorithm for Sparse Signal Reconstruction. Tsinghua Science and Technology, 2017, 22(1): 29-41. https://doi.org/10.1109/TST.2017.7830893
Metrics & Citations  
Article History
Copyright
Return