提出新算法，可高效恢复有异常值的非对称低秩矩阵
Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery
- 采用过参数化预处理子梯度法，突破传统方法局限
- 在存在严重异常值时实现线性收敛，与目标矩阵秩无关
- 适用于测量算子满足混合范数RIP的鲁棒矩阵感知场景
本文研究基于矩阵分解的低秩非对称矩阵恢复问题，针对带有噪声观测的场景提出一种过参数化预处理子梯度算法（OPSA）。首次在文献中给出在存在严重异常值条件下，收敛速率与待恢复矩阵秩无关的线性收敛保证。该方法克服了现有预处理类方法在未知秩的非对称矩阵恢复中缺乏收敛性保障的缺陷。通过应用于（鲁棒）矩阵感知任务，证明当测量算子满足混合范数受限等距性（mixed-norm RIP）时具有显著优势。大量数值实验验证了理论结果，并展示了算法在不同过参数化程度和异常值水平下的有效性。
原文摘要 · Abstract (English)
In this paper, we focus on a matrix factorization-based approach to recover low-rank {\it asymmetric} matrices from corrupted measurements. We propose an {\it Overparameterized Preconditioned Subgradient Algorithm (OPSA)} and provide, for the first time in the literature, linear convergence rates independent of the rank of the sought asymmetric matrix in the presence of gross corruptions. Our work goes beyond existing results in preconditioned-type approaches addressing their current limitation, i.e., the lack of convergence guarantees in the case of {\it asymmetric matrices of unknown rank}. By applying our approach to (robust) matrix sensing, we highlight its merits when the measurement operator satisfies a mixed-norm restricted isometry property. Lastly, we present extensive numerical experiments that validate our theoretical results and demonstrate the effectiveness of our approach for different levels of overparameterization and outlier corruptions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。