🔢 mathematics

Deterministic and randomized Kaczmarz methods for $AXB=C$ with applications to color image restoration

本文提出并分析了几种用于求解形式为 $AXB=C$ 的相容线性矩阵方程的确定性和随机性块卡茨马克（Kaczmarz）方法，建立了它们的收敛性质，并通过数值测试以及在彩色图像恢复中的应用展示了其有效性。

原作者： Wenli Wang, Duo Liu, Gangrong Qu, Michiel E. Hochstenbach

发布于 2026-02-04

📖 1 分钟阅读🧠 深度阅读

原作者： Wenli Wang, Duo Liu, Gangrong Qu, Michiel E. Hochstenbach

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

想象一下你正在试图解开一个巨大且复杂的拼图。在数学世界中，这个拼图就是一个矩阵方程（具体为 $AXB = C $）。你可以把$ A $和$ B $想象成拼图的规则，$ C $是你想看到的图像，而$ X$ 是你需要寻找的缺失部分。

这篇论文介绍了一套全新的工具，用于更快速、更高效地解决这些拼图问题，特别是针对修复模糊彩色图像这类问题。

以下是他们方法的详细拆解，使用了简单的类比：

1. 旧方法 vs. 新方法

“直接”法（重量级选手）：
想象一下，试图通过同时观察每一个拼图块和每一条规则来解开拼图。这就是旧有的、“直接”的方法所做的事情。这就像是为了移动一辆车而试图举起整个汽车。它确实有效，但极其沉重、缓慢，并且需要大量的内存。如果拼图非常庞大（比如一张高分辨率照片），这种方法就会陷入停滞。

“Kaczmarz”法（步进式行者）：
作者使用了一种被称为 Kaczmarz 的方法。与其同时观察整个拼图，不如想象你正在走过一条装满门的走廊。每一扇门代表一条规则（或一个“行”）。

你停在其中一扇门前，检查你当前的猜测是否符合这条特定的规则，并据此对你的猜测进行微调。
然后你走向下一扇门，再次检查，再次调整。
你就这样沿着走廊走下去，不断进行微小的修正，直到你的猜测完美符合所有的门。

这种方法对内存的要求要轻得多，因为你只需要记住一扇门，而不是整个走廊。

2. 三种主要策略

论文提出了三种不同的走廊行走方式：

A. “循环行者”（确定性 BK）

运作方式： 你按照严格的顺序走过走廊：门 1，门 2，门 3……一直走到尽头，然后回到门 1 重新开始。
类比： 这就像一位老师每天按字母顺序，一个接一个地检查每个学生的作业。
优缺点： 它很可预测。然而，如果前几扇门很容易，而最后几扇门很难，你可能会在处理难题之前，在简单的门前浪费太多时间。

B. “随机行者”（随机化 BK）

运作方式： 你不再按顺序行走，而是闭上眼睛，随机指向一扇门。你检查那一扇，进行调整，然后指向另一扇随机的门。
类比： 这就像一位老师通过从帽子里抽签的方式来挑选学生回答问题。
优缺点： 它通常比严格排序的方法更快，因为你可能会不小心提前遇到那些“难”的门。但有时，你可能会连续两次选中同一扇容易的门，这有点浪费时间。

C. “贪婪侦探”（论文的核心创新）

这是作者展现才华的地方。他们意识到，并非所有的门都同样重要。有些门具有“残差”——这是一个高级词汇，指的是“你当前的猜测错得有多离谱”。

策略： 与其随机选择或按序选择，**“贪婪侦探”**会观察所有的门并询问：“我现在哪一个错得最离谱？”
类比： 想象一位老师观察全班同学后说：“我发现 42 号同学对这条特定规则理解得非常混乱。让我们先专注于他吧！”
变体：
- GRBK（贪婪随机化）： 侦探挑选出最困惑的前 10% 的学生，然后从该组中随机挑选一名。
- MWRBK（最大加权残差）： 侦探挑选出单个最困惑的学生，并立即修复他们。这是贪婪方法的“确定性”版本。

3. 应用：修复模糊照片

论文在彩色图像恢复上测试了这些方法。

