关于稀疏性的直觉

2025-11-04

对于高维空间，有一个著名的论断是这样说的，Rn\mathbb{R}^n中的两个随机向量正交概率随n的增加趋近于一，这当然是一个非正式的说法，我们无意于从概率论的角度讨论它，因为其本身的证明并不困难。但其证明隐含着一个重要的想法，即高维向量总是稀疏的。在这个注记里，我们从一个直觉的想法出发，叙述稀疏性与其若干的讨论，而后再把这些直觉严格定义出来。

“稀疏性”，本质上是这样一个概念，对于Rn\mathbb{R}^n中的向量xx，其在某组基下具有坐标化表示，如果坐标里大部分数的绝对值很小，那么其实决定这个向量的位置的只是那些显著的量，于是record的时候我只需要记录这些显著的量，而不需要记录所有的坐标。就这样一个简单的想法，背后就有两个非常困难的问题。第一个问题就是，对于一组向量，我们要怎么找到这样的一组基？第二个问题是，对于确定的基，我们能不能对需要记录的坐标数的最大值有一个估计？这两个问题都十分有趣，我们这里给出第二个问题的一个直觉表达：我们假定，对于界δ\delta，有膜长约束的n维向量需要记录的坐标数为s(n)，那么s(n)是一个怎样的函数？一个直觉就是，对于确定的膜长约束，s(n)一定增长的比线性慢。于是，我们就需要考虑，如何把这个“慢”体现出来？在数学上，这其实就是建立一个不等式关系。因为我们这里不考虑第一个问题，所以我们直接取标准基。于是，刻画不等式就只需要一个简单的工具，那就是把坐标从大到小排列，这个排列有许多好处，最直接的好处是，我们可以用下标表示s(n)，同时，当我们定义了稀疏性后，我们会知道，重排是一个不改变稀疏性的操作。带着这样的思维，我们可以开始正式的表达。

正式的叙述从定义稀疏性（sparsity）的严格定义开始。 首先，引入记号 [N]:={1,2,…,N}[N] := \{1, 2, \ldots, N\} 并用 card(S)\mathrm{card}(S) 表示集合 SS 的基数（即元素个数）。

定义 1
向量 x∈CN\mathbf{x} \in \mathbb{C}^N 的支撑集是其非零元素的索引集合，即

supp(x):={j∈[N]:xj≠0}.\mathrm{supp}(\mathbf{x}) := \{ j \in [N] : x_j \neq 0 \}.

若向量 x∈CN\mathbf{x} \in \mathbb{C}^N 至多有 ss 个非零分量，则称其为s-稀疏（s-sparse），即

∥x∥0:=card(supp(x))≤s.\|\mathbf{x}\|_0 := \mathrm{card}(\mathrm{supp}(\mathbf{x})) \le s.

习惯上使用的记号 ∥x∥0\|\mathbf{x}\|_0 —— 尽管更准确的写法应为 ∥x∥00\|\mathbf{x}\|_0^0 —— 源自如下极限关系：

∥x∥p:=(∑j=1N∣xj∣p)1/p→p→0∑j=1N1{xj≠0}=card({j∈[N]:xj≠0}).\|\mathbf{x}\|_p := \left( \sum_{j=1}^N |x_j|^p \right)^{1/p} \quad \xrightarrow[p \to 0]{} \quad \sum_{j=1}^N 1_{\{x_j \neq 0\}} = \mathrm{card}(\{ j \in [N] : x_j \neq 0 \}).

定义 2
当 p>0p > 0 时，向量 x∈CN\mathbf{x} \in \mathbb{C}^N 的最佳 ss 项近似的 ℓp\ell_p 误差定义为

σs(x)p:=inf⁡{∥x−z∥p:z∈CN 是 s-稀疏的}.\sigma_s(\mathbf{x})_p := \inf \{ \|\mathbf{x} - \mathbf{z}\|_p : \mathbf{z} \in \mathbb{C}^N \text{ 是 } s\text{-稀疏的} \}.

在 σs(x)p\sigma_s(\mathbf{x})_p 的定义中，下确界由一个 ss-稀疏向量 z∈CN\mathbf{z} \in \mathbb{C}^N 取得，
其非零分量对应于 x\mathbf{x} 中绝对值最大的 ss 个分量。
因此，尽管这样的向量 z\mathbf{z} 可能不唯一，但它取得的下确界与 p>0p > 0 无关。

