压缩感知(少就是多)

信号稀疏表示

1928 年，奈奎斯特（Nyquist）研究电报传输，提出带宽与码元率的关系：码元速率不能超过 2B（其中 B 是信道带宽）。1949 年，香农（Shannon）在《通信中的噪声》中把这一思想推广到采样和信号重建，明确提出采样定理。传统的信号采样过程必须满足香农-奈奎斯特采样定理，即采样频率不能低于模拟信号频谱中最高频率的2倍。但是在现实中，面对宽带雷达信号、医学成像、高清视频、超声探测等场景，如果严格按照香农-奈奎斯特采样定理进行采样，就需要极高的采样率。这不仅要求高速模数转换器，带来硬件复杂、功耗大、成本高的问题，还会产生海量数据，使得存储和传输成为瓶颈。

幸运的是，在许多实际场景中，信号在某些变换域（如傅里叶域、小波域、稀疏基底等）往往具有稀疏性或可压缩性。例如，自然图像在小波域只有少量系数显著；语音和音频在频域大部分能量集中在低频；雷达回波中目标回波往往只占据整个时频平面的很小部分。这种稀疏特性为新的理论突破提供了可能，Candes、Romberg、Tao 以及 Donoho 等学者在 2006 年左右独立提出了压缩感知（Compressed Sensing, CS）理论。压缩感知理论指出，即便采样率远低于奈奎斯特速率，只要信号在某个域是稀疏的，就可以通过少量非自适应线性测量获取数据，并借助优化算法从中准确恢复原始信号。压缩感知为数据获取方式带来了新的范式：采集与压缩同时进行，避免了“先大量采样、再压缩存储”的传统冗余过程。这在高速数据采集和大规模信息处理领域具有重要的应用价值。

定义：信号的正交基展开

根据调和分析理论，任意长度为 $N$ 的一维离散时间信号 $f$，都可以在某组标准正交基 ${\phii}{i=0}^{N-1}$ 下表示为其线性组合：

$$f = \sum_{i=0}^{N-1} x_i \phi_i \;=\; \Phi x,\tag{1}$$

其中 ${xi}$ 为展开系数，${\phi_i}$ 为一组完备的标准正交基，$\Phi=[\phi_0,\phi_1,\dots,\phi{N-1}]$。

压缩传感

考虑一般的信号重构问题，已知某一个测量矩阵 $\Phi \in \mathbf{R}^{M\times N} (M \ll N)$ 以及未知信号 $x$，可以得到在该矩阵下的线性测量值 $y \in \mathbb{R}^{M}$

$$y = \Phi x \tag{2}$$

由于 $y$ 的维数远远低于 $x$ 的维数，方程组 (2) 会产生无穷多个解，无法重构原始信号。

---

非凸换凸

如果原始信号 $x$ 是 $K$ 稀疏的，并且满足约束等距条件 (Restricted Isometry Property, RIP)，我们可以将问题转换为求解一个 $l_0$ 范数问题：

$$\hat{\boldsymbol{x}} = \arg\min \|\boldsymbol{x}\|_0 \quad \text{s.t.} \quad \Phi \boldsymbol{x} = \boldsymbol{y},\tag{3}$$

其中 $|\boldsymbol{x}|_0$ 表示 $\boldsymbol{x}$ 中非零元素的个数。

---

定理：Candès–Tao 定理

设 $x0 \in \mathbb{R}^N$ 是 s-稀疏向量，$A \in \mathbb{R}^{m \times N}$ 是测量矩阵，满足条件 $\delta{2s} < \sqrt{2}-1$。令 $y = A x_0$，则通过

$$\hat{x} = \arg\min \|x\|_1 \quad \text{s.t.} \quad A x = y\tag{4}$$

可以恢复 $x_0$。

证明

设 $\hat{x}$ 是 $\ell_1$ 最小化的解，定义误差向量

$$h := \hat{x} - x_0.\tag{5}$$

令 $T = \mathrm{supp}(x_0)$，大小 $|T| \le s$，并将 $h$ 分解为

$$h = h_T + h_{T^c},\tag{6}$$

其中 $hT$ 是 $h$ 在 $T$ 上的分量，$h{T^c}$ 是 $h$ 在 $T^c$ 上的分量。

由于 $\hat{x}$ 是 $\ell_1$ 最小化解：

$$\|\hat{x}\|_1 = \|x_0 + h\|_1 \le \|x_0\|_1.\tag{7}$$

由三角不等式可得：

$$\|h_{T^c}\|_1 \le \|h_T\|_1. \tag{8}$$

将 $h_{T^c}$ 按绝对值大小排序，分块为 $T_1, T_2, \dots$，每块最多 $s$ 个元素：

$$h_{T^c} = h_{T_1} + h_{T_2} + \dots\tag{9}$$

由排序特性：

$$\|h_{T_j}\|_2 \le \frac{\|h_{T_{j-1}}\|_1}{\sqrt{s}}, \quad j \ge 2,\tag{10}$$

并且由式 (8)：

$$\sum_{j\ge 2} \|h_{T_j}\|_2 \le \|h_T\|_2. \tag{11}$$

由于 $A h = 0$，并使用 RIP 条件：

$$\|A(h_T + h_{T_1})\|_2 = \Big\| A \Big(- \sum_{j \ge 2} h_{T_j}\Big) \Big\|_2 \le \sum_{j \ge 2} \|A h_{T_j}\|_2 \le \sqrt{1+\delta_s} \sum_{j\ge 2} \|h_{T_j}\|_2.\tag{12}$$

另一方面：

$$\|A(h_T + h_{T_1})\|_2 \ge \sqrt{1-\delta_{2s}} \|h_T + h_{T_1}\|_2.\tag{13}$$

