🔢 mathematics

Generalized matrix nearness problems II

本文通过引入仿射项、Kronecker 积以及任意正交不变范数，推广了广义矩阵逼近问题，为特定情形提供了闭式解，并为其余情形给出了保证全局收敛的无梯度迭代算法，同时证明了秩约束变体不存在 Mirsky 型定理。

原作者： Rongbiao Thomas Wang, Chi-Kwong Li, Lek-Heng Lim

发布于 2026-05-29

📖 1 分钟阅读🧠 深度阅读

原作者： Rongbiao Thomas Wang, Chi-Kwong Li, Lek-Heng Lim

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你正在试图修复一张模糊、失真的照片。你知道原始图像是完美的，但现在它被拉伸、压扁，或混入了一些噪声。你的目标是找到那个原始图像的“最佳”版本，使其与你手中拥有的失真数据相吻合。在数学世界中，这被称为矩阵邻近问题。

本文是同一作者先前研究的一篇续作。不妨将第一篇论文视为学习如何修复一张仅轻微变形的照片；而这篇新论文则 tackling 更为复杂的失真，并引入了修复这些失真的新工具，且完全无需通常处理此类任务所需的笨重、缓慢的机制。

以下是他们所做工作的简要分解，辅以简单的类比：

1. 新的失真（“是什么”）

在旧问题中，你试图寻找一个矩阵 $X$ 来修正方程 $A \approx X$ 。这就像试图寻找一张看起来像模糊照片的清晰照片。

在这篇新论文中，方程要复杂得多： $A \approx BXC$ 。

类比：想象你不仅仅是在寻找一张照片，而是在寻找一张经过特定滤波器（ $B$ ）处理、再经过特定镜头（ $C$ ）成像，甚至可能还贴上了一张贴纸（一个“仿射项”）的照片。
转折：作者还引入了克罗内克积。如果普通矩阵是单张照片，那么克罗内克积就像是由更小、重复的瓦片组成的照片。他们找到了如何修复这些“瓦片式”照片的方法，即使这些瓦片在排列方式上遵循特定规则（如同具有固定块数的拼图）。

2. 新规则（“约束”）

通常，当你试图修复照片时，可能会有一些规则：“照片必须是黑白的”，或“照片必须是完美的正方形”，或“照片只能包含 5 种不同的颜色”。

作者展示了如何在遵守所有这些规则的同时，求解他们复杂的方程：

秩约束：图像必须简单（低秩）。
对称性：图像如果翻转，必须看起来相同。
正定性：图像中的所有数字必须为正（如同光强度）。
新规则：他们甚至添加了关于“部分迹”（来自量子物理的概念，如同仅测量系统的一部分）和特定“特征值”规则（如同强制图像中存在特定模式）的规则。

3. 大惊喜：一种方案并不适用于所有情况

过去，数学家们认为，如果你使用一种类型的“尺子”（即弗罗贝尼乌斯范数，相当于测量总像素误差）找到了最佳解，那么该解对于你使用的任何“尺子”都是最佳的。这被称为米尔斯基定理。

作者证明了对于他们复杂的这一问题，这是错误的。

类比：想象你试图将行李箱放入汽车后备箱。如果你按总体积测量行李箱，会得到一个尺寸；如果你按最长边测量，会得到另一个尺寸。对于简单问题，无论你怎么测量，“最佳匹配”都是相同的。但对于这些复杂、失真的问题，“最佳匹配”会根据你使用的尺子而改变。不存在一个适用于所有误差测量方式的单一“魔法解”。

4. 新工具：“零阶”算法

由于不存在单一的魔法解，且在大多数情况下无法用简单公式（闭式解）求解这些难题，你通常需要计算机进行猜测和验证。