非正式地说，若向量 x∈CN\mathbf{x} \in \mathbb{C}^N 的最佳 ss 项近似误差随 ss 增加而迅速衰减，
我们称其为可压缩向量（compressible vector）。
根据下述命题，如果 x\mathbf{x} 属于某个较小 p>0p > 0 的单位 ℓp\ell_p 球，则这种情况会发生。

单位 ℓp\ell_p 球定义为：

BpN:={z∈CN:∥z∥p≤1}.B_p^N := \{ \mathbf{z} \in \mathbb{C}^N : \|\mathbf{z}\|_p \le 1 \}.

因此，当 p<1p < 1 时，非凸的球体 BpNB_p^N 可作为可压缩向量的良好模型。

命题 3
对于任意 q>p>0q > p > 0 和任意 x∈CN\mathbf{x} \in \mathbb{C}^N，有

σs(x)q≤1s1/p−1/q∥x∥p.\sigma_s(\mathbf{x})_q \le \frac{1}{s^{1/p - 1/q}} \|\mathbf{x}\|_p.

在证明此命题之前，我们先引入非增重排的概念。

定义 4
向量 x∈CN\mathbf{x} \in \mathbb{C}^N 的非增重排是一个向量 x∗∈RN\mathbf{x}^* \in \mathbb{R}^N，其满足

x1∗≥x2∗≥⋯≥xN∗≥0,x_1^* \ge x_2^* \ge \cdots \ge x_N^* \ge 0,

并存在一个排列 π:[N]→[N]\pi : [N] \to [N] 使得 xj∗=∣xπ(j)∣x_j^* = |x_{\pi(j)}| 对所有 j∈[N]j \in [N] 成立。

命题 3 的证明
若 x∗∈R+N\mathbf{x}^* \in \mathbb{R}_+^N 是向量 x∈CN\mathbf{x} \in \mathbb{C}^N 的非增重排，则有

σs(x)qq=∑j=s+1N(xj∗)q≤(xs∗)q−p∑j=s+1N(xj∗)p≤(1s∑j=1s(xj∗)p)q−pp(∑j=s+1N(xj∗)p)≤1sq/p−1∥x∥pq.\sigma_s(\mathbf{x})_q^q = \sum_{j=s+1}^{N} (x_j^*)^q \le (x_s^*)^{q-p} \sum_{j=s+1}^{N} (x_j^*)^p \le \left( \frac{1}{s} \sum_{j=1}^{s} (x_j^*)^p \right)^{\frac{q-p}{p}} \left( \sum_{j=s+1}^{N} (x_j^*)^p \right) \le \frac{1}{s^{q/p - 1}} \|\mathbf{x}\|_p^q.

结果通过对上式两边取 1/q1/q 次方得到。 □

我们通过寻找不等式

σs(x)q≤cp,qs−1/p+1/q∥x∥p\sigma_s(\mathbf{x})_q \le c_{p,q} s^{-1/p + 1/q} \|\mathbf{x}\|_p

中最小可能的常数 cp,qc_{p,q} 来强化前述命题。
证明的核心是手动求解一个凸优化问题。

定理 5
对于任意 q>p>0q > p > 0 以及任意 x∈CN\mathbf{x} \in \mathbb{C}^N，有不等式

σs(x)q≤cp,qs1/p−1/q∥x∥p\sigma_s(\mathbf{x})_q \le \frac{c_{p,q}}{s^{1/p - 1/q}} \|\mathbf{x}\|_p

其中

cp,q:=[(pq)p/q(1−pq)1−p/q]1/p≤1.c_{p,q} := \left[ \left(\frac{p}{q}\right)^{p/q} \left(1 - \frac{p}{q}\right)^{1 - p/q} \right]^{1/p} \le 1.

值得注意的是，当常取 p=1p = 1 且 q=2q = 2 时，有

σs(x)2≤12s∥x∥1.\sigma_s(\mathbf{x})_2 \le \frac{1}{2\sqrt{s}} \|\mathbf{x}\|_1.

证明。 设 x∗∈R+N\mathbf{x}^* \in \mathbb{R}_+^N 为 x∈CN\mathbf{x} \in \mathbb{C}^N 的非增重排。令
αj:=(xj∗)p,\alpha_j := (x_j^*)^p,
我们将证明与之等价的表述：

