signed

QiShunwang

“诚信为本、客户至上”

UA MATH567 高维统计专题1 稀疏信号及其恢复5 LASSO的估计误差

2021/6/9 0:47:49   来源:

UA MATH567 高维统计专题1 稀疏信号及其恢复5 LASSO的估计误差

    • Signal Recovery Noisy Setting
    • LASSO的估计误差

Signal Recovery Noisy Setting

前四讲算是把无噪声的情况讨论得差不多了,这一讲开始我们讨论含噪声的稀疏信号恢复问题。假设observations是
y = A x ∗ + w y=Ax^*+w y=Ax+w

其中 A ∈ R n × d A \in \mathbb{R^{n \times d}} ARn×d是design matrix, x ∗ ∈ R d x^* \in \mathbb{R}^d xRd是true signal, w w w是noise;现在的问题是我们知道 y y y A A A,想要得到真实信号的一个估计量 x ^ \hat x x^;关于这个问题有三种等价的分析框架:

Penalized Least Square
min ⁡ x    1 2 n ∥ y − A x ∥ 2 2 + λ n ϕ ( x ) \min_x \ \ \frac{1}{2n}\left\| y -Ax \right\|_2^2+\lambda_n\phi(x) xmin  2n1yAx22+λnϕ(x)

其中 λ n \lambda_n λn是regularization parameter, ϕ ( x ) \phi(x) ϕ(x)是penalty function, 1 2 n ∥ y − A x ∥ 2 2 \frac{1}{2n}\left\| y -Ax \right\|_2^2 2n1yAx22是least square loss:

  1. ϕ ( x ) = ∥ x ∥ 1 \phi(x)=\left\| x \right\|_1 ϕ(x)=x1: LASSO
  2. ϕ ( x ) = ∥ x ∥ 2 \phi(x)=\left\| x \right\|_2 ϕ(x)=x2: Ridge regression
  3. ϕ ( x ) = η ∥ x ∥ 1 + ( 1 − η ) ∥ x ∥ 2 \phi(x)=\eta \left\| x\right\|_1+(1-\eta)\left\| x\right\|_2 ϕ(x)=ηx1+(1η)x2: Elastic net

此外还有adaptive lasso, adaptive elastic net, SCAD (smoothly clipped absolute deviations), MCP (minimax concave penalty)等一系列通过设计penalty function得到能实现不同目的的penalized least square模型;

Constraint Least Square
min ⁡ x    1 2 n ∥ y − A x ∥ 2 2 s . t .    ϕ ( x ) ≤ R \min_x \ \ \frac{1}{2n}\left\| y -Ax \right\|_2^2 \\ s.t. \ \ \phi(x) \le R xmin  2n1yAx22s.t.  ϕ(x)R

这与Penalized Least Square是完全等价的。

Relaxed Basis Pursuit或者Basis Pursuit Denoising

min ⁡ x    ϕ ( x ) s . t .    1 2 n ∥ y − A x ∥ 2 2 ≤ b 2 \min_x \ \ \phi(x) \\ s.t. \ \ \frac{1}{2n}\left\| y -Ax \right\|_2^2 \le b^2 xmin  ϕ(x)s.t.  2n1yAx22b2

这种一般在EECS的文献中比较常见,统计学一般用前两种(主要是第一种)框架。


LASSO的估计误差

在noisy setting下,full recovery自然是不可能的了,但我们希望估计误差 ∥ x ^ − x ∗ ∥ \left\| \hat x - x^*\right\| x^x尽可能小,下面我们讨论一下LASSO估计误差的下界。

在第二讲推导 L 1 L_1 L1-minimization时,为了构造 L 0 L_0 L0-norm的scale-invariant性质,我们引入了一个凸锥
C ( S ) = { R d : ∥ Δ S C ∥ 1 ≤ ∥ Δ S ∥ 1 } C(S)=\{\mathbb{R}^d:\left\| \Delta_{S^C} \right\|_1 \le \left\| \Delta_{S} \right\|_1\} C(S)={Rd:ΔSC1ΔS1}