旧方法：大多数优化算法就像试图找到山谷底部的徒步者。他们观察坡度（梯度）来决定向哪个方向迈步。这需要计算复杂的导数，既缓慢又计算成本高昂。
作者的方法：他们开发了一种算法（算法 3），它是**“零阶”的**。
- 类比：与其观察坡度，该算法更像是一位蒙着眼睛却完美知晓山谷形状的徒步者。他们无需感受地面就能知道哪边是下坡；他们只需根据预先计算好的地图迈出一步。
- 优势：它不计算任何梯度或导数。它完全依赖于标准线性代数（例如将矩阵分解为其核心部分）。
- 结果：它极其快速且准确。在他们的测试中，其速度比标准软件（如 CVX）快了几个数量级，并且能够解决标准软件甚至无法触及的问题（例如使用“施瓦茨 3/2-范数”测量误差，这是一种奇怪的非标准尺子，其他软件无法理解）。

5. 现实世界测试

作者不仅在纸面上进行数学推导，还在现实场景中测试了他们的工具：

系统辨识：试图根据输入和输出推断机器的工作原理。他们的工具快速找到了答案，并保持在安全限制内，而标准软件往往根本无法找到有效答案。
目标检测：试图在噪声中识别目标（如雷达信号）。他们的工具比竞争对手快 10 倍。

总结

本文讲述的是如何解决一个非常困难的数学谜题（在严格规则下修复复杂、失真的数据），并使用一种巧妙、轻量级的工具将其解决。

他们为四种特定的、棘手的谜题变体找到了精确解。
他们证明了对于其余情况，无法使用“一刀切”的解决方案。
他们构建了一种新的快速算法，无需计算坡度（梯度）即可找到最佳答案。
他们表明，即使对于那些标准工具无法解决的问题，这种新工具也比其他人使用的笨重标准工具更快、更准确。

这是一个提醒：有时，老派的、巧妙的数学技巧（线性代数）比现代、重型的优化软件更有效。

技术摘要：广义矩阵邻近问题 II

问题定义

本文扩展了最初在 [13] 中研究的广义矩阵邻近问题。基本问题旨在寻找一个矩阵 $X$ ，使其在特定约束下与给定矩阵 $A$ 的距离最小化。此处考虑的广义形式涉及三个给定矩阵 $A, B, C$ ，并最小化目标函数：
$\min_{X \in S} \|A - BXC\|$
其中 $S$ 代表由各种约束（例如秩、范数、对称性、结构、正定性）定义的可行集。本文具体研究了 [13] 中标准弗罗贝尼乌斯范数（ $\|\cdot\|_F$ ）公式的三种扩展：

仿射项：在目标函数中引入仿射项，如 $dx^TE$ 或 $Dxe^T$ 。
克罗内克积：用克罗内克积（例如 $B \otimes X \otimes C$ ）替换标准矩阵乘积，并将秩约束推广为克罗内克秩。
施瓦茨范数：将弗罗贝尼乌斯范数推广为任意正交不变范数，特别是施瓦茨 $p$ -范数（ $\|\cdot\|_{\sigma,p}$ ）。

方法论

本文采用双重方法：针对特定情况推导闭式解，并为一般情况开发零阶迭代算法。

1. 闭式解

作者确定了四种允许闭式解的特定问题变体，扩展了 [13] 的结果：

仿射广义邻近：涉及 $\|A - BXC + Dxe^T\|_F$ 等项的问题。这些问题利用投影算子被转化为标准的广义邻近问题（命题 3.2）。
可分离克罗内克积：最小化 $\|A - B \otimes X \otimes C\|_F$ 。通过引入重排算子 $R$ 将克罗内克结构转化为标准矩阵邻近问题来解决（命题 3.3）。
广义克罗内克秩：在 $\text{rank}_\otimes(X) \le r$ 的约束下最小化 $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ 。利用克罗内克积的重排算子和奇异值分解（SVD）性质，该问题可简化为标准的秩约束问题（命题 3.4，算法 1）。
指定部分迹：在部分迹约束 $\text{tr}_P(X(W \otimes I)) = \lambda W$ 下最小化 $\|A - (B_1 \otimes B_2)X(C_1 \otimes C_2)\|_F$ 。该问题被简化为指定特征值问题或秩约束问题（命题 3.5，推论 3.6）。