α1≥α2≥⋯≥αN≥0,α1+α2+⋯+αN≤1⇒αs+1 q/p+αs+2 q/p+⋯+αN q/p≤cp,q qs q/p−1.\alpha_1 \ge \alpha_2 \ge \cdots \ge \alpha_N \ge 0,\qquad \alpha_1+\alpha_2+\cdots+\alpha_N \le 1 \Rightarrow \alpha_{s+1}^{\,q/p}+\alpha_{s+2}^{\,q/p}+\cdots+\alpha_N^{\,q/p} \le \frac{c_{p,q}^{\,q}}{s^{\,q/p-1}}.

令 r:=q/p>1r := q/p > 1，则目标转化为在下述凸多边形上最大化凸函数

f(α1,α2,…,αN):=αs+1r+αs+2r+⋯+αNrf(\alpha_1,\alpha_2,\ldots,\alpha_N) := \alpha_{s+1}^r + \alpha_{s+2}^r + \cdots + \alpha_N^r

其中

C:={(α1,…,αN)∈RN: α1≥⋯≥αN≥0, α1+⋯+αN≤1}.\mathcal{C} := \{(\alpha_1,\ldots,\alpha_N)\in\mathbb{R}^N:\ \alpha_1\ge\cdots\ge\alpha_N\ge 0,\ \alpha_1+\cdots+\alpha_N\le 1\}.

依照定理 B.16，函数 ff 的最大值在集合 C\mathcal{C} 的某个顶点处取得。
这些顶点由将 (N+1)(N+1) 个不等式约束中的 NN 个改写为等式并与其超平面相交得到。于是有以下情形：

因此

max⁡(α1,…,αN)∈Cf(α1,…,αN)=max⁡s+1≤k≤Nk−skr.\max_{(\alpha_1,\ldots,\alpha_N)\in\mathcal{C}} f(\alpha_1,\ldots,\alpha_N) =\max_{s+1\le k\le N}\frac{k-s}{k^r}.

将 kk 视为连续变量，函数 g(k):=k−skrg(k):=\frac{k-s}{k^r}
在临界点 k∗=rr−1sk^*=\frac{r}{r-1}s 之前单调递增，之后单调递减。于是得到

max⁡(α1,…,αN)∈Cf(α1,…,αN)≤g(k∗)=1r ⁣(1−1r) ⁣r−1 ⁣1s r−1=cp,q q 1s q/p−1.\max_{(\alpha_1,\ldots,\alpha_N)\in\mathcal{C}} f(\alpha_1,\ldots,\alpha_N) \le g(k^*) =\frac{1}{r}\!\left(1-\frac{1}{r}\right)^{\!r-1}\!\frac{1}{s^{\,r-1}} = c_{p,q}^{\,q}\,\frac{1}{s^{\,q/p-1}}.

这即为所求结论。□

—

定义可压缩性的另一种方式是：若向量 x∈CN\mathbf{x}\in\mathbb{C}^N 满足

card({ j∈[N]:∣xj∣≥t })\mathrm{card}\big(\{\,j\in[N]: |x_j|\ge t\,\}\big)

这一“显著分量”（而非非零分量）的数量很小，则称其为可压缩。这自然引出弱 ℓp\ell_p 空间的概念。

定义 6
当 p>0p > 0 时，弱 ℓp\ell_p 空间（weak ℓp\ell_p space）记作 wℓpNw\ell_p^N，它表示复空间 CN\mathbb{C}^N，并配备如下准范数（quasinorm）：

∥x∥p,∞:=inf⁡{M≥0:card({j∈[N]:∣xj∣≥t})≤Mptp, ∀t>0}.\|\mathbf{x}\|_{p,\infty} := \inf\left\{ M \ge 0 : \mathrm{card}\big(\{ j \in [N] : |x_j| \ge t \}\big) \le \frac{M^p}{t^p},\ \forall t > 0 \right\}.

为验证上述定义确实给出了一个准范数，我们需要检查对任意
x,y∈CN\mathbf{x}, \mathbf{y} \in \mathbb{C}^N 和任意 λ∈C\lambda \in \mathbb{C}，是否满足以下性质：

  1. 若 ∥x∥=0\|\mathbf{x}\| = 0，则 x=0\mathbf{x} = 0；
  2. ∥λx∥=∣λ∣∥x∥\|\lambda \mathbf{x}\| = |\lambda| \|\mathbf{x}\|；
  3. ∥x+y∥p,∞≤2max⁡{1,1/p}(∥x∥p,∞+∥y∥p,∞).\|\mathbf{x} + \mathbf{y}\|_{p,\infty} \le 2^{\max\{1, 1/p\}}(\|\mathbf{x}\|_{p,\infty} + \|\mathbf{y}\|_{p,\infty}).