其中 S ⊂ { 1 , 2 , ⋯   , d } S \subset \{1,2,\cdots,d\} S{1,2,,d}是一个指标集;在讨论LASSO估计量时,我们需要再对这个凸锥做一点修正,考虑到LASSO估计量的特点是 L 1 L_1 L1-norm作为penalty提供sparse solution,没有被shrink to zero的那些observation会被proportional shrink,据此我们引入一个新的凸锥
C α ( S ) = { R d : ∥ Δ S C ∥ 1 ≤ α ∥ Δ S ∥ 1 } C_{\alpha}(S)=\{\mathbb{R}^d:\left\| \Delta_{S^C} \right\|_1 \le \alpha \left\| \Delta_{S} \right\|_1\} Cα(S)={Rd:ΔSC1αΔS1}

Restricted Eigenvalue Condition
称design matrix A A A满足Restricted Eigenvalue Condition over index set S S S with parameter ( κ , α ) (\kappa,\alpha) (κ,α)如果
1 n ∥ A Δ ∥ 2 2 ≥ κ ∥ Δ ∥ 2 2 , ∀ Δ ∈ C α ( S ) \frac{1}{n}\left\| A \Delta\right\|_2^2 \ge \kappa \left\| \Delta \right\|_2^2,\forall \Delta \in C_{\alpha}(S) n1AΔ22κΔ22,ΔCα(S)

通常将这个条件简单记为 R E ( κ , α ) RE(\kappa,\alpha) RE(κ,α)

评注
如果 κ > 0 \kappa>0 κ>0,则 R E ( κ , α ) RE(\kappa,\alpha) RE(κ,α)说明
1 n ∥ A Δ ∥ 2 2 ≥ κ ∥ Δ ∥ 2 2 > 0 , ∀ Δ ∈ C α ( S ) ∖ { 0 } \frac{1}{n}\left\| A \Delta\right\|_2^2 \ge \kappa \left\| \Delta \right\|_2^2>0,\forall \Delta \in C_{\alpha}(S) \setminus \{0\} n1AΔ22κΔ22>0,ΔCα(S){0}

这说明
C 1 ( S ) ∩ N u l l ( A ) = { 0 } C_{1}(S) \cap Null(A) = \{0\} C1(S)Null(A)={0}

也就是Restricted Null Property成立。

定理 如果 s u p p ( x ∗ ) = S supp(x^*)=S supp(x)=S ∣ S ∣ = s |S|=s S=s A A A满足 R E ( κ , α ) RE(\kappa,\alpha) RE(κ,α) over S S S:

  1. 在Penalized Least Square形式的LASSO中,如果 λ n ≥ 2 ∥ A T w n ∥ ∞ \lambda_n \ge 2 \left\| \frac{A^Tw}{n}\right\|_{\infty} λn2nATw ∥ x ^ − x ∗ ∥ 2 ≤ 3 κ s λ n \left\| \hat x-x^* \right\|_2 \le \frac{3}{\kappa}\sqrt{s}\lambda_n x^x2κ3s λn因此最小的上界为 6 κ s ∥ A T w n ∥ ∞ \frac{6}{\kappa}\sqrt{s} \left\| \frac{A^Tw}{n}\right\|_{\infty} κ6s nATw
  2. 在Constraint Least Square形式的LASSO中,如果 R = ∥ x ∗ ∥ 1 R=\left\| x^*\right\|_1 R=x1,则 ∥ x ^ − x ∗ ∥ 2 ≤ 4 κ s ∥ A T w n ∥ ∞ \left\| \hat x - x^* \right\|_2 \le \frac{4}{\kappa}\sqrt{s} \left\| \frac{A^Tw}{n}\right\|_{\infty} x^x2κ4s nATw
  3. 在Relaxed Basis Pursuit形式的LASSO中,如果 b 2 ≥ ∥ w ∥ 2 2 2 n b^2 \ge \frac{\left\| w \right\|_2^2}{2n} b22nw22,则 ∥ x ^ − x ∗ ∥ 2 ≤ 4 κ s λ n ∥ A T w n ∥ ∞ + 2 κ b 2 − ∥ w ∥ 2 2 2 n \left\| \hat x - x^* \right\|_2 \le \frac{4}{\kappa}\sqrt{s}\lambda_n \left\| \frac{A^Tw}{n}\right\|_{\infty}+\frac{2}{\sqrt{\kappa}}\sqrt{b^2-\frac{\left\| w\right\|_2^2}{2n}} x^x2κ4s λnnATw+κ 2b22nw22 因此,当 b 2 = ∥ w ∥ 2 2 2 n b^2 = \frac{\left\| w \right\|_2^2}{2n} b2=2nw22时,上界最小,为 4 κ s ∥ A T w n ∥ ∞ \frac{4}{\kappa}\sqrt{s} \left\| \frac{A^Tw}{n}\right\|_{\infty} κ4s nATw

