research-article

Improved Iteratively Reweighted Least Squares for Unconstrained Smoothed $\ell_q$ Minimization

Authors:

Wotao YinAuthors Info & Claims

SIAM Journal on Numerical Analysis, Volume 51, Issue 2

Pages 927 - 957

https://doi.org/10.1137/110840364

Published: 01 January 2013 Publication History

Abstract

In this paper, we first study $\ell_q$ minimization and its associated iterative reweighted algorithm for recovering sparse vectors. Unlike most existing work, we focus on unconstrained $\ell_q$ minimization, for which we show a few advantages on noisy measurements and/or approximately sparse vectors. Inspired by the results in [Daubechies et al., Comm. Pure Appl. Math., 63 (2010), pp. 1--38] for constrained $\ell_q$ minimization, we start with a preliminary yet novel analysis for unconstrained $\ell_q$ minimization, which includes convergence, error bound, and local convergence behavior. Then, the algorithm and analysis are extended to the recovery of low-rank matrices. The algorithms for both vector and matrix recovery have been compared to some state-of-the-art algorithms and show superior performance on recovering sparse vectors and low-rank matrices.

References

[1]

M. S. Asif and J. Romberg, Dantzig selector homotopy with dynamic measurements, Proc. SPIE Computational Imaging VII, 7246 (2009).

[2]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183--202.

[3]

J. F. Cai, E. J. Candès, and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20 (2010) pp. 1956--1982.

[4]

E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009) pp. 717--772.

[5]

E. J. Candès, J. Romberg, and S. Becker, $l_1$-magic, http://users.ece.gatech.edu/$\sim$justin/l1magic (2007).

[6]

E. J. Candès and T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Trans. Inform. Theory, 56 (2010), pp. 2053--2080.

[7]

E. J. Candès, M. B. Wakin, and S. P. Boyd, Enhancing sparsity by reweighted $\ell_1$ minimization, J. Fourier Anal. Appl., 14 (2008), pp. 877--905.

[8]

R. Chartrand and V. Staneva, Restricted isometry properties and nonconvex compressive sensing, Inverse Problems, 24 (2008), 035020.

[9]