前两条性质显然成立，第三条可由下述更一般命题推出。

命题 7
设 x1,…,xk∈CN\mathbf{x}^1, \ldots, \mathbf{x}^k \in \mathbb{C}^N。则当 p>0p > 0 时，

∥x1+⋯+xk∥p,∞≤kmax⁡{1,1/p}(∥x1∥p,∞+⋯+∥xk∥p,∞).\|\mathbf{x}^1 + \cdots + \mathbf{x}^k\|_{p,\infty} \le k^{\max\{1, 1/p\}}\big( \|\mathbf{x}^1\|_{p,\infty} + \cdots + \|\mathbf{x}^k\|_{p,\infty} \big).

证明。 设 t>0t > 0。若对某个 j∈[N]j \in [N] 有
∣xj1+⋯+xjk∣≥t|x_j^1 + \cdots + x_j^k| \ge t，则必存在某个 i∈[k]i \in [k] 使得
∣xji∣≥t/k|x_j^i| \ge t / k。
因此，

{j∈[N]:∣xj1+⋯+xjk∣≥t}⊂⋃i∈[k]{j∈[N]:∣xji∣≥t/k}.\{ j \in [N] : |x_j^1 + \cdots + x_j^k| \ge t \} \subset \bigcup_{i \in [k]} \{ j \in [N] : |x_j^i| \ge t / k \}.

于是可以推出

card({j∈[N]:∣xj1+⋯+xjk∣≥t})≤∑i∈[k]∥xi∥p,∞p(t/k)p=kp(∥x1∥p,∞p+⋯+∥xk∥p,∞p)tp.\mathrm{card}\big(\{ j \in [N] : |x_j^1 + \cdots + x_j^k| \ge t \}\big) \le \sum_{i \in [k]} \frac{\|\mathbf{x}^i\|_{p,\infty}^p}{(t / k)^p} = \frac{k^p(\|\mathbf{x}^1\|_{p,\infty}^p + \cdots + \|\mathbf{x}^k\|_{p,\infty}^p)}{t^p}.

由弱 ℓp\ell_p 准范数的定义可得

∥x1+⋯+xk∥p,∞≤k(∥x1∥p,∞p+⋯+∥xk∥p,∞p)1/p.\|\mathbf{x}^1 + \cdots + \mathbf{x}^k\|_{p,\infty} \le k\big(\|\mathbf{x}^1\|_{p,\infty}^p + \cdots + \|\mathbf{x}^k\|_{p,\infty}^p\big)^{1/p}.

若 p≤1p \le 1，比较 Rk\mathbb{R}^k 中的 ℓp\ell_p 与 ℓ1\ell_1 范数，有

(∥x1∥p,∞p+⋯+∥xk∥p,∞p)1/p≤k1/p−1(∥x1∥p,∞+⋯+∥xk∥p,∞).\big(\|\mathbf{x}^1\|_{p,\infty}^p + \cdots + \|\mathbf{x}^k\|_{p,\infty}^p\big)^{1/p} \le k^{1/p - 1}\big(\|\mathbf{x}^1\|_{p,\infty} + \cdots + \|\mathbf{x}^k\|_{p,\infty}\big).

若 p≥1p \ge 1，则有

(∥x1∥p,∞p+⋯+∥xk∥p,∞p)1/p≤∥x1∥p,∞+⋯+∥xk∥p,∞.\big(\|\mathbf{x}^1\|_{p,\infty}^p + \cdots + \|\mathbf{x}^k\|_{p,\infty}^p\big)^{1/p} \le \|\mathbf{x}^1\|_{p,\infty} + \cdots + \|\mathbf{x}^k\|_{p,\infty}.

结果由此立即得出。□

备注 8
命题 7 中的常数 kmax⁡{1,1/p}k^{\max\{1,1/p\}} 是最优的，留作练习。

有时更方便使用以下等价形式来表示向量 x∈CN\mathbf{x} \in \mathbb{C}^N 的弱 ℓp\ell_p 准范数。

命题 9
当 p>0p > 0 时，向量 x∈CN\mathbf{x} \in \mathbb{C}^N 的弱 ℓp\ell_p 准范数可表示为

∥x∥p,∞=max⁡k∈[N]k1/pxk∗,\|\mathbf{x}\|_{p,\infty} = \max_{k \in [N]} k^{1/p} x_k^*,

其中 x∗∈R+N\mathbf{x}^* \in \mathbb{R}_+^N 表示 x\mathbf{x} 的非增重排（nonincreasing rearrangement）。

