精读笔记
Problem Setting
[Accelerated Exact Recovery from Noisy Data via Averaging and Noise-Aware Adaptive Bregman-Kaczmarz]（arXiv preprint / 2026）
这篇论文实际解决的是 noisy linear inverse problems 中一个很特定的在线观测模型：算法不能访问 clean b，每次 query 某一行只得到 fresh、independent、zero-mean corrupted measurement，但目标仍是恢复 Ax=b 对应的 noise-free minimum-f solution。关键矛盾是：每一步都在注入新噪声，但又希望最终误差趋零，而不是像固定步长 Kaczmarz 那样停在 noise ball。
以前路线各卡一半。ABK 通过 adaptive step 能 exact recovery，但其 block version 用 sum update，理论上没有说明更大 block 是否真的更快；averaged Kaczmarz/RSKA 能做 variance reduction，但 fixed step 在 noisy/inconsistent setting 下仍然有残余误差；标准 randomized Kaczmarz 的 p_i proportional to ||a_i||^2 只看 operator geometry，不看 measurement reliability。本文要解决的是把 batch averaging、adaptive decay、heteroscedastic weighting 放到同一个可证明框架里。
Motivation
已有方法不够的核心原因是它们把两个不同问题混在一起：几何下降方向的选择，以及噪声注入强度的控制。row-norm sampling 对 noiseless geometry 合理，但在 heteroscedastic noise 下会过度信任高噪声测量；block ABK 做了并行，却没有把 block 当成低方差 estimator 来建模，因此 batch size 的理论收益不清楚。
作者的关键观察是：如果 block 内不是求和而是求平均，那么 batch 的作用会从“更大一步”变成“同一方向的低方差估计”；再配合 sampling-weight coupling，可以让 one-step descent 中的确定性残差项和随机噪声项都被干净地分离。缺口不是缺一个新 projection，而是缺一个能同时保留 exact recovery、batch variance reduction 和 noise-aware reliability 的分析对象。
Core Idea
论文真正的核心思想是重新组织每一步 Kaczmarz update 的信息流：每个 row query 产生一个 noisy correction，batch 内对 correction 做平均，而不是累加；同时用权重降低高噪声行的影响，使更新方向既保持对 residual 的有效下降，又最小化每步注入的噪声方差。
本质区别在于 batch 被建模为 stochastic estimator，而不是 block constraint projection。这个改变让分析收缩到一个 PSD matrix T：T 的最大特征值控制 admissible/adaptive step 的速度，batch size 增大会降低该谱常数，uniform case 下最大理论收益正好是 stable rank ||A||_F^2 / sigma_max(A)^2。这个 insight 有迁移价值：在 noisy row-action methods 中，batching 的正确收益来自平均后的二阶矩结构，而不是简单并行更多 row。
Method
AABK 保留 Bregman-Kaczmarz 的 dual-primal mirror update，但关键机制只有三个。
第一，batch averaging。它解决的是 fresh noise 每步持续进入的问题。平均后，噪声二阶项带 1/tau 衰减；更重要的是，谱分析中的 T 显式随 tau 改善，使 batch size 成为 convergence-rate knob，而不只是 hardware knob。
第二，noise-aware weighting。它解决异方差测量可靠性问题。通过 coupling p_i w_i / ||a_i||^2 = alpha / ||A||_F^2，作者保留了期望内积下降项的干净形式；在这个约束下最小化 noise prefactor 得到 p_i proportional to sigma_i ||a_i||、w_i proportional to ||a_i|| / sigma_i。核心变化是把 row 的几何重要性和观测可靠性分开处理。
第三，adaptive step size。它解决 exact recovery，而不是单纯加速。步长由 beta_k 和 sigma_max(T) 控制：早期 beta 大，步长接近常数并可 over-relax；后期 beta 小，步长近似 1/k，从 stochastic approximation 角度消化剩余噪声。没有这个 vanishing tail，averaging 只能降低 noise ball，不能消除它。
Key Insight / Why It Works
最核心贡献不是算法形式复杂，而是 one-step bound 的重参数化。通过 averaging 和 coupling，期望下降项变成 residual norm 的固定比例，noise term 变成 Tr(P W^2 Sigma D^{-2}) / tau，deterministic squared update term 由同一个 PSD matrix T 控制。这样 batch size、noise weighting、adaptive step 不再是互相打架的 heuristic，而是分别进入 bound 的不同位置。
真正有效的部分大概率是两个：average 而非 sum，以及 noise-aware variance minimization。前者解释 batch scaling，后者解释 heteroscedastic setting 下的明显优势。adaptive step 是 exact recovery 的必要条件，但这部分主要继承 ABK/Marshall-Mickelin 一线；Bregman geometry 也是既有框架，本文的新意不在这里。
是否是 scaling？部分是。batch gain 本质上就是 stochastic averaging 的 1/tau variance reduction 加上谱常数改善；论文的贡献在于证明这种 scaling 在 ABK exact recovery 框架里不会破坏收敛，并且 uniform case 的最大收益由 stable rank 限定。换言之，这不是 magical acceleration，而是把 mini-batch variance reduction 放到了 row-action inverse problem 的正确谱坐标中。
noise-aware weighting 是 better inductive bias：它引入了“测量可靠性不等”的先验。若 sigma_i 真实可靠，这个 bias 很强；若 sigma_i 错估或噪声不是 zero-mean fresh，则该机制可能直接失效。文中未充分说明 variance estimation 的鲁棒性，因此实际部署中最脆弱的不是迭代公式，而是 noise model calibration。
Relation To Prior Work
最接近的路线是 ABK、RKA/RSKA、randomized Kaczmarz with averaging、以及 heteroscedastic/weighted randomized Kaczmarz。本文不是跳出 Kaczmarz 谱系，而是在 Bregman-Kaczmarz + stochastic approximation 这条线上补上 batch/noise-aware 这一环。
和 ABK 的本质差异：ABK 依靠 adaptive shrinking step 从 independent noise 中 exact recovery，但 block-sum 不提供明确 monotone batch acceleration；AABK 把 block 改成 averaged estimator，使 batch size 进入 T 并带来 stable-rank-controlled gain。
和 RSKA/RKA 的本质差异：这些方法已有 averaging，但 fixed step under noise 只能到 noise ball；AABK 的 adaptive tail 才是 exact recovery 的关键。
和传统 row-norm sampling 的差异：传统采样优化 noiseless geometry；本文在 coupling 下显式优化 noise constant。看似新的是 p_i proportional to sigma_i ||a_i||、w_i proportional to ||a_i||/sigma_i，但思想上是 importance sampling / inverse-variance weighting 的重组；实质创新在于证明该选择与 Bregman-Kaczmarz exact recovery 和 batch monotonicity 兼容。
Dataset / Evaluation
实验覆盖 synthetic Gaussian matrix 和一个 simulated CT reconstruction。它们基本能验证论文的核心 claim：异方差 fresh Gaussian noise 下，averaging 降低噪声，noise-aware weights 优于 uniform，adaptive step 能继续越过固定步长方法的 noise floor。CT 例子比纯 synthetic 更贴近 inverse problem，但仍是 controlled simulation，不是真实设备噪声链路。
evaluation 支持理论机制，但不应过度解读。实验没有系统测试 biased noise、temporally correlated noise、unknown sigma_i、non-Gaussian heavy-tail、真实固定 corrupted RHS 等情形；这些恰好是 exact recovery 假设最敏感的地方。AABK_gen_heur 在 CT 表格中指标非常高，但其 beta_0 heuristic 极大、step phase 被拉长，增益归因不完全干净；可能混有 parameter tuning / phase selection 的影响。文中没有大段 ablation 去隔离 sigma estimation、tau、gamma、beta_0 的贡献。
Limitation
最大限制是 noise model：fresh、independent、zero-mean 是 exact recovery 的根。真实 inverse problems 中更常见的是固定 noisy measurement、系统偏差、相关噪声或校准误差；在这些情况下，AABK 很可能退化为更好的 noise-ball method，而不是 exact recovery method。
第二个限制是 sigma_i 需要已知。noise-aware optimality 如果建立在错误方差上，可能会系统性低估某些 row 的破坏性。文中未充分说明 sigma_i 如何在 deployment 中稳定估计，也没有给出 misspecification analysis。
第三，最优性只在 coupling p_i w_i / ||a_i||^2 固定的 admissible family 内成立。这是为了分析 tractability 引入的约束，不代表全局最优 sampling-weight design。作者自己也承认 fully optimal pair 可能在 coupling 外。
第四，general weights 下真实 sigma_max(T) 可能不随 tau 单调，论文用 upper bound U(tau) 保障 certified rate。这在理论上成立，但可能保守；实际加速和 bound 加速之间的 gap 文中未充分说明。
第五，当前 guarantee 是 expectation bound。对在线 noisy inverse problems，high-probability behavior、tail risk、早期 transient spike 是否可控更接近实际需求。
Takeaway
- 1. 对 noisy row-action methods，batch 的正确用法是 averaged estimator，而不是 block-sum；否则 parallelism 未必转化为 convergence-rate gain。
- 2. 在 heteroscedastic measurement setting 中，row norm sampling 是不完整的 inductive bias；可靠性必须进入 sampling/weighting，否则高噪声少数行会主导误差常数。
- 3. exact recovery from noisy queries 的本质不是把噪声滤干净，而是 early aggressive descent + late Robbins-Monro tail 的步长调度；averaging 只是在这个过程中降低每步噪声注入。
- 4. 未来真正值得做的是脱离 fresh independent noise 假设：处理 correlated/biased/fixed noise、unknown variance、high-probability bounds，以及 coupling 外的 joint optimal design。
一句话总结
这篇论文把 averaged mini-batch variance reduction 和 inverse-variance-style noise weighting 严格嵌入 adaptive Bregman-Kaczmarz exact recovery 框架，实质贡献是证明 batch scaling 与异方差可靠性建模可以在同一个谱分析对象下组合。