R. Chartrand and W. Yin, Iteratively reweighted algorithms for compressive sensing, \newblock in Proceedings of International Conference on Acoustics, Speech, and Signal Processing (ICASSP'08), 2008, pp. 3869--3872.

[10]

I. Daubechies, R. DeVore, M. Fornasier, and C. S. Güntük, Iteratively reweighted least squares minimization for sparse recovery, \newblock Commun. Pure Appl. Math., 63 (2010), pp. 1--38.

[11]

L. Eldén, Matrix Methods in Data Mining and Pattern Recognition: Fundamentals of Algorithms, SIAM, Philadelphia, 2007.

[12]

M. Fazel, H. Hindi, and S. P. Boyd, A rank minimization heuristic with application to minimum order system approximation, in Proceedings of the American Control Conference, vol. 6, IEEE, Arlington, VA, 2001, pp. 4734--4739.

[13]

M. Fornasier, H. Rauhut, and R. Ward, Low-rank matrix recovery via iteratively reweighted least squares minimization, SIAM J. Optim., 21 (2011) pp. 1614--1640.

[14]

S. Foucart, Sparse recovery algorithms: Sufficient conditions in terms of restricted isometry constants, in Proceedings of the 13th International Conference on Approximation Theory, 2010.

[15]

S. Foucart and M. J. Lai, Sparsest solutions of underdetermined linear systems via $\ell_q$-minimization for $0<q\le 1$, Appl. Comput. Harmon. Anal., 26 (2009), 395--407.

[16]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2 (1976), pp. 17--40.

[17]

D. Ge, X. Jiang, and Y. Ye, A Note on Complexity of $L_p$ Minimization, Technical report, Stanford University, Stanford, CA, 2010.

[18]

E. T. Hale, W. Yin, and Y. Zhang, Fixed-point continuation for $\ell_1 $-minimization: Methodology and convergence, SIAM J. Optim., 19 (2008), pp. 1107--1130.

[19]

G. Hardy, J. Littlewood, and G. Polya, Inequalities. Cambridge University Press, Cambridge, UK, 1952.

[20]

R. H. Keshavan, A. Montanari, and S. Oh, Matrix completion from a few entries, IEEE Trans. Inform. Theory, 56 (2010), pp. 2980--2998.

[21]

M. J. Lai and J. Wang, An unconstrained $\ell_q $ minimization with $0 < q \leq 1 $ for sparse solution of underdetermined linear systems, SIAM J. Optim., 21 (2011), pp. 82--101.

[22]

N. Linial, E. London, and Y. Rabinovich, The geometry of graphs and some of its algorithmic applications. Combinatorica, 15 (1995), pp. 215--245.

[23]

Z. Liu and L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 1235--1256.

[24]

S. Ma, D. Goldfarb, and L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Math. Programming (2011), pp. 321--353.

[25]

A. W. Marshall, I. Olkin, and B. Arnold, Inequalities: Theory of Majorization and Its Applications, Springer, New York, 2005.

[26]

K. Mohan and M. Fazel, Iterative reweighted least squares for matrix rank minimization, in 48th Annual Allerton Conference on Communication, Control, and Computing, 2010, pp. 653--661.

[27]

T. Morita and T. Kanade, A sequential factorization method for recovering shape and motion from image streams, IEEE Trans. Pattern Analysis Machine Intelligence, 19 (1997) pp. 858--867.

[28]

S. Osher, Y. Mao, B. Dong, and W. Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci., 8 (2010), pp. 93--111.

[29]

B. Recht, M. Fazel, and P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52 (2010), pp. 471--501.

[30]

J. D. M. Rennie and N. Srebro, Fast maximum margin matrix factorization for collaborative prediction, in Proceedings of the 22nd International Conference on Machine Learning, 2005, pp. 713--719.

[31]

Q. Y. Sun, Recovery of sparsest signals via $\ell_q$-minimization, Appl. Comput. Harmon. Anal., 32 (2012), pp. 329--341.

[32]

K. C. Toh and S. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pacific J. Optim., 6 (2010) pp. 615--640.

[33]

C. Tomasi and T. Kanade, Shape and motion from image streams under orthography: A factorization method, Int. J. Comput. Vision, 9 (1992) pp. 137--154.

[34]

Z. Wen, W. Yin, and Y. Zhang, Solving a Low-Rank Factorization Model for Matrix Completion by a Nonlinear Successive Over-Relaxation Algorithm, Math. Programming Comput., 4 (2012), pp. 333--361.

[35]

J. Yang and X. Yuan, An inexact alternating direction method for trace norm regularized least squares problem, Optimization Online, 2010.

[36]

W. Yin, S. Osher, D. Goldfarb, and J. Darbon, Bregman iterative algorithms for $\ell_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1 (2008), pp. 143--168.

Cited By

Abergel RBouaziz ONuel G(2024)A review on the Adaptive-Ridge Algorithm with several extensionsStatistics and Computing10.1007/s11222-024-10440-634:4Online publication date: 25-Jun-2024
https://dl.acm.org/doi/10.1007/s11222-024-10440-6
Ke CShin SLou YAhn M(2024)A Generalized Formulation for Group Selection via ADMMJournal of Scientific Computing10.1007/s10915-024-02571-9100:1Online publication date: 31-May-2024
https://dl.acm.org/doi/10.1007/s10915-024-02571-9
Li XYuan JTai XLiu S(2024)Efficient Convex Optimization for Non-convex Non-smooth Image RestorationJournal of Scientific Computing10.1007/s10915-024-02504-699:2Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10915-024-02504-6
Show More Cited By

Recommendations

Low-rank Matrix Recovery via Iteratively Reweighted Least Squares Minimization

We present and analyze an efficient implementation of an iteratively reweighted least squares algorithm for recovering a matrix from a small number of linear measurements. The algorithm is designed for the simultaneous promotion of both a minimal ...
Accelerated reweighted nuclear norm minimization algorithm for low rank matrix recovery

In this paper we propose an accelerated reweighted nuclear norm minimization algorithm to recover a low rank matrix. Our approach differs from other iterative reweighted algorithms, as we design an accelerated procedure which makes the objective ...
An Unconstrained $\ell_q$ Minimization with $0q\leq1$ for Sparse Solution of Underdetermined Linear Systems

We study an unconstrained version of the $\ell_q$ minimization for the sparse solution of underdetermined linear systems for $0<q\leq1$. Although the minimization is nonconvex when $q<1$, we introduce a regularization and develop an iterative algorithm. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Numerical Analysis

SIAM Journal on Numerical Analysis Volume 51, Issue 2

2013

605 pages

ISSN:0036-1429

DOI:10.1137/sjnaam.51.2

Issue’s Table of Contents

© 2013, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2013

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Abergel RBouaziz ONuel G(2024)A review on the Adaptive-Ridge Algorithm with several extensionsStatistics and Computing10.1007/s11222-024-10440-634:4Online publication date: 25-Jun-2024
https://dl.acm.org/doi/10.1007/s11222-024-10440-6
Ke CShin SLou YAhn M(2024)A Generalized Formulation for Group Selection via ADMMJournal of Scientific Computing10.1007/s10915-024-02571-9100:1Online publication date: 31-May-2024
https://dl.acm.org/doi/10.1007/s10915-024-02571-9
Li XYuan JTai XLiu S(2024)Efficient Convex Optimization for Non-convex Non-smooth Image RestorationJournal of Scientific Computing10.1007/s10915-024-02504-699:2Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10915-024-02504-6
Zhang XPeng DSu Y(2024)A singular value shrinkage thresholding algorithm for folded concave penalized low-rank matrix optimization problemsJournal of Global Optimization10.1007/s10898-023-01322-888:2(485-508)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10898-023-01322-8
Kümmerle CMaly JOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Recovering simultaneously structured data via non-convex iteratively reweighted least squaresProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669265(71799-71833)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669265
Xiao RFu YWan A(2023)Upper Bound of Null Space Constant $\rho(p,t,A,k)$ and High-Order Restricted Isometry Constant $\delta_{tk}$ for Sparse Recovery via $\ell_{p}$ MinimizationIEEE Transactions on Signal Processing10.1109/TSP.2023.329619771(2927-2935)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TSP.2023.3296197
Zeng HXue JLuong HPhilips W(2023)Multimodal Core Tensor Factorization and its Applications to Low-Rank Tensor CompletionIEEE Transactions on Multimedia10.1109/TMM.2022.321674625(7010-7024)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TMM.2022.3216746
Najiya KSastry C(2023)Analysis of general weights in weighted ℓ 1−2 minimization through applicationsDigital Signal Processing10.1016/j.dsp.2022.103833133:COnline publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.dsp.2022.103833
Ge ZWu ZZhang XNi Q(2023)An extrapolated proximal iteratively reweighted method for nonconvex composite optimization problemsJournal of Global Optimization10.1007/s10898-023-01299-486:4(821-844)Online publication date: 7-Jun-2023
https://dl.acm.org/doi/10.1007/s10898-023-01299-4
Ma BZalmai NLoeliger H(2022)Smoothed-NUV Priors for ImagingIEEE Transactions on Image Processing10.1109/TIP.2022.318674931(4663-4678)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1109/TIP.2022.3186749
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents