精读笔记

Problem Setting

Sparse Recovery via \(\ell_p^p/\ell_q^p\) Ratio Minimization: Theory and Algorithm（arXiv preprint / 2026）。这篇论文解决的是 constrained norm-ratio sparse recovery 的理论和算法闭环问题：给定欠定线性测量，在精确或有噪约束下最小化 \(\|x\|_p^p/\|x\|_q^p\)。它不是单纯提出一个新的 penalty，而是试图回答这个广义 ratio 模型什么时候 exact recovery、什么时候 stable recovery、以及一个直接处理分式结构的算法是否至少收敛到合理 stationary point。

真正难点有三层。第一，目标是非凸、非光滑、非分离且 scale-invariant，传统 \(\ell_1\) NSP/RIP 不能直接搬过来。第二，分母 \(\ell_q\) 会把全局幅值结构耦合进目标，导致 recovery 条件不仅依赖 support，还依赖动态范围和 head-tail 结构。第三，算法上如果把 ratio 当普通非凸 penalty 处理，很容易失去 descent 或只得到特例算法。

以前方法卡在两个地方：一是大量工作只覆盖 \(\ell_1/\ell_2\)、\(\ell_1/\ell_\infty\)、\(\ell_p/\ell_1\) 等特例；二是已有一般 \(\ell_p/\ell_q\) 稳定恢复分析常数较松，compressible signal 的误差界中还会出现显式维度因子。本文的关键矛盾是：想保留 ratio 模型接近 \(\ell_0\) 的尺度不变 inductive bias，同时又要恢复可验证的几何条件和可执行算法。

Motivation

已有路线不够的地方不是“没有 ratio penalty”，而是缺少对一般 \((p,q)\) 的统一可解释理论。ratio 模型经验上对高动态范围、相干矩阵更友好，但理论往往停留在特例或较粗常数；非凸 \(\ell_p\) 更 sparse，但算法 landscape 更差；\(\ell_1\)-based ratio 更好分析，但偏置和 model failure 仍可能明显。

作者的核心观察是：\(\ell_p^p/\ell_q^p\) 的本质优势来自 scale invariance，而 recovery 几何应当由 null space 中向量的“有效稀疏度”决定，即 \(\|h\|_p/\|h\|_q\) 这类 norm-ratio，而不是单独的 \(\ell_p\) 或 \(\ell_q\) 控制。换句话说，真正缺的是把 ratio 的尺度不变结构显式写进 NSP/RIP 分析，而不是再设计一个近似 \(\ell_0\) 的 penalty。

另一个动机是算法层面的：Dinkelbach 是处理分式规划的自然工具，但直接求每步全局 difference minimization 不现实；prox-linear 则给出一个可控的局部替代问题。作者想补的是“fractional structure-aware”算法，而不是把 ratio 展开后交给通用非凸求解器。

Core Idea

核心思想可以概括为：把 ratio 目标的恢复能力归因到 null space 中扰动方向的 norm-ratio 下界，并把有噪误差分析归因到 head/tail 分解下 \(\ell_p,\ell_q,\ell_2\) 之间的局部转换。这个视角比传统 \(\ell_1\)-NSP 更贴近 ratio 模型，因为 ratio 的目标值本身就是某种连续有效 sparsity measure。

理论上它可能有效，是因为对一个 \(s\)-sparse ground truth，任何可行扰动都来自 \(\ker A\)。如果 null space 中的任何非零扰动都在 \(\ell_p/\ell_q\) 意义下“不够 sparse”，那么加入扰动会提高 ratio 目标。这个机制直接解释了 exact recovery 条件中的 \(3^{1/p}s^{1/p-1/q}\)：它要求 null space 远离所有可能伪装成 sparse signal 的方向。

和 prior 的本质区别不是 penalty 形式，而是分析方式。prior 多用特定 \((p,q)\) 的代数性质或较粗 RIP/ROP 不等式；本文试图给出一个对 \(0<p\le1,q>1\) 统一的 norm-ratio 几何框架。最实质的新增信息是 compressible case 中的 block-local norm conversion：它把旧分析中的全维度 \(n^{1/q-1/2}\) 替换成由 \(k,t\) 控制的局部因子，这是一个真正有迁移价值的 proof trick。

Method

第一，local optimality 用 \(\ell_p\)-NSP 加局部扰动展开来证明 sparse point 是 strict local minimizer。这里 GNRC \(\kappa_{p,q}(x_0)\) 的作用是刻画 \(p=1\) 时动态范围对局部条件的影响；对 \(p<1\)，由于 \(|t|^p\) 在零附近更尖，局部稀疏促进更强，因此标准 \(\ell_p\)-NSP 已足够。这部分解决的是非凸目标是否至少在正确稀疏点附近有正确几何。

