Tight Majorizations and Convergence Rates of Nuclear Norm Minimization IRLS

核范数最小化 IRLS 的紧致优超与收敛速率

Abstract: Iteratively reweighted least squares (IRLS) methods constitute a natural approach to nuclear norm minimization, but their convergence rates and the role of the weight operator have remained poorly understood.

摘要： 迭代重加权最小二乘法（IRLS）是核范数最小化的一种自然方法，但其收敛速率以及权重算子的作用一直以来理解尚不充分。

This paper establishes sharp convergence rates for IRLS methods for constrained nuclear norm minimization in low-rank recovery. A central ingredient is a new majorization analysis for the smoothed nuclear norm: we prove that the harmonic-mean weight operator defines a valid global quadratic majorizer.

本文为低秩恢复中约束核范数最小化的 IRLS 方法建立了精确的收敛速率。其核心要素是对平滑核范数进行的一种新的优超分析：我们证明了调和平均权重算子定义了一个有效的全局二次优超函数。

Furthermore, we show that this weight operator is optimal within the family of power-mean weights, clarifying why it improves over classical one-sided reweighting schemes that use only row- or column-space information.

此外，我们证明了该权重算子在幂平均权重族中是最优的，这阐明了为何它优于仅使用行空间或列空间信息的经典单侧重加权方案。

Under a Schatten-1 null space property, we prove global linear convergence of IRLS algorithms using a variety of weight operators, including the harmonic-mean weights. For IRLS with harmonic-mean weights, we prove a dimension-independent, locally linear convergence rate.

在 Schatten-1 零空间性质下，我们证明了使用多种权重算子（包括调和平均权重）的 IRLS 算法具有全局线性收敛性。对于使用调和平均权重的 IRLS，我们证明了其具有与维度无关的局部线性收敛速率。

We provide a counterexample showing that this dimension-independent local rate cannot in general be obtained for IRLS algorithms using one-sided weight operators, which predominate in the literature.

我们提供了一个反例，表明对于文献中占主导地位的、使用单侧权重算子的 IRLS 算法，通常无法获得这种与维度无关的局部收敛速率。

Numerical experiments corroborate the theoretical results and illustrate the practical advantage of harmonic-mean reweighting across square, rectangular, and adversarially initialized recovery problems.

数值实验证实了上述理论结果，并展示了调和平均重加权在方形、矩形以及对抗性初始化恢复问题中的实际优势。