证明。
给定 x∈CN\mathbf{x} \in \mathbb{C}^N，根据定义有

∥x∥p,∞=∥x∗∥p,∞.\|\mathbf{x}\|_{p,\infty} = \|\mathbf{x}^*\|_{p,\infty} .

记∥x∥:=max⁡k∈[N]k1/pxk∗\|x\|:= \max_{k \in [N]} k^{1/p} x_k^*，我们需要证明 ∥x∥=∥x∗∥p,∞\|\mathbf{x}\| = \|\mathbf{x}^*\|_{p,\infty}。

令 t>0t > 0。注意到要么存在某个 k∈[N]k \in [N] 使得 {j∈[N]:xj∗≥t}=[k]\{ j \in [N] : x_j^* \ge t \} = [k]，
要么该集合为空。 在前一种情况下，由于 t≤xk∗=∥x∥/k1/pt \le x_k^* = \|\mathbf{x}\| / k^{1/p}，因此

card({j∈[N]:xj∗≥t})=k≤∥x∥ptp.\mathrm{card}(\{ j \in [N] : x_j^* \ge t \}) = k \le \frac{\|\mathbf{x}\|^p}{t^p}.

在后一种情况下该不等式平凡成立。
因此根据弱 ℓp\ell_p 准范数定义，有

∥x∗∥p,∞≤∥x∥.\|\mathbf{x}^*\|_{p,\infty} \le \|\mathbf{x}\|.

假设反之，∥x∥>∥x∗∥p,∞\|\mathbf{x}\| > \|\mathbf{x}^*\|_{p,\infty}，
则存在某个 ε>0\varepsilon > 0 使得

∥x∥≥(1+ε)∥x∗∥p,∞.\|\mathbf{x}\| \ge (1+\varepsilon)\|\mathbf{x}^*\|_{p,\infty}.

由此有

k1/pxk∗≥(1+ε)∥x∗∥p,∞k^{1/p} x_k^* \ge (1+\varepsilon)\|\mathbf{x}^*\|_{p,\infty}

对某个 k∈[N]k \in [N] 成立。于是集合

{j∈[N]:xj∗≥(1+ε)∥x∗∥p,∞/k1/p}\{ j \in [N] : x_j^* \ge (1+\varepsilon)\|\mathbf{x}^*\|_{p,\infty} / k^{1/p} \}

包含集合 [k][k]。根据定义，

k≤∥x∗∥p,∞p((1+ε)∥x∗∥p,∞/k1/p)p=k(1+ε)p,k \le \frac{\|\mathbf{x}^*\|_{p,\infty}^p} {((1+\varepsilon)\|\mathbf{x}^*\|_{p,\infty}/k^{1/p})^p} = \frac{k}{(1+\varepsilon)^p},

这导致矛盾。因此，

∥x∥=∥x∗∥p,∞.\|\mathbf{x}\| = \|\mathbf{x}^*\|_{p,\infty}.

□

这种弱 ℓp\ell_p 准范数的替代表达式，提供了一种更直接的方法来与 ℓp\ell_p（或准范数）比较。

命题 10
对任意 p>0p > 0 与任意 x∈CN\mathbf{x} \in \mathbb{C}^N，有

∥x∥p,∞≤∥x∥p.\|\mathbf{x}\|_{p,\infty} \le \|\mathbf{x}\|_p.

证明。
对任意 k∈[N]k \in [N]，

∥x∥pp=∑j=1N(xj∗)p≥∑j=1k(xj∗)p≥k(xk∗)p.\|\mathbf{x}\|_p^p = \sum_{j=1}^{N} (x_j^*)^p \ge \sum_{j=1}^{k} (x_j^*)^p \ge k(x_k^*)^p.

两边取 1/p1/p 次方并在 kk 上取最大值得

∥x∥p≥max⁡k∈[N]k1/pxk∗=∥x∥p,∞.\|\mathbf{x}\|_p \ge \max_{k \in [N]} k^{1/p} x_k^* = \|\mathbf{x}\|_{p,\infty}.

□

弱 ℓp\ell_p 准范数的替代表达式，使我们能够方便地得到命题 3 的变体，其中弱 ℓp\ell_p 替代了普通的 ℓp\ell_p。

命题 11
对于任意 q>p>0q > p > 0 和任意 x∈CN\mathbf{x} \in \mathbb{C}^N，有不等式

