Linear Convergence of Iteratively Reweighted Least Squares for Nuclear Norm Minimization

Low-rank matrix recovery problems are ubiquitous in many areas of science and engineering. One approach to solve these problems is Nuclear Norm Minimization, which is itself computationally challenging to solve. Iteratively Reweighted Least Squares (IRLS) uses a sequence of suitable (re-)weighted least squares problems to minimize the nuclear norm. However, while global convergence guarantees have been established for IRLS in this context, no convergence rates have been known so far. In this paper, we show that an IRLS variant named MatrixIRLS converges to the ground truth solution with a linear rate. Numerical simulations corroborate our theoretical findings.