压缩感知和稀疏优化简介

摘要/Abstract

摘要： 介绍压缩感知和稀疏优化的基本概念、理论基础和算法概要. 压缩感知利用原始信号的稀疏性，从远少于信号元素个数的测量出发，通过求解稀疏优化问题来恢复完整的原始稀疏信号. 通过一个小例子展示这一过程，并以此说明压缩感知和稀疏优化的基本理念. 接着简要介绍用以保证l₁凸优化恢复稀疏信号的零空间性质和RIP条件. 最后介绍求解稀疏优化的几个经典算法.

关键词: 压缩感知, 稀疏优化, 零空间性质, 受限正交条件, 紧缩算子, 线性化近似点算法, 分裂Bregman方法和交替方向增广拉格朗日函数法, Bregman方法和增广拉格朗日函数法

Abstract: We briefly introduce the basic principle and theory of compressive sensing and sparse optimization. Compressive sensing is a new paradigm of signal acquisition, which senses a sparse signal by taking a set of incomplete measurements and recovers the signal by solving an optimization problem. This article first illustrates the compressive sensing paradigm through a synthetic example. Then we describe two sufficient conditions, the null space property and restricted isometry principle, for l₁ convex minimization to give the sparsest solution. Finally, we summarize a few typical algorithms for solving the optimization models arising from compressive sensing.

Key words: compressive sensing, sparse optimization, null space property, RIP,shrinkage, prox-linear algorithms, split Bregman/alternating direction augmented Lagragian method, Bregman/augmented Lagragian method

中图分类号:

文再文,印卧涛,刘歆,张寅. 压缩感知和稀疏优化简介[J]. 运筹学学报, 2012, 16(3): 49-64.

WEN Zaiwen YIN Wotao LIU Xin ZHANG Yin. Introduction to compressive sensing and sparse optimization[J]. Operations Research Transactions, 2012, 16(3): 49-64.

参考文献