问题： 你有一张模糊且带有噪声的照片（方程中的“C”）。你想恢复出原始清晰的照片（“X”）。
设定： 模糊过程就像一个将图像涂抹开的滤镜。数学方程描述了这种模糊是如何发生的。
结果： 作者发现，**“贪婪侦探”**类方法（尤其是那个挑选“错得最严重”的一行的算法）是最快的。它们比旧方法用更少的步骤就达到了清晰的图像。
- “循环行者”很慢，因为它在图像简单的部分浪费了时间。
- “随机行者”表现尚可，但有时会错过关键的模糊区域。
- “贪婪侦探”直接瞄准了图像中最模糊的部分并首先修复它们，从而节省了大量时间。

4. 核心要点

效率： 通过只关注问题中当前“错误”的部分，这些新方法比同时观察所有内容的方法解决得更快。
灵活性： 这些方法无论是在“超定”（规则过多）还是“欠定”（规则过少）的情况下都适用。
胜出者： MWRBK 方法（即始终挑选单个最严重的误差进行修复的方法）在他们的测试中脱颖而出。它是恢复图像最一致且最快的方式。

简而言之，这篇论文告诉我们，在解决巨大的数学拼图时，不要只是绕圈子或者随机猜测。 相反，要观察全局，找到最大的错误，并首先修复它。这是一种更聪明、更快速完成任务的方法。

技术摘要：用于 $AXB = C$ 的确定性与随机化 Kaczmarz 方法

问题陈述

本文研究了如下形式的一致线性矩阵方程的求解问题：
$AXB = C$
其中 $A \in \mathbb{R}^{m \times p}$ ， $B \in \mathbb{R}^{q \times n}$ ，且 $C \in \mathbb{R}^{m \times n}$ 。目标是求出 $X \in \mathbb{R}^{p \times q}$ 。该方程出现在多种工程应用中，包括图像处理、控制理论和计算机视觉。文中特别强调了一个应用场景，即无噪声彩色图像修复的前向模型，表示为 $AXA_c^T = C$ ，其中 $A$ 代表通道内模糊， $A_c$ 代表跨通道模糊。

作者指出，直接求解此类方程的方法具有三次复杂度，并且在解不唯一或存在噪声时可能会失效。虽然已存在现有的迭代方法（例如基于梯度的迭代 (GI) 方法），但这些方法通常在每次迭代时都需要存储并访问整个系数矩阵，从而导致高昂的计算成本。本文的研究重点是行作用法 (row-action methods)，这类方法每次迭代仅访问 $A$ 的一行，在内存利用率和对噪声的鲁棒性方面具有优势。

方法论

本文将传统的用于线性系统 $Ax=b$ 的 Kaczmarz 类方法扩展到了矩阵方程 $AXB=C$。所提出的方法分为确定性循环变体以及随机化/贪婪变体。

1. 分块 Kaczmarz (BK) 方法

作者首先提出了一种名为分块 Kaczmarz (BK) 的确定性循环变体。与以往将方程分解为标量子系统的扩展方法不同，BK 方法每次处理 $A$ 的一行（以及对应的 $C$ 的一行），同时利用整个矩阵 $B$ 。

通用 BK (算法 2)： 适用于任何规模的 $B$ 。它通过基于第 $i_k$ 行 $A$ 的秩一更新来更新 $X$ 。作者证明，只要满足 $0 < \alpha < 2\|B\|^{-2}$ ，对于任何初始猜测 $X_0$ ，该方法都收敛于特定解 $X^*_0 = A^+CB^+ + X_0 - A^+AX_0BB^+$ 。
具有全列秩的 BK (算法 3)： 当 $B$ 具有全列秩时，通过 QR 分解（$B=QR $）将方程转化为$ AXQ = \tilde{C}$。这使得能够推导出该方法一个完整周期（扫描）的简洁矩阵公式。
具有全行秩的 BK (算法 4)： 当 $B$ 具有全行秩时，方程被重新表述为 $AX = \hat{C}$ 。这被视为一个具有多个右手侧的线性系统。作者推导出了一个扫描公式，并证明了其收敛性质类似于标准的多右手侧 Kaczmarz 方法。
等价性： 命题 3.7 确立了当 $B$ 非奇异时，算法 3 和算法 4 是等价的。

2. 贪婪与随机化变体

在 BK 框架的基础上，作者将来自线性系统的贪婪和随机化策略扩展到了矩阵方程语境中：