σs(x)q≤dp,qs1/p−1/q∥x∥p,∞,\sigma_s(\mathbf{x})_q \le \frac{d_{p,q}}{s^{1/p - 1/q}} \|\mathbf{x}\|_{p,\infty},

其中

dp,q:=(pq−p)1/q.d_{p,q} := \left( \frac{p}{q - p} \right)^{1/q}.

证明。
不失一般性，假设 ∥x∥p,∞≤1\|\mathbf{x}\|_{p,\infty} \le 1，
则对所有 k∈[N]k \in [N] 有 xk∗≤1/k1/px_k^* \le 1 / k^{1/p}。于是：

σs(x)qq=∑k=s+1N(xk∗)q≤∑k=s+1N1kq/p≤∫sN1tq/p dt=1q/p−11sq/p−1=pq−p1sq/p−1.\sigma_s(\mathbf{x})_q^q = \sum_{k=s+1}^{N} (x_k^*)^q \le \sum_{k=s+1}^{N} \frac{1}{k^{q/p}} \le \int_s^{N} \frac{1}{t^{q/p}} \, dt = \frac{1}{q/p - 1}\frac{1}{s^{q/p - 1}} = \frac{p}{q - p}\frac{1}{s^{q/p - 1}}.

两边取 1/q1/q 次方即得所求结论。□

命题 11 表明：当 x∈CN\mathbf{x} \in \mathbb{C}^N 可压缩且满足 ∥x∥p,∞≤1\|\mathbf{x}\|_{p,\infty} \le 1（其中 pp 很小）时， 其最佳 ss 项近似误差 σs(x)q\sigma_s(\mathbf{x})_q 随 ss 增加而快速衰减。我们以下给出一个关于非增重排（nonincreasing rearrangement）的技术性引理。

引理 12
对于 x,z∈CN\mathbf{x}, \mathbf{z} \in \mathbb{C}^N，非增重排满足

∥x∗−z∗∥∞≤∥x−z∥∞.(2.1)\|\mathbf{x}^* - \mathbf{z}^*\|_\infty \le \|\mathbf{x} - \mathbf{z}\|_\infty. \tag{2.1}

此外，对任意 s∈[N]s \in [N]，有

∣σs(x)1−σs(z)1∣≤∥x−z∥1,(2.2)|\sigma_s(\mathbf{x})_1 - \sigma_s(\mathbf{z})_1| \le \|\mathbf{x} - \mathbf{z}\|_1, \tag{2.2}

并且当 k>sk > s 时，

(k−s)xk∗≤∥x−z∥1+σs(z)1.(2.3)(k - s)x_k^* \le \|\mathbf{x} - \mathbf{z}\|_1 + \sigma_s(\mathbf{z})_1. \tag{2.3}

证明。
对 j∈[N]j \in [N]，设 SS 为对应于 z\mathbf{z} 的 jj 个最大绝对值分量的索引集合。
则非增重排 x∗,z∗\mathbf{x}^*, \mathbf{z}^* 满足

xj∗≤max⁡ℓ∈S∣xℓ∣≤max⁡ℓ∈S∣zℓ∣+∥x−z∥∞=zj∗+∥x−z∥∞.x_j^* \le \max_{\ell \in S} |x_\ell| \le \max_{\ell \in S} |z_\ell| + \|\mathbf{x} - \mathbf{z}\|_\infty = z_j^* + \|\mathbf{x} - \mathbf{z}\|_\infty.

交换 x\mathbf{x} 与 z\mathbf{z} 的角色即可得到式 (1)。

接下来，设 v∈CN\mathbf{v} \in \mathbb{C}^N 为 z\mathbf{z} 的最佳 ss 项近似，则有

σs(x)1≤∥x−v∥1≤∥x−z∥1+∥z−v∥1=∥x−z∥1+σs(z)1,\sigma_s(\mathbf{x})_1 \le \|\mathbf{x} - \mathbf{v}\|_1 \le \|\mathbf{x} - \mathbf{z}\|_1 + \|\mathbf{z} - \mathbf{v}\|_1 = \|\mathbf{x} - \mathbf{z}\|_1 + \sigma_s(\mathbf{z})_1,

由对称性，同理可得式 (2)。

式 (3) 则由下式推出：

(k−s)xk∗≤∑j=s+1kxj∗≤∑j≥s+1xj∗=σs(x)1.(k - s)x_k^* \le \sum_{j=s+1}^{k} x_j^* \le \sum_{j \ge s+1} x_j^* = \sigma_s(\mathbf{x})_1.

证毕。□

主题： 高维向量, 范数不等式, 稀疏性