Journal Home > Volume 22 , Issue 1
Tsinghua Science and Technology 2017, 22(1): 29-41 https://doi.org/10.1109/TST.2017.7830893
Open Access | Issue | Published: 26 January 2017

A Piecewise Linear Programming Algorithm for Sparse Signal Reconstruction

Show Author's Information Kuangyu Liu,  Xiangming Xi,  Zhiming Xu,  Shuning Wang( )
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.
Keywords:
compressed sensing, continuous piecewise linear programming, interior point method
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
Download citation
EndNote(RIS)
BibTeX

470

Views

8

Downloads

Citations

2

Crossref

N/A

WoS

1

Scopus

0

CSCD

Abstract Full text About this article

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.


menu
Abstract
Full text
Outline
About this article

A Piecewise Linear Programming Algorithm for Sparse Signal Reconstruction

Show Author's information Kuangyu Liu, Xiangming Xi, Zhiming Xu, Shuning Wang( )
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.

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 sensing, continuous piecewise linear programming, interior point method

References(43)

[1]
Donoho D. L., Compressed sensing, IEEE Transactions on Information Theory, vol. 52, no. 4, pp. 1289-1306, 2006.
DOI 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.
DOI 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.
DOI 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.
DOI
[5]
Baron D., Wakin M. B., Duarte M. F., Sarvotham S., and Baraniuk R. G., Distributed compressed sensing, arXiv: 0901.3403v1 [cs.IT], 2009.
DOI
[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.
DOI Google Scholar
[7]
Tsaig Y. and Donoho D. L., Extensions of compressed sensing, Signal Processing, vol. 86, no. 3, pp. 549-571, 2006.
DOI 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.
DOI
[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.
DOI
[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.
DOI
[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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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
DOI 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.
DOI
[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
DOI
[22]
Chartrand R. and Staneva V., Restricted isometry properties and nonconvex compressive sensing, Inverse Problems, vol. 24, no. 3, pp. 657-682, 2008.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI
[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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI Google Scholar
[34]
Blumensath T., Accelerated iterative hard thresholding, Signal Processing, vol. 92, no. 3, pp. 752-756, 2012.
DOI Google Scholar
[35]
Cormode G. and Muthukrishnan S., Combinatorial algorithms for compressed sensing, in Structural Information and Communication Complexity. Springer, 2006, pp. 280-294.
DOI
[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.
DOI
[38]
Ji S., Xue Y., and Carin L., Bayesian compressive sensing, IEEE Transactions on Signal Processing, vol. 56, no. 6, pp. 2346-2356, 2008.
DOI 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.
DOI
[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.
DOI 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.
DOI
[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.
DOI Google Scholar
[43]
Wright S. J., Primal-Dual Interior-Point Methods. Society for Industrial and Applied Mathematics, 1997.
DOI
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 08 November 2015
Revised: 08 January 2016
Accepted: 27 January 2016
Published: 26 January 2017
Issue date: February 2017

Copyright

© The author(s) 2017

Acknowledgements

This paper was jointly supported by the National Natural Science Foundation of China (Nos. 61473165 and 61134012) and the National Key Basic Research and Development (973) Program of China (No. 2012CB720505).

Rights and permissions

Return