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.

本文提出了谐波均值迭代加权最小二乘（HM-IRLS）算法，应用于从不完整的线性观测中恢复秩为 r 的矩阵 X，通过一系列低复杂度的线性问题求解，以优化非凸的 Schatten-p 准范罚项，以提高低秩性。HM-IRLS 算法具有三个主要优势，尤其是在矩阵完成设置中：第一，算法自变量对于相关感兴趣的情况下以低秩矩阵呈现出显着的全局收敛性；第二，即使线性观察值的数量非常接近理论下界 r（d1+d2-r），HM-IRLS 表现出接近 1 的经验恢复概率；第三，如果线性观察满足适合的零空间属性，则 HM-IRLS 表现出局部超线性收敛速度（2-p）的优势。