提出最优权重策略,显著提升低秩恢复中核范数迭代重加权的收敛速度。
Tight Majorizations and Convergence Rates of Nuclear Norm Minimization IRLS
- 用调和平均权重构建全局二次上界,理论证明其最优性。
- 在特定条件下实现维数无关的局部线性收敛,比传统方法快得多。
- 适用于各种矩阵形状和初始化,实验验证效果优于主流方案。
迭代重加权最小二乘(IRLS)是核范数最小化的一种自然方法,但其收敛速率及权重算子的作用长期未被充分理解。本文针对低秩恢复中的约束核范数最小化问题,建立了IRLS方法的精确收敛速率。核心贡献在于对平滑核范数提出了新的上界分析:调和平均权重算子构成有效的全局二次上界。进一步证明该权重在幂平均权重族中是最优的,解释了为何其优于仅使用行或列空间信息的单边重加权方法。在施瓦茨-1零空间性质下,我们证明了多种权重算子(包括调和平均权重)的全局线性收敛性。对于采用调和平均权重的IRLS,我们证明了维数无关的局部线性收敛率。我们还给出反例,表明使用单边权重的IRLS通常无法获得此类维数无关的局部收敛率。数值实验验证了理论结果,并展示了调和平均重加权在方阵、矩形矩阵及对抗性初始化下的实际优势。
原文摘要 · Abstract (English)
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. 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. 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. 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. Numerical experiments corroborate the theoretical results and illustrate the practical advantage of harmonic-mean reweighting across square, rectangular, and adversarially initialized recovery problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。