第二，uniform exact recovery 用 null-space norm-ratio 下界替代 signal-dependent local 条件。证明机制很直接：用 \(\ell_p^p\) 的次可加性给分子下界，用 \(\ell_q\) 三角不等式给分母上界，再用 sparse norm inequality 控制 ground truth 与 perturbation 的 ratio。它带来的核心变化是把“所有 sparse signal 可恢复”变成一个对 \(\ker A\) 的统一有效稀疏度排斥条件。

第三，sample complexity 只在 \(p=1\) 下展开。对 \(q\ge2\)，通过 sub-Gaussian matrix deviation 在 \(\ell_1\)-ball 上给出 \(\|h\|_1/\|h\|_2\) 下界，再用 \(\|h\|_q\le\|h\|_2\)。对 \(1<q<2\)，用 RIP implies robust NSP 加 Stechkin inequality。这里的关键不是 tightness，而是把 deterministic norm-ratio condition 转为 probabilistic sufficient condition。

第四，stable recovery 分两块。exact \(k\)-sparse 情况下，作者围绕 Lemma 5.1 的 head-tail inequality，引入辅助方程零点 \(z_0\) 控制 \(\|h_{-max(k)}\|_q/\|h_{max(k)}\|_q\)，再结合 sparse convex decomposition 得到更松的 RIP 条件和更小误差常数。compressible 情况下，核心是 block decomposition：每个 tail block 只用自己的 cardinality 做 \(\ell_q\)-\(\ell_2\) 转换，从而避免旧工作对整个 \(h\) 使用维度相关不等式。

第五，算法用 prox-linear Dinkelbach。Dinkelbach 更新 \(\alpha_k=\|x^k\|_p^p/\|x^k\|_q^p\)，每步最小化 \(h(x)-\langle \alpha_k\nabla \|x^k\|_q^p,x\rangle+\frac\beta2\|x-x^k\|^2\)。这解决的是分式目标下降难控的问题；prox 项提供 sufficient decrease，线性化分母避免直接处理非凸 difference。

Key Insight / Why It Works

最重要的 insight 是：ratio sparsity 的 recovery 条件应该看 null space 的 ratio geometry，而不是单独看某个 norm 的 NSP。\(\|h\|_p/\|h\|_q\) 本质上是 continuous effective support size；如果 null space 中不存在 effective support size 小的方向，任何可行扰动都会让解变得“不够 sparse”，从而 exact recovery。这个解释比单纯写 RIP 常数更接近模型本身。

第二个真正有效的点是 block-localization。旧分析在 \(1<q<2\) 时用 \(\|h\|_q\le n^{1/q-1/2}\|h\|_2\)，这在 compressed sensing 中非常粗，因为误差向量全维度可能很大，但 tail block 的有效自由度其实由排序分块控制。本文把 norm conversion 下放到每个 block，是去掉维度依赖的关键。这不是 scaling，而是 proof geometry 的改进。

第三，\(p<1\) 的优势在理论和实验中都来自更强的 near-zero sparsity bias。局部最优性里 \(\delta_r^{1-p}\to0\) 使得 \(p<1\) 比 \(p=1\) 更容易压制支撑外小扰动；实验里中等 \(p\) 更好也符合这个机制。但太小的 \(p\) 会让 landscape 更坏，algorithm failure 增加。因此经验最优不是越非凸越好，而是 sparsity bias 和 optimization tractability 的折中。

哪些可能只是辅助？RIP 条件相对 Zhu et al. 的改善主要来自不等式常数重排和更紧 tail bound，属于实质但偏 analysis-level 的增益；是否转化为真实 phase transition 改善，实验没有直接验证。Dinkelbach-prox-linear 的框架合理，但内层 ADMM、初始化和 continuation 对结果影响可能很大，文中没有充分隔离这些因素。实验增益很可能同时来自模型参数选择和 solver tuning，而不完全是理论条件变松。

这篇不是 retrieval、memory reuse、data coverage 或 test-time compute 型工作；核心是 better inductive bias 加 proof-level geometry refinement。所谓 scalability 也不是计算规模上的显著扩展，而是理论覆盖从特例扩到一般 \((p,q)\)，以及 compressible bound 从显式维度依赖变成局部 sparsity 参数依赖。

Relation To Prior Work

最接近的是 \(\ell_1/\ell_2\)、\(\ell_1/\ell_\infty\)、\(\ell_p/\ell_1\)、SPOQ、q-ratio sparsity/CMSV，以及 Zhu et al. 2026 的 \(\ell_p/\ell_q\) RIP/ROP 稳定恢复。谱系上它属于 scale-invariant nonconvex sparse recovery，而不是 separable nonconvex penalty 或 convex relaxation。

和 \(\ell_1/\ell_2\) 路线相比，本文把 denominator 从 \(2\)-norm 推广到任意 \(q>1\)，同时允许 numerator 非凸 \(p<1\)。这带来更灵活的 sparsity/dynamic-range bias，但也牺牲了很多特例中的闭式 proximal 和较干净几何。