评注
从上面这几个结果来看, κ \kappa κ越大(restricted eigenvalue condition越严格), s s s越小(信号越系数),估计量的误差就越小;另外,上界的大小主要由 ∥ A T w n ∥ ∞ \left\| \frac{A^Tw}{n}\right\|_{\infty} nATw决定,其中 w w w是noise term;如果 A A A是固定的, w ∼ i i d N ( 0 , σ 2 ) w \sim_{iid} N(0,\sigma^2) wiidN(0,σ2),假设(标准化design matrix的列向量)
∥ A j ∥ 2 n = 1 \frac{\left\|A_j \right\|_2}{n}=1 nAj2=1

A A A满足 R E ( κ , α ) RE(\kappa,\alpha) RE(κ,α),则
A T w n ∼ N ( 0 , A T A n 2 σ 2 ) \frac{A^Tw}{n} \sim N(0,\frac{A^TA}{n^2}\sigma^2) nATwN(0,n2ATAσ2)

A T w n \frac{A^Tw}{n} nATw中每个元素的边缘分布为 N ( 0 , σ 2 / n ) N(0,\sigma^2/n) N(0,σ2/n),因此 A T w n \frac{A^Tw}{n} nATw L ∞ L_{\infty} L-norm其实就是 d d d N ( 0 , σ 2 / n ) N(0,\sigma^2/n) N(0,σ2/n)的最大值;根据UA MATH567 高维统计III 随机矩阵12 整数环上的区间的应用:拐点侦测的统计量及假设检验中介绍的最大值的概率不等式,
P ( ∥ A T w n ∥ ∞ ≥ σ ( 2 log ⁡ d n + δ ) ) ≤ 2 e − n δ 2 2 P(\left\| \frac{A^Tw}{n}\right\|_{\infty} \ge \sigma(\sqrt{\frac{2 \log d}{n}}+\delta)) \le 2e^{-\frac{n\delta^2}{2}} P(nATwσ(n2logd +δ))2e2nδ2

1 n ≲ δ \frac{1}{\sqrt{n}} \lesssim \delta n 1δ,则 n δ 2 → ∞ n\delta^2 \to \infty nδ2,从而以上概率的上界为0,这说明 ∥ A T w n ∥ ∞ \left\| \frac{A^Tw}{n}\right\|_{\infty} nATw依概率1满足
∥ A T w n ∥ ∞ = O ( s log ⁡ d n ) \left\| \frac{A^Tw}{n}\right\|_{\infty} =O(\sqrt{\frac{s\log d}{n}}) nATw=O(nslogd )

这是一个非常重要的结果,这时到目前为止的Frequentist Optimality;

证明第二条结论
考虑
min ⁡ x    1 2 n ∥ y − A x ∥ 2 2 s . t .    ∥ x ∥ 1 ≤ R = ∥ x ∗ ∥ 1 \min_x \ \ \frac{1}{2n}\left\| y -Ax \right\|_2^2 \\ s.t. \ \ \left\| x\right\|_1 \le R=\left\|x^* \right\|_1 xmin  2n1yAx22s.t.  x1R=x1

