×

Linearized alternating directions method for \(\ell_1\)-norm inequality constrained \(\ell_1\)-norm minimization. (English) Zbl 1295.65042

Summary: The \(\ell_1\)-regularization is popular in compressive sensing due to its ability to promote sparsity property. In the past few years, intensive research activities have been attracted to the algorithms for \(\ell_1\)-regularized least squares or its multifarious variations. In this study, we consider the \(\ell_1\)-norm minimization problems simultaneously with \(\ell_1\)-norm inequality constraints. The formulation of this problem is preferable when the measurement of a large and sparse signal is corrupted by an impulsive noise, in the mean time the noise level is given. This study proposes and investigates an inexact alternating direction method. At each iteration, as the closed-form solution of the resulting subproblem is not clear, we apply a linearized technique such that the closed-form solutions of the linearized subproblem can be easily derived. Global convergence of the proposed method is established under some appropriate assumptions. Numerical results, including comparisons with another algorithm are reported which demonstrate the superiority of the proposed algorithm. Finally, we extend the algorithm to solve \(\ell_2\)-norm constrained \(\ell_1\)-norm minimization problem, and show that the linearized technique can be avoided.

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
65K05 Numerical mathematical programming methods
90C05 Linear programming

Software:

PDCO; TwIST; FPC_AS; SPGL1
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 183-202 (2009) · Zbl 1175.94009
[2] Bioucas-Dias, J. M.; Figueiredo, M., A new TwIST: two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Trans. Image Process., 16, 2992-3004 (2007)
[3] Candès, E.; Tao, T., Near optimal signal recovery from random projections: universal encoding strategies, IEEE Trans. Inf. Theory, 52, 5406-5425 (2004) · Zbl 1309.94033
[4] Candès, E.; Romberg, J.; Tao, T., Stable signal recovery from imcomplete and inaccurate information, Commun. Pure Appl. Math., 59, 1207-1233 (2005)
[5] Candès, E.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 489-509 (2006) · Zbl 1231.94017
[6] Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM Rev., 43, 129-159 (2001) · Zbl 0979.94010
[7] Donoho, D. L., Compressed sensing, IEEE Trans. Inf. Theory, 52, 1289-1306 (2006) · Zbl 1288.94016
[8] Donoho, D. L., For most large underdetemined systems of linear equations, the minimal \(\ell_1\)-norm solution is also the sparsest solution, Commun. Pure Appl. Math., 59, 907-934 (2006) · Zbl 1105.90068
[9] Duchi, J.; Shalev-Shwartz, S.; Singer, Y.; Chandra, T., Efficient projection onto the \(\ell_1\)-ball for learning in high dimensions, (Proceedings of the 25th International Conference on Machine Learning. Proceedings of the 25th International Conference on Machine Learning, ICML 08 (2008)), 272-279
[10] Figueiredo, M.; Nowak, R.; Wright, S. J., Gradient projection for sparse reconstructin: application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Signal Process., 586-597 (2007)
[11] Hale, E. T.; Yin, W.; Zhang, Y., Fixed-point continuation for \(\ell_1\)-minimization: methodology and convergence, SIAM J. Optim., 19, 1107-1130 (2008) · Zbl 1180.65076
[12] Shalev-Shwartz, S.; Singer, Y., Efficient learning of label ranking by soft projections onto polyhedra, J. Mach. Learn. Res., 7, 1567-1599 (2006) · Zbl 1222.68302
[13] van den Berg, E.; Friedlander, M. P., Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 890-912 (2008) · Zbl 1193.49033
[14] Wen, Z.; Yin, W.; Goldfab, D.; Zhang, Y., A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation, SIAM J. Sci. Comput., 32, 1832-1857 (2010) · Zbl 1215.49039
[15] Wright, S. J.; Nowak, R.; Figueiredo, M., Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57, 2479-2493 (2009) · Zbl 1391.94442
[16] Xiao, Y.; Wu, S.-Y.; Li, D.-H., Splitting and linearizing augmented Lagrangian algorithm for subspace recovery from corrupted observations, Adv. Comput. Math., 38, 837-858 (2013) · Zbl 1269.65057
[17] Xiao, Y.; Zhu, H.; Wu, S.-Y., Primal and dual alternating direction algorithms for \(\ell_1-\ell_1\) norm minimization problems in compressive sensing, Comput. Optim. Appl., 54, 441-459 (2013) · Zbl 1269.90081
[18] Yang, J.; Yuan, X., Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization, Math. Comput., 82, 301-329 (2013) · Zbl 1263.90062
[19] Yang, J.; Zhang, Y., Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing, SIAM J. Sci. Comput., 33, 250-278 (2011) · Zbl 1256.65060
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.