贪婪随机分块 Kaczmarz (GRBK, 算法 5)： 通过涉及最大加权残差范数和平均加权残差范数的阈值来选择行，扩展了 GRK 方法。
松弛贪婪随机分块 Kaczmarz (RGRBK, 算法 6)： 引入了一个可调参数 $\theta \in [0, 1]$ $θ \in [0, 1]$ ，用于在最大残差策略和平均残差策略之间进行平衡。
- $\theta = 1/2$ ：与 GRBK 一致。
- $\theta = 1$ ：与确定性的 MWRBK 一致。
最大加权残差分块 Kaczmarz (MWRBK, 算法 7)： 一种确定性方法，在每一步选择具有最大加权残差的行。

收敛性分析

论文对所有提出的方法进行了严格的收敛性分析：

BK 方法： 被证明收敛于 $X^*_0$ （如果 $X_0=0$ 且满足特定值域条件，则收敛于最小范数解 $X^* = A^+CB^+$ ）。
GRBK, RGRBK, MWRBK： 被证明在初始矩阵为零的情况下，以期望意义收敛于唯一的最小范数解 $X^*$ 。
收敛因子： 作者推导了收敛因子的上界。他们表明，贪婪/随机化变体（GRBK, RGRBK, MWRBK）的界限小于或等于标准随机分块 Kaczmarz (RBK) 方法的界限。具体而言，RGRBK 的上界随着 $\theta$ 的增加而减小，这表明确定性的 MWRBK ( $\theta=1$ ) 具有最紧的理论界限。
最优步长： 分析表明，当松弛参数 $\alpha = \|B\|^{-2}$ 时，收敛因子的上界达到最小。

核心贡献

扩展 Kaczmarz 方法： 本文成功地将确定性循环、贪婪随机化和最大加权残差 Kaczarkz 策略扩展到了通用的矩阵方程 $AXB=C$。
创新的分块公式： 作者针对 $B$ 具有全列秩或全行秩的情况，引入了特定的公式（算法 3 和 4），从而能够推导出优雅的完整扫描矩阵公式。
理论保证： 为所有提出的方法建立了收敛性质，包括显式的误差界限以及收敛至最小范数解的条件。
复杂度分析： 所提方法的单次迭代复杂度被证明为二次复杂度（ $O(q(p+n))$ 或类似），显著低于基于梯度的迭代 (GI) 方法的三次复杂度。
图像修复应用： 将这些方法应用于无噪声彩色图像修复模型，展示了其实际效用。

数值结果

作者通过数值实验验证了其理论发现：

合成数据： 在各种矩阵配置（过定、欠定、秩亏损）下的测试确认了 BK 方法的线性渐近收敛性。
与 RBK 的比较： 在对比 RBK、GRBK、RGRBK 和 MWRBK 的测试中，尽管由于残差计算导致单次迭代成本略高，但贪婪变体一致比标准的 RBK 需要更少的迭代次数和更少的总 CPU 时间。
图像修复： 在恢复模糊彩色图像（人脸、鸟、猕猴猩猩）的应用中，所提方法（特别是 MWRBK 和 RGRBK）在总计算时间上优于 GI 方法，并在达到目标误差所需的迭代次数方面优于标准的 BK 和 RBK 方法。
性能趋势： 结果表明，MWRBK 方法（确定性， $\theta=1$ ）通常在迭代次数和总时间方面实现最快收敛，这证实了收敛界限随 $\theta$ 改善的理论预测。

意义与主张

本文声称，所提出的 Kaczmarz 类方法为现有的线性矩阵方程迭代求解器提供了一种计算高效的替代方案。

效率： 通过利用秩一更新和行作用策略，这些方法避免了 GI 方法所需的昂贵矩阵-矩阵乘法，将复杂度从三次降低到二次。
鲁棒性： 其行作用的特性使得这些方法适用于大规模问题，并可能对噪声具有鲁棒性（尽管本文侧重于无噪声情况）。
贪婪策略的优越性： 数值实验表明，引入贪婪选择策略（GRBK, RGRBK, MWRBK）相比纯随机或循环选择能显著加速收敛，其中确定性的 MWRBK 在迭代次数和运行时间方面表现出最具吸引力的特征。
理论洞察： 针对 $B$ 的特定秩条件的扫描公式推导，为理解分块 Kaczmarz 方法的行为提供了更深的理论见解。

作者总结道，虽然 BK 方法对于理解行选择效应很有价值，但贪婪扩展（尤其是 MWRBK）在实践中始终能实现更快的收敛。他们指出，目前的研究局限于无噪声方程，并将应用这些方法处理含噪声右手侧作为未来的研究方向。