结合 (12)：

$$\sqrt{1-\delta_{2s}} \|h_T + h_{T_1}\|_2 \le \sqrt{1+\delta_s} \|h_T\|_2 \le \sqrt{1+\delta_s} \|h_T + h_{T_1}\|_2.\tag{14}$$

只要 $\delta_{2s} < \sqrt{2}-1$，上述不等式只能成立当

$$h_T + h_{T_1} = 0.\tag{15}$$

递推可得：

$$h_{T^c} = 0, \quad h_T = 0 \implies h = 0.\tag{16}$$

因此：

$$\hat{x} = x_0. \tag{17}$$

---

稀疏界限

我们首先考虑问题具有唯一解时的稀疏度上界。

定理：Donoho–Elad 唯一性定理

设 $A \in \mathbb{R}^{m \times n}$ （或 $\mathbb{C}^{m \times n}$）为列归一化矩阵，其互相干性为

$$\mu(A) = \max_{i \neq j} |\langle a_i, a_j \rangle|.\tag{18}$$

若向量 $x \in \mathbb{R}^n$ 满足

$$y = A x \quad \text{且} \quad \|x\|_0 < \frac{1}{2} \Big( 1 + \frac{1}{\mu(A)} \Big),\tag{19}$$

则 $x$ 是 $y = Ax$ 的唯一最稀疏解。

证明

假设系统 $y = A x$ 有两个不同的解 $x$ 和 $x’$，定义差向量 $h = x - x’$，则有

$$A h = A(x - x') = 0.\tag{20}$$

设 $T = \mathrm{supp}(h)$，则 $|T| \le 2 |x|_0$。对任意 $i \in T$：

$$0 = \langle a_i, A h \rangle = h_i + \sum_{j \in T, j \neq i} h_j \langle a_i, a_j \rangle.\tag{21}$$

取绝对值并利用 $\mu(A)$：

$$|h_i| \le \mu(A)(|T|-1)|h_{\max}|,\tag{22}$$

其中 $|h{max}| = max{i \in T} |h_i|$ 。

因此：

$$1 \le \mu(A)(2\|x\|_0 - 1).\tag{23}$$

若

$$\|x\|_0 < \tfrac{1}{2}\Big(1 + \tfrac{1}{\mu(A)}\Big),\tag{24}$$

则矛盾。因此 $x$ 是唯一的最稀疏解。 Q.E.D.

---

定理：Welch 界

设 $A \in \mathbb{C}^{m \times n}$（或 $\mathbb{R}^{m \times n}$）是列归一化矩阵：

$$\|a_i\|_2 = 1, \quad i=1,2,\dots,n,\tag{25}$$

则互相干性满足下界：

$$\mu(A) \ge \sqrt{\frac{n-m}{m(n-1)}}.\tag{26}$$

等号成立当且仅当 $A$ 形成等角紧框架 (Equiangular Tight Frame, ETF)。

证明

记 Gram 矩阵 $G = A^\ast A$，则 $G_{ii}=1$。其 Frobenius 范数：

$$\|G\|_F^2 = n + \sum_{i \neq j} | \langle a_i, a_j \rangle |^2.\tag{27}$$

另一方面：

$$\|G\|_F^2 \ge \tfrac{n^2}{m}.\tag{28}$$

因此：

$$\sum_{i \neq j} | \langle a_i, a_j \rangle |^2 \ge \tfrac{n(n-m)}{m}.\tag{29}$$

由 $\mu(A)$ 定义：

$$\sum_{i \neq j} | \langle a_i, a_j \rangle |^2 \le n(n-1)\mu(A)^2.\tag{30}$$

于是：

$$\mu(A) \ge \sqrt{\tfrac{n-m}{m(n-1)}}.\tag{31}$$

等号成立当 $A$ 为 ETF。 Q.E.D.

---

推论：基于 Welch 界的稀疏解唯一性

代入 Welch 界，可得稀疏度上界：

$$\|x\|_0 < \frac{1}{2} \Big( 1 + \sqrt{\frac{m(n-1)}{n-m}} \Big).\tag{32}$$

因此，任意稀疏度小于该下界的信号在矩阵 $A$ 下都有唯一最稀疏表示。

---

测量界限

我们从信息论角度证明稀疏恢复所需的最少测量数限制。

定理：稀疏恢复的信息论下界

设 $x \in \mathbb{R}^n$ 是 $k$-稀疏信号，$A \in \mathbb{R}^{m \times n}$ 是测量矩阵。
对于任意恢复算法，要以概率 $1-\delta$ 恢复 $x$，测量数 $m$ 必须满足：

$$m \ge c \cdot k \log\left(\frac{n}{k}\right) + \log\left(\frac{1}{\delta}\right),\tag{33}$$

其中 $c > 0$ 是常数。

证明

设 $X$ 是 $x$ 的支持集合的随机变量，取值集合：

$$\mathcal{X} = \{ S \subset [n] : |S| = k \}, \quad |\mathcal{X}| = \binom{n}{k}.\tag{34}$$

令 $Y = A X$，$\hat{X}(Y)$ 为恢复算法的估计，错误概率：

$$P_e = \Pr(\hat{X}(Y) \neq X) \le \delta.\tag{35}$$

由 Fano 不等式：

$$I(X;Y) \ge \log |\mathcal{X}| (1-P_e) - \log 2.\tag{36}$$

当 $n \gg k$：

$$\log \binom{n}{k} \approx k \log \tfrac{n}{k}.\tag{37}$$

测量 $Y$ 提供的信息量至多 $m$，因此：

$$m \ge k \log \tfrac{n}{k}(1-\delta) - \log 2.\tag{38}$$

故结论成立。 Q.E.D.