Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery

Abstract

We propose a new iteratively reweighted least squares (IRLS) algorithm for the recovery of a matrix $X\in {\mathbb{C}}^{d_1\times d_2}$ of rank $r\ll \min (d_1,d_2)$ from incomplete linear observations, solving a sequence of low complexity linear problems. The easily implementable algorithm, which we call harmonic mean iteratively reweighted least squares (HM-IRLS), optimizes a non-convex Schatten-$p$ quasi-norm penalization to promote low-rankness and carries three major strengths, in particular for the matrix completion setting. First, we observe a remarkable global convergence behavior of the algorithm's iterates to the low-rank matrix for relevant, interesting cases, for which any other state-of-the-art optimization approach fails the recovery. Secondly, HM-IRLS exhibits an empirical recovery probability close to $1$ even for a number of measurements very close to the theoretical lower bound $r(d_1+d_2-r)$, i.e., already for significantly fewer linear observations than any other tractable approach in the literature. Thirdly, HM-IRLS exhibits a locally superlinear rate of convergence (of order $2-p$) if the linear observations fulfill a suitable null space property. While for the first two properties we have so far only strong empirical evidence, we prove the third property as our main theoretical result.

47 pages, 6 figures

References in corpus (4)

• Global Optimality of Local Search for Low Rank Matrix Recovery
• Matrix Completion has No Spurious Local Minimum
• Stability of low-rank matrix recovery and its connections to Banach space geometry
• A generalisation of Mirsky's singular value inequalities

Cited by in corpus (7)

• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries
• Iteratively Reweighted Least Squares for Basis Pursuit with Global Linear Convergence Rate
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method
• Approximation, Gelfand, and Kolmogorov numbers of Schatten class embeddings
• Denoising and Completion of Structured Low-Rank Matrices via Iteratively Reweighted Least Squares
• Low Rank Regularization: A Review