Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Rate

被引:0
作者
Kuemmerle, Christian [1 ]
Verdun, Claudio Mayrink [2 ,3 ]
Stoeger, Dominik [4 ]
机构
[1] Johns Hopkins Univ, Dept Appl Math & Stat, Baltimore, MD 21218 USA
[2] Tech Univ Munich, Dept Math, Munich, Germany
[3] Tech Univ Munich, Dept Elect & Comp Engn, Munich, Germany
[4] KU Eichstatt Ingolstadt, Dept Math, Eichstatt, Germany
来源
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 34 (NEURIPS 2021) | 2021年 / 34卷
关键词
SIGNAL RECOVERY; ALGORITHMS; ROBUST; MINIMIZATION; RECONSTRUCTION; SELECTION; PROPERTY;
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The recovery of sparse data is at the core of many applications in machine learning and signal processing. While such problems can be tackled using l(1)-regularization as in the LASSO estimator and in the Basis Pursuit approach, specialized algorithms are typically required to solve the corresponding high-dimensional non-smooth optimization for large instances. Iteratively Reweighted Least Squares (IRLS) is a widely used algorithm for this purpose due to its excellent numerical performance. However, while existing theory is able to guarantee convergence of this algorithm to the minimizer, it does not provide a global convergence rate. In this paper, we prove that a variant of IRLS converges with a global linear rate to a sparse solution, i.e., with a linear error decrease occurring immediately from any initialization, if the measurements fulfill the usual null space property assumption. We support our theory by numerical experiments showing that our linear rate captures the correct dimension dependence. We anticipate that our theoretical findings will lead to new insights for many other use cases of the IRLS algorithm, such as in low-rank matrix recovery.
引用
收藏
页数:14
相关论文
共 72 条
[31]  
Ene A., 2019, P 36 INT C MACHINE L, P1794
[32]   Conjugate gradient acceleration of iteratively re-weighted least squares methods [J].
Fornasier, Massimo ;
Peter, Steffen ;
Rauhut, Holger ;
Worm, Stephan .
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2016, 65 (01) :205-259
[33]   LOW-RANK MATRIX RECOVERY VIA ITERATIVELY REWEIGHTED LEAST SQUARES MINIMIZATION [J].
Fornasier, Massimo ;
Rauhut, Holger ;
Ward, Rachel .
SIAM JOURNAL ON OPTIMIZATION, 2011, 21 (04) :1614-1640
[34]  
Foucart S., 2013, APPL NUMERICAL HARMO
[35]   CONSTRAINED RESTORATION AND THE RECOVERY OF DISCONTINUITIES [J].
GEMAN, D ;
REYNOLDS, G .
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1992, 14 (03) :367-383
[36]   Sparse signal reconstruction from limited data using FOCUSS: A re-weighted minimum norm algorithm [J].
Gorodnitsky, IF ;
Rao, BD .
IEEE TRANSACTIONS ON SIGNAL PROCESSING, 1997, 45 (03) :600-616
[37]  
GREEN PJ, 1984, J ROY STAT SOC B, V46, P149
[38]   Sparse representations in unions of bases [J].
Gribonval, R ;
Nielsen, M .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2003, 49 (12) :3320-3325
[39]   METHODS OF CONJUGATE GRADIENTS FOR SOLVING LINEAR SYSTEMS [J].
HESTENES, MR ;
STIEFEL, E .
JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS, 1952, 49 (06) :409-436
[40]   ROBUST REGRESSION USING ITERATIVELY RE-WEIGHTED LEAST-SQUARES [J].
HOLLAND, PW ;
WELSCH, RE .
COMMUNICATIONS IN STATISTICS PART A-THEORY AND METHODS, 1977, 6 (09) :813-827