Articles

First-order optimality condition of basis pursuit denoise problem

Expand
  • 1. School of Mathematics and Computational Science, Xiangtan University, Xiangtan 411105, Hunan Province, P. R. China;
    2. Hunan Key Laboratory for Computation and Simulation in Science and Engineering, Xiangtan University, Xiangtan 411105, Hunan Province, P. R. China;
    3. Department of Mathematics and Computational Science, College of Science, National University of Defense Technology, Changsha 410073, P. R. China

Received date: 2013-06-28

  Revised date: 2014-02-28

  Online published: 2014-10-01

Supported by

Project supported by the National Natural Science Foundation of China (No. 61271014), the Special- ized Research Fund for the Doctoral Program of Higher Education (No. 20124301110003), and the Graduated Students Innovation Fund of Hunan Province (No.CX2012B238)

Abstract

A new first-order optimality condition for the basis pursuit denoise (BPDN) problem is derived. This condition provides a new approach to choose the penalty param- eters adaptively for a fixed point iteration algorithm. Meanwhile, the result is extended to matrix completion which is a new field on the heel of the compressed sensing. The numerical experiments of sparse vector recovery and low-rank matrix completion show validity of the theoretic results.

Cite this article

Wei ZHU;Shi SHU;Li-zhi CHENG . First-order optimality condition of basis pursuit denoise problem[J]. Applied Mathematics and Mechanics, 2014 , 35(10) : 1345 -1352 . DOI: 10.1007/s10483-014-1860-9

References

[1] Johnson, B. R., Modisette, J. P., Nordlander, P., and Kinsey, J. L. Wavelet bases in eigenvalue problems in quantum mechanics. APS March Meeting Abstracts, 1, 1903-1903 (1996)
[2] Donoho, D. L. and Elad, M. On the stability of the basis pursuit in the presence of noise. Signal Processing, 86(3), 511-532 (2006)
[3] Chen, S. S., Donoho, D. L., and Saunders, M. A. Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing, 20(1), 33-61 (1998)
[4] Candès, E. J., Romberg, J. K., and Tao, T. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics, 59(8), 1207-1223 (2006)
[5] 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, 52(2), 489-509 (2006)
[6] Donoho, D. L. Compressed sensing. IEEE Transactions on Information Theory, 52(4), 1289-1306 (2006)
[7] 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, 1(1), 143-168 (2008)
[8] Cai, J. F., Osher, S., and Shen, Z. Linearized Bregman iterations for compressed sensing. Mathe- matics of Computation, 78(267), 1515-1536 (2009)
[9] Osher, S., Mao, Y., Dong, B., and Yin, W. Fast linearized Bregman iteration for compressive sensing and sparse denoising. Communications in Mathematical Sciences, 8(1), 93-111 (2010)
[10] Hale, E. T., Yin, W., and Zhang, Y. Fixed-point continuation for l1-minimization: methodology and convergence. SIAM Journal on Optimization, 19(3), 1107-1130 (2008)
[11] Candès, E. J. and Plan, Y. Matrix completion with noise. Proceedings of the IEEE, 98(6), 925-936 (2010)
[12] Candès, E. J. and Recht, B. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717-772 (2009)
[13] Candès, E. J. and Tao, T. The power of convex relaxation: near-optimal matrix completion. IEEE Transactions on Information Theory, 56(5), 2053-2080 (2010)
[14] Zhang, H., Cheng, L., and Zhu, W. Nuclear norm regularization with a low-rank constraint for matrix completion. Inverse Problems, 26(11), 115009 (2010)
[15] Zhang, H., Cheng, L. Z., and Zhu, W. A lower bound guaranteeing exact matrix completion via singular value thresholding algorithm. Applied and Computational Harmonic Analysis, 31(3), 454-459 (2011)
[16] Van Den Berg, E. and Friedlander, M. P. Probing the Pareto frontier for basis pursuit solutions. SIAM Journal on Scientific Computing, 31(2), 890-912 (2008)
[17] Van Den Berg, E. Convex Optimization for Generalized Sparse Recovery, Ph. D. dissertation, the University of British Columbia (2009)
[18] Bertsekas, D. P., Nedi′c, A., and Ozdaglar, A. E. Convex Analysis and Optimization, Athena Scientific, Belmont (2003)
[19] Cai, J. F., Candès, E. J., and Shen, Z. A singular value thresholding algorithm for matrix com- pletion. SIAM Journal on Optimization, 20(4), 1956-1982 (2010)
[20] Ma, S., Goldfarb, D., and Chen, L. Fixed point and Bregman iterative methods for matrix rank minimization. Mathematical Programming, 128(1-2), 321-353 (2011)
[21] Zhang, H. and Cheng, L. Z. Projected Landweber iteration for matrix completion. Journal of Computational and Applied Mathematics, 235(3), 593-601 (2010)
[22] Hale, E. T., Yin, W. T., and Zhang, Y. A Fixed-Point Continuation Method for l1-Regularized Minimization with Applications to Compressed Sensing, CAAM Technical Report, TR07-07, Rice University, Texas (2007)
Outlines

/

APS Journals | CSTAM Journals | AMS Journals | EMS Journals | ASME Journals