Cand{\`{e}}s E, Tao T. Near optimal signal recovery from random projections: universal encoding strategies [J]. IEEE Transactions on Information Theory, 2006, 52(1): 5406-5425.
Donoho D. Compressed sensing [J]. IEEE Transactions on Information Theory, 2006, 52, 1289-1306.
Natarajan B K. Sparse approximate solutions to linear systems [J]. SIAM Journal on Computing, 1995, 24: 227-234.
Cohen A, Dahmen W, DeVore R A. Compressed sensing and best k-term approximation [J]. Journal of the American Mathematical Society, 2009, 22: 211-231.
Rudelson M, Vershynin R. Geometric approach to error correcting codes and reconstruction of signals [J]. International Mathematical Research Notices, 2005, 64: 4019-4041.
Rudelson M, Vershynin R. Geometric approach to error correcting codes and reconstruction of signals [J]. International Mathematical Research Notices, 2005, 64: 4019-4041.
Donoho D, Huo X. Uncertainty principles and ideal atomic decompositions [J]. IEEE Transactions on Information Theory, 2001, 47: 2845-2862.
Gribonval R, Nielsen M. Sparse representations in unions of bases [J]. IEEE Transactions on Information Theory, 2003, 49(12): 3320-3325.
Zhang Y. A simple proof for recoverability of 1-minimization: go over or under? [R]. Rice University CAAM Technical Report TR05-09, 2005.
Kashin B S. Diameters of certain finite-dimensional sets in classes of smooth functions [J]. Izv. Akad. Nauk SSSR, Ser. Mat., 1977, 41(2): 334-351.
Garnaev A, Gluskin E D. The widths of a Euclidean ball [J]. Dokl. Akad. Nauk SSSR, 1984, 277(5): 1048-1052.
Milman V D, Schechtman G. Asymptotic theory of finite dimensional normed spaces, with an appendix by M. Gromov [M]// Lecture Notes in Mathematics, Berlin: Springer, 2001.
Cand{\`{e}}s E, Tao T. Decoding by linear programming [J]. IEEE Transactions on Information Theory, 2005, 51: 4203-4215.
Foucart S, Lai M J. Sparsest solutions of underdetermined linear systems via lq-minimization for 0<q\le 1 [J]. Applied and Computational Harmonic Analysis, 2009, 26(3): 395-407.
Foucart S. A note on guaranteed sparse recovery via l1-minimization [J]. Applied and Computational Harmonic Analysis, 2010, 29(1): 97-103.
Cai T T, Wang L, Xu G. Shifting inequality and recovery of sparse signals [J]. IEEE Transactions on Signal Processing, 2010, 58(3): 1300-1308.
Mo Q, Li S. New bounds on the restricted isometry constant δ_2k [J]. Applied and Computational Harmonic Analysis, 2011, 31(3): 460-468.
Zhang Y. Theory of compressive sensing via l1-minimization: a non-{RIP} analysis and extensions [R]. Rice University, CAAM Technical Report TR08-11,

2008.
Vavasis S A. Derivation of compressive sensing theorems from the spherical section property [EB/OL] www.student.math.uwaterloo.ca/~co769/simplif.pdf. 2009.
Darbon J, Sigelle M. Image restoration with discrete constrained total variation, {Part I}: fast and exact optimization [J]. Journal of Mathematical Imaging and Vision, 2006, 26(3): 261-276.
Goldfarb D, Yin W. Parametric maximum flow algorithms for fast total variation minimization [J]. SIAM Journal on Scientific Computing, 2009, 31(5): 3712-3743.
Chan T F, Zhou H M, Chan R H. Continuation method for total variation denoising problems [J]. Advanced Signal Processing Algorithms, 1995, 2563(1): 314-325.
Chambolle A. An algorithm for total variation minimization and applications [J]. Journal of Mathematical Imaging and Vision, 2004, 20: 89-97.
Wohlberg B, Rodriguez P. An Iteratively Reweighted Norm Algorithm for Minimization of Total Variation Functionals [J]. Signal Processing Letters,IEEE, 2007, 14(12): 948-951.
Figueiredo M, Nowak R. An {EM} algorithm for wavelet-based image restoration [J]. IEEE Transactions on Image Processing, 2003, 12: 906-916.
De Mol C, Defrise M. A Note on Wavelet-based Inversion Algorithms [J]. Contemporary Mathematics, 2002, 313: 85-96.
Bect J, Blanc-Feraud L, Aubert G, et al. A l1-unified variational framework for image restoration [J]. European Conference on Computer Vision, Prague, Lecture Notes in Computer Sciences 3024, 2004: 1-13.
Hale E T, Yin W, Zhang Y. Fixed-Point Continuation for l1-Minimization: Methodology and Convergence [J]. SIAM Journal on Optimization, 2008, 19(3): 1107-1130.
Ma S Q, Goldfarb D, Chen L F. Fixed point and {B}regman iterative methods for matrix rank minimization [J]. Math. Program., 2011, 128(1-2): 321-353.
Bregman L. The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming [J]. USSR Computational Mathematics and Mathematical Physics, 1967, 7: 200-217.
Candes E, Wakin M B, Boyd S P. Enhancing sparsity by reweighted l1 minimization [J]. Journal of Fourier Analysis and Applications, 2008, 14(5): 877-905.
Chartrand R, Yin W. Iteratively Reweighted Algorithms for Compressive Sensing [C]//International Conference on Acoustics, Speech, and Signal Processing, 2008: 3869-3872.
Daubechies I, DeVore R, Fornasier M, et al. Iteratively reweighted least squares minimization for sparse recovery [J]. Communications on Pure and Applied Mathematics, 2010, 63(1): 1-38.
Mohan K, Fazel M. Iterative reweighted least squares for matrix rank minimization [C]//48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2010: 653-661.
Fornasier M, Rauhut H, Ward R. Low-rank Matrix Recovery via Iteratively Reweighted Least Squares Minimization [J]. SIAM Journal on Optimization, 2011, 21: 1614-1640.
Lai M J, Xu Y, Yin W. On Unconstrained Nonconvex Minimizatino for Sparse Vector and Low-Rank Matrix Recovery [J]. Submitted to SIAM Journal on Numerical Analysis, 2011.
Chartrand R, Staneva V. Restricted isometry properties and nonconvex compressive sensing [J]. Inverse Problems, 2008, 24: 1-14.
Lai M J, Liu L Y. A New Estimate of Restricted Isometry Constants for Sparse Solutions [J]. Applied and Computational Harmonic Analysis, 2011, 30: 402-406.
Sun Q. Recovery of sparsest signals via l_q-minimization [J]. Applied and Computational Harmonic Analysis, 2012, 32(3): 329-341.
Ge D, Jiang X, Ye Y. A note on complexity of L_p minimization [J]. Mathematical Programming, 2011, 129: 285-299.
Tropp J. Gilbert A. Signal recovery from partial information via orthogonal matching pursuit [J]. IEEE Transactions on Information Theory, 2007, 53(12): 4655-4666.
Donoho D, Tsaig Y, Drori I, et al. Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit [R]. Stanford Technical Report, 2006.
Needell D, Vershynin R. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit [J]. Selected Topics in Signal Processing, IEEE Journal of, 2010, 4(2): 310-316.
Dai W, Milenkovic O. Subspace pursuit for compressive sensing reconstruction [J]. IEEE Transactions on Information Theory, 2009, 55(5): 2230-2249.
Needell D, Tropp J A. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples [J]. Applied and Computational Harmonic Analysis, 2008, 26(3): 301-321.
石光明, 刘丹华, 高大化, 等. 电子学报压缩感知理论及其研究进展[J]. 电子学报, 2009, 37(5): 1070-1081.
许志强. 压缩感 [J]. 中国科学, 已接收.
Yang J F, Zhang Y. Alternating direction algorithms for l_1-problems in compressive sensing [J]. SIAM Journal on Scientific Computing, 2011, 33(1): 250-278.