用于矩阵补全的贪心阶段式秩一矩阵追踪

《Signal Processing》：Greedy stagewise rank-one matrix pursuit for matrix completion

　　

## 摘要

低秩矩阵补全是信号处理中的一个基本逆问题，出现在需要从不完整且有噪声的观测中恢复具有结构化矩阵信号的诸多应用中。基于核范数最小化的经典凸方法具有强大的恢复精度，但往往计算成本高昂；而贪心秩一追踪方法虽然更简单、更快，但由于其保守的单原子更新方式，可能收敛缓慢。本文提出了分阶段秩一矩阵追踪算法（Stagewise Rank-One Matrix Pursuit，StR1MP），这是一种贪心谱恢复算法，通过每次迭代选择多个显著奇异分量来扩展经典秩一矩阵追踪。其选择规则基于从空残差模型推导出的统计阈值，使该方法能够区分残差中的信息性奇异方向与掩蔽噪声。我们建立了以下理论保证：空模型下的噪声拒绝、足够强信号奇异值的检测、对经典秩一矩阵追踪的单步优势，以及观测最小二乘目标的单调递减性。在合成矩阵补全问题和真实推荐基准上的实验表明，所提方法在保持具有竞争力的重建精度的同时，显著减少了迭代次数和运行时间。这些结果表明，分阶段残差谱选择为不完整低秩信号恢复提供了一种有效且计算上具有吸引力的方法。

## 引言

分阶段正交匹配追踪（Stagewise Orthogonal Matching Pursuit，StOMP）作为一种贪心稀疏恢复方法被提出，它通过在每次迭代中选择所有残差相关性超过统计校准阈值的所有坐标（而不仅仅是一个坐标）来改进经典正交匹配追踪（OMP）[1] [2]。这一简单修改以重要方式改变了贪心恢复的几何特性：它不再强制每次一个原子的策略，而是允许在残差中包含证据表明多个分量超过噪声本底时同时激活多个显著方向。在高维逆问题中，这种分阶段视角通常比严格的单步逐次追踪能更忠实地匹配残差的结构。

本文开发了这一思想的矩阵值类似物，用于低秩矩阵补全。矩阵补全涉及从其部分条目中恢复未知的低秩矩阵，可自然地解释为不完整数据谱估计问题。未知信号是矩阵值的，观测算子掩蔽了大量条目，目标是从部分且有噪声的测量中推断主导的潜在奇异结构。此类问题在信号处理中反复出现，包括协同过滤、基于图的数据恢复和结构化约束低秩估计[3]–[8]。从这一视角看，矩阵补全不仅仅是一个通用的优化问题；它是一个在缺失数据获取条件下的谱逆问题。

精确的观测模型和最小二乘公式将在第2节中给出一次。从高层次来看，本文考虑从一组噪声条目中恢复未知的低秩矩阵。经典方法包括基于核范数最小化的凸松弛及其奇异值阈值化求解器[9]，以及基于原子或奇异方向更新的贪心秩构建程序[10]–[15]。凸方法通常具有统计学吸引力但计算量较大，而贪心方法较轻量但在新分量的接纳方式上可能过于保守。

在贪心低秩方法中，秩一矩阵追踪（Rank-One Matrix Pursuit，R1MP）和正交秩一矩阵追踪（Orthogonal Rank-One Matrix Pursuit，OR1MP）尤其具有吸引力，因为它们直接处理残差的主导奇异方向[16][17]。在第 $t$ 次迭代中，这些方法构造残差矩阵并选择一个与其主导奇异模态对齐的单秩一原子。这恰好是稀疏逼近中经典单坐标贪心追踪的矩阵类似物。然而，它也继承了向量情况下促使StOMP提出的同样结构性局限：如果残差包含多个统计上 meaningful 的分量，仅选择其中一个可能不必要地减缓收敛。换言之，当残差谱景观明确表明存在多个活跃模态时，一次一个秩的追踪可能过于严格。

近期工作也已经远远超越了最早的核范数和贪心基线。具有自动秩估计的秩一矩阵补全使用秩一权重上的 $\ell_1$ 惩罚来避免预先指定秩[18]。鲁棒秩一变体将平方损失替换为 $\ell_p$ 或显式鲁棒正则化器，以减少对脉冲型损坏和离群值的敏感性[19][20]。与此同时，可扩展的非凸低秩学习方法使用有界、截断或其他非凸替代函数来表示秩和奇异值，通常比朴素的核范数最小化具有改进的计算行为[21]–[24]。这些发展促使我们对经典贪心算法和新型非凸低秩求解器进行公平比较。

这一观察提出了一个直接且理论上自然的问题：StOMP背后的分阶段原则能否从向量设置中的残差相关性提升为矩阵设置中的残差奇异值？本文发展的答案是肯定的。我们提出了分阶段秩一矩阵追踪（StR1MP），一种贪心矩阵补全方法，用分阶段谱激活规则替代经典的单奇异方向更新。给定残差

$$R_t = P_{\Omega}(Y - X_t),$$

其奇异值分解为

$$R_t = \sum_{i=1}^{q_t} \sigma_i(R_t)\, u_i\, v_i^\top, \quad q_t := \mathrm{rank}(R_t),$$

所提方法选择所有满足

$$\sigma_i(R_t) > \tau_t$$

的奇异方向 $(u_i, v_i)$，其中 $\tau_t$ 是从空残差模型推导出的阈值。该阈值的选择使得在掩蔽噪声模型下，纯噪声产生的奇异值以高概率保持在其下方，而足够强的信号诱导的奇异方向则超过它。选出的原子随后被纳入活跃集，并在观测条目上进行最小二乘重新拟合。因此，所提方法是一个矩阵分阶段追踪方案：StOMP对残差相关性进行阈值化，而StR1MP对残差奇异值进行阈值化。

