受限特征值与稀疏可识别性

无约束的最小特征值遍历所有方向。高维时 $p>n$，总有某个非零向量落在 $\ker X$，所以全空间最小特征值是零。稀疏分析并不要求每条方向都能被观察到，而是先用惩罚比较证明误差不能主要堆在真支持之外，再在剩余的锥上检查预测能否控制参数。

这套顺序有两项独立责任。基本不等式负责证明“误差属于哪里”，设计条件负责证明“在这片区域内，小预测意味着多小的参数误差”。若把近似解当作精确解，第一项责任已经失效，第二项再漂亮也不能补上。

常数之间能比较什么 ​

对任意 $h$，Cauchy–Schwarz 不等式理路Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积，且等号精确刻画线性相关。给 $\Vert h_S{\Vert }_1\le \sqrt{s}\Vert h_S{\Vert }_2$。同时 $\Vert h_S{\Vert }_2\le \Vert h{\Vert }_2$，所以

若全局最小特征值为 ${\lambda }_{min}(\mathrm{\Gamma })>0$，则 ${\alpha }^2\ge {\lambda }_{min}(\mathrm{\Gamma })$。反过来不成立：受限锥可以完全避开全局零空间。

对固定有限 $s,c$，锥上还有 $\Vert h{\Vert }_2^2\le (1+c^{2}s)\Vert h_S{\Vert }_2^2$ 和 $\Vert h_S{\Vert }_1^2\ge \Vert h_S{\Vert }_2^2$，因此

所以本页三个固定支持常数是否严格为正是等价的，但其数值以及随 $s,n$ 变化的统一下界并不相同。拿一个 $\kappa$ 界直接当作同数值的全 ${\ell }_2$ 界，会丢掉这些因子。文献中更大支持集版本的 RE 还改变了定义域，不能只靠这里的比较替换。

从锥上的不等式走到误差界 ​

令 $q=\Vert Xh{\Vert }_2/\sqrt{n}$、$a=\Vert h_S{\Vert }_1$、$b=\Vert h_{S^c}{\Vert }_1$。精确解满足 $q^2+\lambda b\le 3\lambda a$，而兼容条件给 $a\le \sqrt{s}q/{\varphi }_3$。因此

若 $q=0$，${\varphi }_3>0$ 又给 $h=0$；若 $q>0$，除以 $q$ 得到式(4)的预测界。再用 $a+b\le 4a$，得到 $\Vert h{\Vert }_1\le 4\sqrt{s}q/{\varphi }_3\le 12\lambda s/{\varphi }_3^2$。平方在最后的分母出现两次来源：一次用设计控制 $a$，一次控制 $q$。

若改用 ${\kappa }_3>0$，同样推理给 $\Vert h_S{\Vert }_2\le 3\lambda \sqrt{s}/{\kappa }_3^2$，其中只控制支持内欧氏误差。若用 ${\alpha }_3>0$，则直接以 $a\le \sqrt{s}\Vert h{\Vert }_2$ 得

这也解释了为什么必须先声明使用哪一种常数。

两列相关性可以完整算出 ​

取

锥内非零向量可写成 $h=h_1(1,t)$，$|t|\le c$。支持分母等于 $h_1^2$，所以

最小值在 $t=-r$ 取得。全向量分母还要除以 $1+t^2$；最小特征方向 $t=-\mathrm{sign}(r)$ 属于锥，因此

当 $r=1/2$ 时，${\kappa }^2={\varphi }^2=3/4$，${\alpha }^2=1/2$。取无噪声 ${\beta }^0=(1,0)$、$\lambda =1/4$，唯一 Lasso 解为 $(3/4,0)$；实际 $q^2=1/16$、$\Vert h{\Vert }_1=\Vert h{\Vert }_2=1/4$。式(4)给 $q^2\le 3/4$、$\Vert h{\Vert }_1\le 4$，式(6)给 $\Vert h{\Vert }_2\le 3/2$。界很保守，但方向和定标正确。

当 $r=1$，$h=(1,-1)$ 既在锥内又满足 $Xh=0$，三个常数全为零。此时两种一稀疏真参数 $(1,0)$ 和 $(0,1)$ 产生相同响应分布。不是把优化再做精确一些就能恢复哪一列真正非零。

全局奇异不一定破坏指定支持 ​

考虑三个单位尺度列，其 Gram 矩阵为

第二、第三列重复，故 ${\lambda }_{min}(\mathrm{\Gamma })=0$。但任意 $h$ 都满足 $h^{\mathsf{T}}\mathrm{\Gamma }h=h_1^2+(h_2+h_3{)}^2\ge h_1^2$，取 $h=(1,0,0)$ 又达到等号，所以对任意有限 $c$ 都有 ${\kappa }^2={\varphi }^2=1$。第一列的稀疏信号仍可得到式(4)的控制。

这并非“该矩阵对所有一稀疏信号都好”。若改成 $S=\{2\}$、$c\ge 1$，向量 $(0,1,-1)$ 就在锥中，受限常数变成零。固定支持保证与统一稀疏保证的量词在这里有实际区别。

可识别性、等距性与支持选择的边界 ​