假设 θ ^ \hat \theta θ^是它的解, x ∗ x^* x是true signal,定义 Δ = x ^ − x ∗ \Delta=\hat x - x^* Δ=x^x;根据解的定义,
∥ y − A x ^ ∥ 2 2 ≤ ∥ y − A x ∗ ∥ 2 2 ∥ A x ∗ + w − A x ^ ∥ 2 2 ≤ ∥ w ∥ 2 2 ∥ w − A Δ ∥ 2 2 ≤ ∥ w ∥ 2 2 ∥ w ∥ 2 2 + ∥ A Δ ∥ 2 2 − 2 w T A Δ ≤ ∥ w ∥ 2 2 ∥ A Δ ∥ 2 2 ≤ 2 w T A Δ \left\| y -A\hat x \right\|_2^2 \le \left\| y -Ax^* \right\|_2^2 \\ \left\| Ax^* +w-A\hat x \right\|_2^2 \le \left\| w \right\|_2^2 \\ \left\| w-A\Delta \right\|_2^2 \le \left\| w \right\|_2^2 \\ \left\| w \right\|_2^2 +\left\|A\Delta \right\|_2^2-2w^TA\Delta \le \left\|w \right\|_2^2 \\ \left\|A\Delta \right\|_2^2 \le 2w^TA\Delta yAx^22yAx22Ax+wAx^22w22wAΔ22w22w22+AΔ222wTAΔw22AΔ222wTAΔ

根据Cauchy不等式
∥ A Δ ∥ 2 2 n ≤ 2 w T A Δ n ≤ 2 ∥ A T w n ∥ ∞ ∥ Δ ∥ 1 \frac{ \left\|A\Delta \right\|_2^2}{n} \le \frac{2w^TA\Delta}{n} \le 2\left\| \frac{A^Tw}{n}\right\|_{\infty} \left\| \Delta \right\|_1 nAΔ22n2wTAΔ2nATwΔ1

下面我们说明 Δ ∈ C 1 ( S ) ⊂ C 3 ( S ) \Delta \in C_1(S) \subset C_3(S) ΔC1(S)C3(S):因为 x ∗ x^* x是true signal,所以
∥ x S ∗ ∥ = ∥ x ∗ ∥ 1 = R ≥ ∥ x ^ ∥ 1 = ∥ x ∗ + Δ ∥ 1 = ∥ x S ∗ + Δ S ∥ 1 + ∥ Δ S C ∥ 1 ≥ ∥ x S ∗ ∥ − ∥ Δ S ∥ 1 + ∥ Δ S C ∥ 1 \left\| x^*_S \right\| = \left\|x^* \right\|_1=R \ge \left\| \hat x\right\|_1 = \left\| x^*+\Delta\right\|_1 \\= \left\| x^*_S+\Delta_S\right\|_1+\left\| \Delta_{S^C} \right\|_1 \ge \left\| x^*_S \right\|-\left\| \Delta_{S} \right\|_1+\left\| \Delta_{S^C} \right\|_1 xS=x1=Rx^1=x+Δ1=xS+ΔS1+ΔSC1xSΔS1+ΔSC1

所以
∥ Δ S C ∥ 1 ≤ ∥ Δ S ∥ 1 \left\| \Delta_{S^C} \right\|_1 \le \left\| \Delta_{S} \right\|_1 ΔSC1ΔS1

也就是说 Δ ∈ C 1 ( S ) \Delta \in C_1(S) ΔC1(S);根据 R E ( κ , 1 ) RE(\kappa,1) RE(κ,1)
∥ Δ ∥ 2 2 ≤ 1 n κ ∥ A Δ ∥ 2 2 ≤ 2 κ ∥ A T w n ∥ ∞ ∥ Δ ∥ 1 \left\| \Delta \right\|_2^2 \le \frac{1}{n\kappa}\left\| A \Delta\right\|_2^2 \le \frac{2}{\kappa}\left\| \frac{A^Tw}{n}\right\|_{\infty} \left\| \Delta \right\|_1 Δ22nκ1AΔ22κ2nATwΔ1

其中
∥ Δ ∥ 1 = ∥ Δ S ∥ 1 + ∥ Δ S C ∥ 1 ≤ 2 ∥ Δ S ∥ 1 ≤ 2 s ∥ Δ S ∥ 2 \left\| \Delta \right\|_1=\left\| \Delta_S \right\|_1+\left\| \Delta_{S^C} \right\|_1 \le 2\left\| \Delta_S \right\|_1 \le 2 \sqrt{s}\left\| \Delta_S \right\|_2 Δ1=ΔS1+ΔSC12ΔS12s ΔS2

代入上式中可得
∥ Δ ∥ 2 ≤ 4 κ s ∥ A T w n ∥ ∞ \left\| \Delta \right\|_2 \le \frac{4}{\kappa}\sqrt{s} \left\| \frac{A^Tw}{n}\right\|_{\infty} Δ2κ4s nATw