这种从StOMP到矩阵补全的提升不仅在算法上是自然的，在信号处理上也具有意义。在稀疏信号恢复中，我们识别相对于噪声本底携带显著能量的坐标。在不完整低秩恢复中，类似的对象不是坐标，而是奇异模态。因此，残差奇异谱扮演了检测域的角色。对该谱进行阈值化产生了一个检验，判断给定的残差方向应被解释为信息性结构还是掩蔽噪声波动。这赋予了该方法明确的谱处理解释：每次迭代执行残差谱筛选，保留所有统计显著的奇异模态，并抑制纯噪声模态。这一视角与信号处理领域的近期发展高度一致，其中矩阵补全越来越多地被当作一种结构化谱恢复原语来处理，而不仅仅是秩惩罚优化模板[3]–[8]。

因此，本文的贡献是双重的。首先，我们提出了一种分阶段矩阵追踪算法，其选择规则是StOMP背后阈值化原则的奇异值域类似物。其次，我们对该规则进行了严格的分析。具体而言，我们从空残差模型推导了一个阈值，建立了该模型下的噪声拒绝保证，证明了足够强信号奇异值的检测，表明所选集在激活时总是包含经典的R1MP原子，并建立了R1MP的单步优势以及观测最小二乘目标的单调递减性。其要点不仅仅是在启发式上加速已知的贪心方法，而是将分阶段低秩追踪置于一个干净的统计和谱基础之上。

所得到的图景在概念上是简单的。经典R1MP是单原子贪心规则；StR1MP是其分阶段推广。经典StOMP对向量残差相关性进行阈值化；本方法对矩阵残差奇异值进行阈值化。前者作用于坐标字典中，后者作用于秩一谱字典中。这种类比足够强，能够同时指导算法和其理论，但矩阵设置也引入了非平凡的新问题，因为被阈值化的对象是掩蔽残差算子的奇异值，而不是标量内积。因此，分析必须结合矩阵集中性、摄动理论和贪心逼近的思想。

本文其余部分组织如下。第2节固定观测模型、观测最小二乘目标以及全文使用的符号。第3节提出StR1MP算法及其每次迭代的开销。第4节发展空残差模型并推导分阶段奇异值阈值。第5节建立理论保证：噪声拒绝、检测、R1MP原子的包含性、单步优势以及观测残差能量的单调收敛性。第6节报告在合成和真实矩阵补全问题上的实验，包括与经典R1MP、ADMiRA、核范数最小化以及近期非凸/鲁棒矩阵补全基线的比较，以及参数敏感性、鲁棒性和极端稀疏性评估。第7节为结论。

## 问题建模

我们考虑有噪低秩矩阵补全。设 $M \in \mathbb{R}^{m \times n}$ 为未知矩阵，$\Omega \subseteq \{1, \cdots, m\} \times \{1, \cdots, n\}$ 为观测索引集合。数据矩阵为 $Y = P_{\Omega}(M + N)$，其中 $N \in \mathbb{R}^{m \times n}$ 为加性噪声矩阵，$P_{\Omega}$ 为逐元素定义的采样算子：

$$[P_{\Omega}(X)]_{ij} = \begin{cases} X_{ij}, & (i,j) \in \Omega, \\ 0, & (i,j) \notin \Omega. \end{cases}$$

目标是在 $M$ 具有低秩的假设下，从不完整的观测 $Y$ 中恢复 $M$。该设置在协同过滤、高光谱成像及相关逆问题中出现。

## 分阶段秩一矩阵追踪

本节介绍所提出的分阶段秩一矩阵追踪（StR1MP）算法，用于低秩矩阵恢复。该方法通过每次迭代中纳入残差的多个奇异分量来扩展经典秩一矩阵追踪（R1MP）框架。选择规则受到分阶段稀疏恢复算法（如StOMP）[2]的启发。

### 阈值选择

所提分阶段算法选择残差矩阵中奇异值超过数据依赖阈值的奇异方向。为从理论上确定该阈值，我们研究了在空假设下（即无信号分量残留）残差的分布。其推导遵循与StOMP阈值分析相同的哲学，即在纯噪声模型下分析残差[2]。在矩阵设置下——

## 理论保证

本节建立所提分阶段选择规则的主要理论性质。全文使用残差分解

$$R_t = S_t + W,$$

其中 $S_t = P_{\Omega}(M - X_t)$，$W = P_{\Omega}(N)$，如第2.4节所述。候选集为 $\mathcal{C}_t = \{(u_i, v_i) : \sigma_i(R_t) > \tau_t\}$，其中 $\tau_t$ 是式(7)中定义的阈值。分析分为五个步骤：空模型下的噪声拒绝、残差奇异值的摄动、强信号奇异值的检测、R1MP原子的包含性以及定量——

## 实验设置

我们在合成矩阵补全问题上评估所提出的StR1MP算法，并将其与经典和近期基线进行比较。经典基线包括核范数最小化（NNM，通过奇异值阈值化求解[9][11][12]）、秩一矩阵追踪（R1MP）[16]以及ADMiRA[15]。核范数最小化代表低秩恢复的经典凸松弛方法，而R1MP和ADMiRA是典型的贪心——

## 结论

本文提出了分阶段秩一矩阵追踪（StR1MP），一种用于低秩矩阵补全的贪心算法，通过分阶段选择多个奇异分量来扩展经典秩一追踪。我们从空残差模型推导了一个统计驱动的谱阈值，使算法能够区分信息性奇异方向与噪声。我们建立了噪声拒绝保证（定理1）、强信号奇异值检测（定理2）——

## 利益冲突声明

作者声明不存在已知的可能影响本文所报告工作的竞争性经济利益或个人关系。

Angshul Majumdar