若对每个至多 $s_0$ 的支持都有 $\kappa (S,c)>0$，且 $c\ge 1$，就不可能有非零的至多 $2s_0$ 稀疏向量 $v$ 满足 $Xv=0$。证明是把其支持分成大小至多 $s_0$ 的两部分，选 ${\ell }_1$ 质量较大的一半作为 $S$，于是 $v\in C(S,1)\subseteq C(S,c)$，与正的 $\kappa$ 矛盾。因此两个至多 $s_0$ 稀疏参数不能产生相同均值。

受限等距性质则要求对每个至多 $k$ 稀疏的 $v$ 有 $(1-d_k)\Vert v{\Vert }_2^2\le \Vert Xv{\Vert }_2^2/n\le (1+d_k)\Vert v{\Vert }_2^2$。它同时要求上下界，而且检验的是严格稀疏向量；本页的锥允许许多小的非零坐标。适当阶数和常数的等距条件可以推出 Lasso 所需的受限界，但不能仅凭两个名称都含“受限”就视为同一条件。

即便 $\mathrm{\Gamma }$ 全局正定，也未必让原始 Lasso 选中真支持。支持恢复理路Lasso 支持恢复与不可表示条件Lasso support recovery · Lasso sign consistency · Lasso irrepresentable condition用活动集上的显式候选和非活动集的严格对偶余量证明符号恢复，区分可识别性、参数小误差、变量筛选和坐标推断。给出一个最小特征值为 $1-3\sqrt{2}/5>0$ 的三列设计，Lasso 却持续选择额外变量。受限界说明误差可以变小，支持选择还要防止零坐标上残留任何非零值。

近似解：把松弛量与锥宽一起处理 ​

假定真支持非空，噪声事件与基本不等式成立，候选的归一化目标容差为 $\delta \ge 0$。现在有

令 ${\varphi }_4=\varphi (S,4)>0$。分两种情况，而不是直接宣称 $h\in C(S,3)$：

• 若 $a\ge 2\delta /\lambda$，则 $b\le 3a+2\delta /\lambda \le 4a$，所以 $h\in C(S,4)$。又 $q^2\le 4\lambda a$，兼容条件给 $q\le 4\lambda \sqrt{s}/{\varphi }_4$，继而 $a+b\le 5a\le 20\lambda s/{\varphi }_4^2$
• 若 $a<2\delta /\lambda$，式(7)直接给 $q^2<8\delta$、$b<8\delta /\lambda$、$a+b<10\delta /\lambda$，无需再调用受限条件

两种情况合并得到

第一种情况下如果 $q=0$，正的兼容常数先给 $h=0$，无须除以零。若 $S=\varnothing$，不用定义式(2)的常数；基本不等式直接给 $q^2+\lambda \Vert h{\Vert }_1\le 2\delta$。

例如正交设计 $\mathrm{\Gamma }=I_2$、$S=\{1\}$、$\lambda =0.1$、$\delta =0.001$，有 ${\varphi }_4^2=1$。式(8)给 $q^2\le 0.16$、$\Vert h{\Vert }_1\le 2$；较小的优化项分别为 $0.008$ 和 $0.1$。这不是预测误差必然为 $0.16$，而是此组条件可认证的上界。随着 $\delta$ 降低，统计项不会跟着消失。

怎样接到坐标推断 ​

去偏 Lasso理路去偏 Lasso 与坐标置信区间Debiased Lasso · de-biased Lasso · de-sparsified Lasso · desparsified Lasso · 去稀疏 Lasso用近似逆矩阵修正 Lasso 的残差得分，将坐标误差拆成高斯主项与可控制的乘积余项，并据此构造置信区间。需要初始总误差 $L=\Vert \tilde{\beta }-{\beta }^0{\Vert }_1$ 的控制。本页式(8)提供一种有条件的上界；把它乘上该页可计算的逆矩阵行缺陷 ${\delta }_j$，再与 $\sigma \sqrt{v_j/n}$ 比较，就能判断余项是否足够小。这里优化容差 $\delta$ 与逆行缺陷 ${\delta }_j$ 是不同量。

若列尺度有界、次高斯噪声使 $\lambda$ 取 $\sqrt{\log p/n}$ 量级，并且相关兼容常数有统一正下界，精确解的预测界是 $s\log p/n$ 量级，${\ell }_1$ 界是 $s\sqrt{\log p/n}$ 量级。式(8)说明近似解还须把 $\delta$ 控制在相容尺度，不能只报告迭代次数。验证统一设计条件本身可能很困难；这些公式并不宣称已提供高维矩阵上廉价的全支持认证算法。

无噪声欠定解码需要再指定恢复规则 ​

本页的稀疏可识别性排除两个短支持参数产生同一观测，却尚未说明一个可计算的规则会返回哪一个可行点。基追踪的稀疏恢复证书理路基追踪的稀疏恢复证书Basis pursuit recovery certificate · RIP certificate for sparse recovery · 基追踪与受限等距恢复从无噪声欠定观测建立 ℓ1 解码器，用完整分块证明和可精算的单纯形矩阵分开认证优化最优性与统一稀疏恢复。给出 $min\{\Vert z{\Vert }_1:Az=y\}$、常数一误差锥和受限奇异值的完整分块证明；其七乘八单纯形矩阵可以对所有一稀疏输入统一认证。另一份二乘三矩阵的所有二列都独立，甚至 ${\delta }_2<1$，基追踪却偏爱目标 $2/3$ 的错误向量。这里的锥 RE、严格稀疏下界和指定解码器的成功因此仍须分别核对；有噪声 Lasso 的常数三锥及本页全部误差界不因此改变。