2. 米尔斯基型结果的不存在性

本文研究了 Eckart–Young–Mirsky 定理（该定理指出最佳秩- $r$ 近似与所使用的正交不变范数无关）是否可推广到广义问题 $\min_{\text{rank}(X) \le r} \|A - BXC\|$ 。

结果：作者证明，当 $B$ 和 $C$ 不是单位矩阵时，不存在米尔斯基型结果。
证据：通过反例（例 4.2），他们证明了秩约束广义问题的最小化子取决于所选的具体施瓦茨范数（ $p=1, 2, \infty$ ）。这与标准秩近似问题形成对比，在后者的所有正交不变范数下解是通用的。

3. 迭代算法（算法 3）

对于不存在闭式解的情况（特别是针对一般施瓦茨范数和复杂约束），作者提出了一种基于迪克斯特拉投影法（算法 2）的迭代算法，并针对施瓦茨范数进行了专门化（算法 3）。

机制：该算法在两个步骤之间交替：
1. $X$ -更新：在弗罗贝尼乌斯范数下求解广义矩阵邻近问题（使用 [13] 中的方法或第 3 节推导的闭式解）。
2. $Y$ -更新：求解施瓦茨范数 $\|Y\|_{\sigma,p} + \frac{\mu}{2}\|Y - M\|_F^2$ 的邻近算子问题。作者推导出了 $Y$ 奇异值的显式闭式更新公式，分别针对 $p=1$ （核范数）、 $p=\infty$ （谱范数）以及一般 $p \in (1, \infty)$ （引理 5.5–5.7）。
关键特征：该算法是零阶的；它不计算显式梯度或次梯度。它完全依赖于数值线性代数运算（SVD 和矩阵乘法）。
收敛性：已证明该算法从任意初始点出发均收敛至全局最小化子。收敛速度为次线性（由于 $p \neq 2$ 时施瓦茨范数缺乏强凸性），尽管数值实验表明在实践中表现出近线性行为。

关键结果

闭式展开：本文提供了仿射、可分离克罗内克、克罗内克秩和部分迹变体的广义邻近问题的显式解。
理论局限性：确立了在存在非单位乘数 $B$ 和 $C$ 的情况下，解在不同正交不变范数下的通用性（米尔斯基定理）会失效。
算法性能：
- 速度：在数值实验（第 6 节）中，算法 3 显著优于通用凸优化求解器（特别是带有 SCS 求解器的 CVX）。对于大维度，CVX 往往无法在合理的时间限制内收敛，而算法 3 收敛迅速。
- 精度：算法 3 在前向误差上达到了机器精度（ $\approx 10^{-15}$ ），而 CVX 表现出波动的误差（范围从 $10^{-7}$ 到 $10^3$ ），并且经常无法满足约束（例如在系统识别任务中）。
- 通用性：该算法成功处理了非标准凸目标（例如施瓦茨 $3/2$ -范数）和非凸约束（例如秩约束、指定特征值），而这些是 CVX 等标准求解器无法触及的。

意义与主张

本文声称通过以下方式推进了矩阵邻近问题领域：

扩展可解性：为涉及仿射项和克罗内克结构的新类别问题提供闭式解。
阐明理论边界：展示了将经典近似定理（米尔斯基）推广到广义设置时的局限性。
提供稳健的替代方案：提出了一种全局收敛、无梯度且计算性能优于通用求解器的迭代算法。
强调结构利用：作者强调，通过数值线性代数利用特定的矩阵结构（如 [13] 和本工作所做的那样），比单纯依赖通用凸优化框架能获得更好的性能和更广泛的适用性（包括非凸情况）。

该工作作为 [13] 的续篇呈现，保持了在不进行导数计算的情况下解决优化问题的理念，从而利用矩阵空间的丰富结构。