Accelerated alternating minimization algorithm for low-rank approximations in the Chebyshev norm

技术摘要：Chebyshev 范数下低秩近似的加速交替最小化算法

问题陈述
本文探讨了在 Chebyshev 范数（也称为一致范数或 $L_\infty$ 范数）下构建矩阵低秩近似的问题。给定矩阵 $A \in \mathbb{R}^{m \times n}$ 和整数秩 $r \ge 1$，目标是寻找矩阵 $U \in \mathbb{R}^{m \times r}$ 和 $V \in \mathbb{R}^{n \times r}$，以最小化：
$$\|A - UV^T\|_C \to \min$$
其中 $\|X\|_C = \max_{i,j} |x_{ij}|$。与依赖于奇异值衰减且在单位不变范数（如谱范数或 Frobenius 范数）下可通过奇异值分解（SVD）高效求解的传统低秩近似不同，Chebyshev 近似适用于那些可能不表现出快速奇异值衰减、但在逐元素意义上仍具有低秩结构的矩阵。该问题在计算上极具挑战性；即使是秩为 1 的情况，检查是否存在特定误差界内的近似解也是 NP 完全问题。

方法论
作者提出了一种**加速交替最小化（CAM）**算法。该方法将矩阵近似问题分解为一系列向量近似问题。具体而言，固定一个因子矩阵（例如 $V$），问题就简化为求解 $m$ 个独立的最佳一致近似问题，形式如下：
$$\|a - Vu\|_\infty \to \min_{u \in \mathbb{R}^r}$$
其中 $a$ 是 $A$ 的一行，$V$ 是固定的因子。

核心技术贡献在于加速了这一子问题求解器。作者基于先前工作中引入的交替最小化框架（具体为参考文献 [6] 的任意秩和 [7] 的秩 1 情况），但引入了显著的算法改进：

1. 等振荡准则：本文建立了一个向量成为最佳一致近似问题解的充要条件，类比于多项式近似的 Chebyshev 等振荡定理。这涉及识别一个“特征集”索引，在该集合中，残差相对于子矩阵的行列式以交替符号达到其最大绝对值。
2. 加速求解器：作者提出了一种算法来求解该子问题，其复杂度为 $O(r^3 + Inr)$，其中 $I$ 是迭代次数。这优于文献 [6] 中方法的 $O(I(nr + r^4))$ 复杂度。加速是通过维护当前特征子矩阵（大小为 $(r+1) \times r$）的 QR 分解，并利用秩 1 更新来高效计算特征集中行的最优替换而实现的。
3. 交替最小化框架：完整算法在更新 $U$ 和 $V$ 之间交替，使用加速求解器。为确保数值稳定性，作者在每次迭代中应用重归一化。

主要贡献

• 加速算法：一种求解最佳一致近似问题（子问题 3）的新算法，在精确算术下与现有方法等价，但具有更低的计算复杂度。
• 理论表征（双向交错）：作者引入了秩 $r$ 的双向交错（2-way alternance）概念。他们证明，存在双向交错是 $(U, V)$ 成为低秩 Chebyshev 近似问题最优解的必要条件。
• 收敛性质：本文证明了所提出的交替最小化方法的所有极限点都满足双向交错条件。虽然序列 $\{U^{(t)}\}$ 和 $\{V^{(t)}\}$ 本身的收敛性仍然是一个未解决的理论问题（类似于交替最小二乘算法），但已证明极限点具有所需的结构性质。
• 数值评估：在大规模矩阵（包括 Hilbert 矩阵、单位矩阵和函数生成矩阵）上的广泛实验证明了该方法的有效性。

结果
数值评估将提出的 CAM 方法与交替投影（AP）方法和 SVD 进行了比较：

• 精度与稳定性：在具有快速奇异值衰减的 Hilbert 矩阵和单位矩阵上，CAM 在 20 个随机初始点上，在近似精度和稳定性方面始终优于 AP。
• 与 SVD 的比较：对于像单位矩阵这样在单位范数下难以用低秩结构近似的矩阵，CAM 实现了比 SVD 显著更低的 Chebyshev 误差。
• 可扩展性：该方法成功处理了大规模矩阵（高达 $n=32,768$）。相比之下，由于重复 SVD 计算的成本，交替投影方法在更大尺寸（例如 $n=32,768$）下变得计算上不可行。
• 函数生成矩阵：对于由高维球面上的指数核生成的矩阵，CAM 再次显示出比基线方法更优越的精度和稳定性。

意义
本文在三个主要领域声称具有重要意义：

1. 算法效率：它提供了一种计算高效的工具来解决最佳一致近似问题，使得大规模 Chebyshev 低秩近似成为可能。
2. 理论洞察：它将交错概念推广到任意秩，为 Chebyshev 范数下的最优性提供了严格的必要条件，而该条件此前主要仅针对秩 1 情况建立。
3. 实用价值：结果表明，对于逐元素误差至关重要（而非谱误差）的应用，所提出的加速交替最小化是现有基于投影方法的稳健且优越的替代方案，特别是对于大规模问题。