和 Zhu et al. 的真正差异在于三点：第一，加入 exact recovery 的 local/uniform deterministic 条件，而不仅是 noisy stable recovery；第二，\(k\)-sparse RIP 条件通过 \(\Psi\) 和 \(z_0\) 的更紧 tail 控制弱化旧界，且证明 \(p<1\) 时严格更宽；第三，compressible case 用 block-local estimate 移除显式 \(n\) 因子。这些是实质创新。

看似新的部分中，Dinkelbach 思路本身并不新，prox-linear 也不是新算法范式；新意在于把它们拼到一般 \(\ell_p^p/\ell_q^p\) 受约束 ratio 上，并给出外层 descent/cluster criticality。采样复杂度部分对 \(p=1\) 是自然延伸，更多是把 deterministic condition 接到 sub-Gaussian/RIP 标准工具上，创新性弱于 block-local stable recovery 分析。

Dataset / Evaluation

实验覆盖的是 synthetic compressed sensing：相关 Gaussian matrix 和 oversampled DCT coherent dictionary；信号是高动态范围 sparse vector。这个设置和论文 claim 是对齐的，因为 ratio 模型本来就主打 high dynamic range 和 coherent sensing 下的稀疏恢复。

但 evaluation 的外推范围有限。没有真实应用数据，没有大规模系统测试，也没有复杂噪声模型下的充分验证。实验主要证明：在作者选择的 synthetic regime 里，中等非凸 \((p,q)\) 和 DLPA solver 比若干 ratio baseline 更稳。它并不能证明理论界 sharp，也不能证明算法对任意 initialization 或任意 coherent matrix 都可靠。

比较中有一个好的设计：区分 model failure 和 algorithm failure。这能帮助判断失败来自目标函数本身还是求解器。但这个分类仍依赖最终返回点和 objective comparison，不能完全排除局部极小、内层未收敛、初始化偏置等因素。文中未充分说明不同 baseline 的调参公平性和计算预算是否完全等价，因此算法层面的优势归因仍需谨慎。

Limitation

第一，核心理论仍然是 sufficient condition。null-space ratio 条件和 RIP/ROP 条件是否接近必要条件，文中没有证明；常数 \(3^{1/p}\)、各类 \(a_p\)、\(\Psi\) 可能仍偏保守。

第二，最有经验价值的 \(0<p<1\) 区间缺少随机采样复杂度。作者明确只对 \(p=1\) 做 sub-Gaussian sample complexity，因为非凸 \(\ell_p\) ball 的 Gaussian width 更难。这意味着理论最完整的区域并不是实验最强的区域。

第三，算法收敛结论依赖较强假设：迭代有界、\(\nabla\|x\|_q^p\) 在访问区域 Lipschitz、prox-linear 子问题被精确求解、\(\beta>\bar\alpha L_s\)。尤其当 \(1<q<2\) 且坐标接近零时，Lipschitz 条件并不自动成立。实际实现用 ADMM/GST 近似求子问题，理论没有完全覆盖 inexact inner solve。

第四，scale-invariant ratio 本身会带来非凸 landscape。实验中小 \(p\) 的 algorithm failure 很高，说明模型越接近 \(\ell_0\)，优化越不稳定。论文没有提供全局收敛或 basin-of-attraction 分析，因此实际成功高度依赖初始化和 continuation。

第五，实验增益归因不清。\((p,q)=(0.7,1.5)\) 的好表现可能来自模型 bias，也可能来自该参数下 solver landscape 更温和；baseline 是否同等优化充分，文中未充分说明。不能把实验曲线直接解读为理论 recovery 条件的优势。

Takeaway

• 1. 对 scale-invariant sparse recovery，正确的几何对象是 null-space 的 norm-ratio，而不是单个 norm 的 NSP/RIP；这个视角可以迁移到其他 ratio 或 normalized penalty。
• 2. compressible recovery 分析中，避免全向量 norm conversion、改用 ordered block-local conversion，是一个很有价值的 proof pattern；它能系统性移除不必要的 ambient dimension factor。
• 3. 非凸程度存在最优中间区间：\(p<1\) 提供更强 sparsity bias，但太小会导致优化失败；未来真正有用的是 adaptive \((p,q)\) 和 solver-aware theory，而不是继续推更极端的 \(p\to0\)。
• 4. 这篇把 \(\ell_p^p/\ell_q^p\) 从经验 ratio heuristic 往统一理论框架推进了一步，但算法全局性、采样 sharpness 和真实应用泛化还没有解决。

一句话总结

这篇论文是 scale-invariant nonconvex sparse recovery 路线中的一次系统化推进：它没有发明全新 penalty，而是把一般 \(\ell_p^p/\ell_q^p\) ratio 的恢复几何、稳定误差界和 Dinkelbach 型求解框架统一到一个更干净的 norm-ratio 分析框架中。