×

First-order optimality condition of basis pursuit denoise problem. (English) Zbl 1298.49039

Summary: 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 parameters 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.

MSC:

49K35 Optimality conditions for minimax problems
90C06 Large-scale problems in mathematical programming
90C22 Semidefinite programming
90C25 Convex programming

Software:

SPGL1; PDCO
PDFBibTeX XMLCite
Full Text: DOI

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) · Zbl 0866.60021
[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) · Zbl 1163.94329 · doi:10.1016/j.sigpro.2005.05.027
[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) · Zbl 0919.94002 · doi:10.1137/S1064827596304010
[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) · Zbl 1098.94009 · doi:10.1002/cpa.20124
[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) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[6] Donoho, D. L. Compressed sensing. IEEE Transactions on Information Theory, 52(4), 1289-1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[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) · Zbl 1203.90153 · doi:10.1137/070703983
[8] Cai, J. F., Osher, S., and Shen, Z. Linearized Bregman iterations for compressed sensing. Mathematics of Computation, 78(267), 1515-1536 (2009) · Zbl 1198.65102 · doi:10.1090/S0025-5718-08-02189-3
[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) · Zbl 1190.49040 · doi:10.4310/CMS.2010.v8.n1.a6
[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) · Zbl 1180.65076 · doi:10.1137/070698920
[11] Candès, E. J. and Plan, Y. Matrix completion with noise. Proceedings of the IEEE, 98(6), 925-936 (2010) · doi:10.1109/JPROC.2009.2035722
[12] Candès, E. J. and Recht, B. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717-772 (2009) · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5
[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) · Zbl 1366.15021 · doi:10.1109/TIT.2010.2044061
[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) · Zbl 1206.65140 · doi:10.1088/0266-5611/26/11/115009
[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) · Zbl 1401.90165 · doi:10.1016/j.acha.2011.04.004
[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) · Zbl 1193.49033 · doi:10.1137/080714488
[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ć, A., and Ozdaglar, A. E. Convex Analysis and Optimization, Athena Scientific, Belmont (2003) · Zbl 1140.90001
[19] Cai, J. F., Candès, E. J., and Shen, Z. A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 20(4), 1956-1982 (2010) · Zbl 1201.90155 · doi:10.1137/080738970
[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) · Zbl 1221.65146 · doi:10.1007/s10107-009-0306-5
[21] Zhang, H. and Cheng, L. Z. Projected Landweber iteration for matrix completion. Journal of Computational and Applied Mathematics, 235(3), 593-601 (2010) · Zbl 1225.65049 · doi:10.1016/j.cam.2010.06.010
[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) · Zbl 1206.65232
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.