Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery
Christian Kümmerle, Juliane Sigl; 19(47):1−49, 2018.
Abstract
We propose a new iteratively reweighted least squares (IRLS) algorithm for the recovery of a matrix X∈Cd1×d2 of rank r≪min 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.
[abs][pdf][bib] [github.com]
© JMLR 2018. (edit, beta) |