1.12-稀疏表示与压缩感知

AI总结

压缩感知又称压缩采样，是一种与数据采集的传统 Nyquist 方法不同的新采样技术。压缩感知理论认为，某些信号和图像可以从比传统方法少得多的样本中恢复或重构。压缩感知与稀疏表示密切相关。

稀疏向量与稀疏表示

• 稀疏向量(矩阵)：大多数元素为零

• 稀疏表示：使用少量基本信号的线性组合表示一目标信号

• 稀疏表示

  • 信号向量 $\mathbf{y}\in {\mathbb{R}}^m$ 最多可分解为 $m$ 个正交基 (向量) ${\mathbf{g}}_k\in {\mathbb{R}}^m,k=1,\cdots ,m$，这些正交基的集合称为完备正交基。
  • 此时，信号分解$\mathbf{y}=\mathbf{G}\mathbf{c}={\sum }_{i=1}^m{c}_i{\mathbf{g}}_i$中的系数向量 $\mathbf{c}$ 一定是非常稀疏的。

过完备分解与字典

• 若将 $\mathbf{y}\in {\mathbb{R}}^m$ 分解为 $n$ 个 $m$ 维向量 ${\mathbf{a}}_i\in {\mathbb{R}}^m,i=1,\cdots ,n$ 的线性组合$\mathbf{y}=\mathbf{A}\mathbf{x}={\sum }_{i=1}^n{x}_i{\mathbf{a}}_i(n>m)$，这 $n$ 个向量 不可能是正交基的集
• 这些列向量通常被称为原子或框架，并称这些原子的集合是过完备的
• 过完备的原子组成的矩阵 $\mathbf{A}=[{\mathbf{a}}_1,\cdots ,{\mathbf{a}}_n]\in {\mathbb{R}}^{m\times n}(n>m)$ 称为字典或库)

对字典 (矩阵) $\mathbf{A}\in {\mathbb{R}}^{m\times n}$，通常作如下假设：

1. $\mathbf{A}$ 的行数 $m$ 小于列数 $n$。
2. $\mathbf{A}$ 具有满行秩，即 $\text{rank}(\mathbf{A})=m$。
3. $\mathbf{A}$ 的列具有单位 Euclidean 范数 $\Vert {\mathbf{a}}_j{\Vert }_2=1$

求解过完备分解式

信号过完备分解式 $\mathbf{y}=\mathbf{A}\mathbf{x}={\sum }_{i=1}^n{x}_i{\mathbf{a}}_i(n>m)$ 为欠定方程，存在无穷多组解向量 $\mathbf{x}$。

求最小 $L_2$ 范数解(经典方法)

$$\min \Vert \mathbf{x}{\Vert }_2\text{subject to}\mathbf{A}\mathbf{x}=\mathbf{y}$$

• 优点：解唯一，物理解释为最小能量解
• 缺点：元素通常取非零值，不符合许多实际应用的稀疏表示要求

求最小 $L_0$ 范数解 (现代方法)

$$\min \Vert \mathbf{x}{\Vert }_0\text{subject to}\mathbf{A}\mathbf{x}=\mathbf{y}$$

（式中 $L_0$ 范数 $\Vert \mathbf{x}{\Vert }_0$ 是向量 $\mathbf{x}$ 的非零元素的个数）

• 优点：针对许多实际应用情况，只选择一个稀疏的解向量
• 缺点：计算比较难于处理。

在存在观测数据误差或背景噪声的情况下，最小 $L_0$ 范数解为

$$\min \Vert \mathbf{x}{\Vert }_0\text{subject to}\Vert \mathbf{A}\mathbf{x}-\mathbf{y}{\Vert }_2⩽\epsilon$$

式中 $\epsilon$ 为一很小的误差或扰动。

• 称现代方法的求解结果为稀疏表示，加上 $\epsilon$ 的限制后称为稀疏逼近

• $K$ 稀疏：向量 $\mathbf{x}$ 的 $L_0$ 范数 $\Vert \mathbf{x}{\Vert }_0⩽K$，$K$ 为正整数

• 最稀疏表示：具有最小 $L_0$ 范数的稀疏分解

稀疏编码

稀疏编码可以给出刺激的简洁表示。
只给定未标识的输入数据，稀疏编码可以对捕捉数据中的高级特征的基函数进行机器学习。

原始数据：$\mathbf{X}$
字典/基：$\mathbf{A}$
稀疏系数：$\mathbf{S}$

如果给定的是 $m$ 维实值输入向量的一组集合 $({\mathbf{x}}_1,\cdots ,{\mathbf{x}}_k)$，则稀疏编码的目的就是确定基矩阵 $\mathbf{A}$ 和系数矩阵 $\mathbf{S}$，使得 $\mathbf{X}\approx \mathbf{A}\mathbf{S}$，其中 $\mathbf{X}=[{\mathbf{x}}_1,\cdots ,{\mathbf{x}}_k]\in {\mathbb{R}}^{m\times k}$ 和 $\mathbf{S}=[{\mathbf{s}}_1,\cdots ,{\mathbf{s}}_k]\in {\mathbb{R}}^{n\times k}$ 分别表示输入矩阵和系数矩阵，并且系数矩阵的每一个列向量都是稀疏向量，即稀疏向量 ${\mathbf{s}}_i$ 是与输入向量 ${\mathbf{x}}_i$ 对应的系数向量 ${\mathbf{x}}_i\approx \mathbf{A}{\mathbf{s}}_i$。

（特别之处：程序需要自己学习，找到字典/基矩阵）

• 主要特点

  • 系数向量只有少数元素不等于零，大多数元素为零。
    • 因此，对应于某个输入向量，基矩阵中只有少数基向量被激活
    • 与新陈代谢的观点不谋而合：越少的神经元被激励时，所用的能量也就越少。

• 临界完备编码

  • 基向量的个数 $n$ 等于输入向量的维数 $m$
    • 该编码的目标是求一可逆的加权矩阵 $\mathbf{A}$，利用它对输入进行变换，以满足对输出作用的某种优化准则，如解相关、稀疏性等。
    • 临界完备编码的典型例子有：JPEG 图像压缩中使用的离散余弦变换和正交小波变换等。
    • 在临界完备编码的情况下，输入向量的小变化都有可能导致系数的突然变化，从而使得编码对输入向量中的误差或者噪声敏感。

• 过完备基集合

  • 稀疏化会淘汰那些对描述给定的图像结构无用的大量基向量，因为这些基向量与稀疏向量的零元素相乘，而被完全淘汰
  • 过完备码对噪声和其他形式的退化具有更大的数值稳定性。
  • 在使用生成模型对输入结构进行匹配时，过完备编码比临界完备编码具有更大的灵活性。

压缩感知的稀疏表示

• Nyquist 采样定理
  • 只有采样速率大于或者等于信号带宽的 2 倍时，才能精确地重建或重构原始信号。

然而，对于超宽带通信和信号处理、计算机视觉、生物医学成像、遥感成像、传感器网络等众多应用，信号的带宽越来越大，从而对信号的采样速率、传输速度和存储空间的要求也越来越高。为了应对和缓解这些变化带来的挑战与压力，通常的做法是先使用 Nyquist 速率采样，再进行采样数据的压缩。问题是，对于超宽带信号，Nyquist 速率采样成本太高，而且大量被压缩掉的数据对信号而言是不重要或者冗余的信息。

稀疏信号：在大多数采样时刻的取值等于零或者近似等于零，只有少数采样时刻的取值明显不等于零的信号。

许多自然信号在时域并不是稀疏信号，但是在某个变换域是稀疏的。这些稀疏变换工具包括 Fourier 变换、短时 Fourier 变换、小波变换和 Gabor 变换等。信号常称为可压缩信号。

压缩感知 ：压缩 + 低速率采样

令 $x(t)$ 是一连续时间信号，理想情况下，我们希望使用 Nyquist 速率采样，得到 $n$ 个离散时间信号的向量 $\mathbf{x}=[x(1),\cdots ,x(n){]}^{\text{T}}\in {\mathbb{R}}^n$。然而，实际上，我们使用远低于 Nyquist 速率采样，只得到一低维测量数据向量 $\mathbf{y}=[y(1),\cdots ,y(m){]}^{\text{T}}\in {\mathbb{R}}^m$，其中

$$y(k)=⟨{\mathbf{\varphi }}_k,\mathbf{x}⟩,k\in M$$

式中 $M\subset \{1,\cdots ,n\}$ 是一个基数 (cardinality) $m\ll n$ 的子集，而 ${\mathbf{\varphi }}_k$ 表示感知基 $\mathbf{\Phi }\in {\mathbb{R}}^{n\times n}$ 的第 $k$ 列。上式又可写成向量形式

$$\mathbf{y}=\mathbf{A}\mathbf{x}$$

式中，感知矩阵 $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ 的 $m$ 个行向量由感知基 (sensing basis) $\mathbf{\Phi }$ 的 $m$ 个列向量的转置排列组成，即 $\mathbf{A}=[{\mathbf{\varphi }}_1,\cdots ,{\mathbf{\varphi }}_m{]}^{\text{T}}$，其中 $1,\cdots ,m\in M$。

感知波形 $\mathbf{y}$ 可以是时域或空域的采样向量；若感知波形为像素的指标函数，则 $\mathbf{y}$ 是由数字摄像机的传感器采集的图像数据向量；若感知波形为正弦波，则 $\mathbf{y}$ 是 Fourier 系数向量，这正是核磁共振成像 (magnetic resonance imaging, MRI) 的感知模式。

然而，即使感知波形 $\mathbf{y}$ 和感知矩阵 $\mathbf{A}$ 已知，我们也无法通过求解矩阵方程 $\mathbf{y}=\mathbf{A}\mathbf{x}$，恢复或者重构高维信号向量 $\mathbf{x}$，这主要是因为 $m\ll n$，使得求解欠定的矩阵方程的 $n$ 维解向量 $\mathbf{x}$ 往往不实际，何况使用 Nyquist 速率对超宽带信号采样的成本也很高。例如，对某个 1G 带宽的超宽带视频信号，至少得用 2G Hz 的 Nyquist 速率采样，则 $n=2\times 10^9$，即整个解向量 $\mathbf{x}$ 至少含有 $2\times 10^9$ 个元素。

实际的信号或者图像常常是用时域表示的，并且在某个变换域 (例如频域) 是可压缩的，而可压缩的信号或图像往往可以使用稀疏向量充分逼近。于是，可以使用某个表示矩阵 (representation matrix) $\mathbf{\Psi }\in {\mathbb{R}}^{n\times n}$，将 $\mathbf{x}$ 从时域变换到频域或者其他某个可压缩的变换域，得到 $\mathbf{x}$ 的稀疏表示

$$\mathbf{x}=\mathbf{\Psi }\mathbf{\alpha }$$

其中，系数向量 $\mathbf{\alpha }\in {\mathbb{R}}^n$ 是 $\mathbf{x}$ 的 $K$-稀疏表示，即 $\mathbf{\alpha }$ 只含 $K$ 个非零元素。

$$\mathbf{y}=\mathbf{A}\mathbf{\Psi }\mathbf{\alpha }=\mathbf{V}\mathbf{\alpha }$$

式中 $\mathbf{V}=\mathbf{A}\mathbf{\Psi }$ 称为全息字典或库 ，因为它包含了感知和表示的全面信息。

现在的问题是：在给定感知基 $\mathbf{\Phi }\in {\mathbb{R}}^{n\times n}$ 和表示基 $\mathbf{\Psi }\in {\mathbb{R}}^{n\times n}$ 的情况下，能否通过求解欠定的矩阵方程式，由低维的感知波形 $\mathbf{y}\in {\mathbb{R}}^m$ 精确地或高概率地重构出 Nyquist 速率采样的高维数据向量 $\mathbf{x}\in {\mathbb{R}}^n$。

用低维的采样数据向量恢复或重构 Nyquist 速率采样的高维数据向量，称为压缩感知。压缩感知是一种采样新理论，又称压缩采样。

图 1.12.1 画出了压缩感知的方框图。图中，虚线所示的部分为虚拟部分，是实际中不执行的操作。

方法	传统感知	压缩感知
采样速率	Nyquist 速率或更高速率	低速率
感知方式	感知后压缩（数字式）	感知期间压缩（物理方式）
感知量	大，后期压缩丢弃很多数据	小，因而可快速感知，传感器少且低廉
压缩比	较好的压缩比，压缩是自适应的	压缩是非自适应的
感知数据计算	简单	复杂，涉及稀疏优化

(2) 非相干性 (incoherence) 的基本思想是：当感知基 $\mathbf{\Phi }$ 与表示基 $\mathbf{\Psi }$ 不相干时，与感兴趣的自然信号和图像不同，采样或者感知的波形具有极为稠密的表示式 (1.12.12)，其中 $\mathbf{\alpha }$ 是一个 $K$-稀疏的系数向量。

考虑 $m\times n$ 测量矩阵 $\mathbf{A}=[{\mathbf{a}}_1,\cdots ,{\mathbf{a}}_n]$，其列向量已经全部归一化，即 $\Vert {\mathbf{a}}_i{\Vert }_2=1,i=1,\cdots ,n$。衡量一个矩阵质量的经典测度是矩阵列向量之间的相干 (coherence)，定义为两个不同列向量之间的互相关的最大绝对值：

$$\mu (\mathbf{A})=\underset{i\ne j}{\max }|⟨{\mathbf{a}}_i,{\mathbf{a}}_j⟩|=\underset{i\ne j}{\max }|{\mathbf{a}}_i^{\text{H}}{\mathbf{a}}_j|$$

粗略地讲，相干参数 $\mu$ 可以度量两个列向量之间是如何相类似，若相干参数大，则至少有两个列向量彼此相类似。反之，若相干参数 $\mu$ 小，则测量矩阵 $\mathbf{A}$ 的各个列是几乎相互正交的。

两个 $n\times n$ 矩阵 $\mathbf{A}$ 和 $\mathbf{B}$ 之间的互相干参数 (mutual coherence parameter) 定义为：

$$\mu (\mathbf{A},\mathbf{B})=\sqrt{n}\underset{1⩽j,k⩽n}{\max }|⟨{\mathbf{a}}_j,{\mathbf{b}}_k⟩|\text{\hspace{1em}(1.12.14)}$$

通俗地讲，互相干度量 $\mathbf{A}$ 的列向量 ${\mathbf{a}}_j$ 和 $\mathbf{B}$ 的列向量 ${\mathbf{b}}_k$ 之间的最大相关。如果 $\mathbf{A}$ 和 $\mathbf{B}$ 含有相关的任何两个列向量，则矩阵 $\mathbf{A}$ 和 $\mathbf{B}$ 之间的相干参数就大；反之，若两个矩阵之间的互相干很小，则一个矩阵的所有列向量都与另一矩阵的各个列向量几乎相互正交。

一个 $m\times n$ 感知基矩阵 $\mathbf{\Phi }$ 称为非相干的 (incoherent)，若：

$$\underset{j\ne k}{\max }|⟨{\mathbf{\varphi }}_j,{\mathbf{\varphi }}_k⟩|⩽\frac{1}{\sqrt{m}}\text{\hspace{1em}(1.12.15)}$$

一个 $m\times n$ ($m<n$) 宽矩阵 $\mathbf{\Phi }$ 称为紧致框架 (tight frame)，若：

$$\mathbf{\Phi }{\mathbf{\Phi }}^{\text{T}}=\frac{n}{m}{\mathbf{I}}_{m\times m}\text{\hspace{1em}(1.12.16)}$$

满足 $\mathbf{M}{\mathbf{M}}^{\text{T}}=c^2{\mathbf{I}}_{m\times m}$ 的所有 $m\times n$ ($m<n$) 宽矩阵 $\mathbf{M}$ 的集合称为共形矩阵 (conformal matrices)。在所有的共形矩阵中，紧致框架具有最小的谱范数。

感知基矩阵 $\mathbf{\Phi }\in {\mathbb{R}}^{n\times n}$ 和表示基矩阵 $\mathbf{\Psi }\in {\mathbb{R}}^{n\times n}$ 之间的互相干 $\mu (\mathbf{\Phi },\mathbf{\Psi })\in [1,\sqrt{n}]$。因此，称感知基矩阵 $\mathbf{\Phi }\in {\mathbb{R}}^{n\times n}$ 和表示基矩阵 $\mathbf{\Psi }\in {\mathbb{R}}^{n\times n}$ 非相干，若：

$$\underset{j\ne k}{\max }|⟨{\mathbf{\varphi }}_j,{\mathbf{\psi }}_k⟩|⩽1\text{\hspace{1em}(1.12.17)}$$

定理 1.12.1 令 $\mathbf{x}\in {\mathbb{R}}^n$，感知矩阵 $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ 由感知基 $\mathbf{\Phi }$ 的 $m$ 个列向量转置组成；并且 $\mathbf{x}$ 用表示基 $\mathbf{\Psi }$ 表示的系数向量 $\mathbf{\alpha }$ 是 $K$-稀疏的。若：

$$m⩾C{\mu }^2(\mathbf{\Phi },\mathbf{\Psi })K\log (n/\delta )\text{\hspace{1em}(1.12.18)}$$

对某个正常数 $C$ 成立，则 $L_1$ 范数最小化问题：

$$\min \Vert \mathbf{\alpha }{\Vert }_1\text{subject to}\mathbf{y}=\mathbf{A}\mathbf{\Psi }\mathbf{\alpha }\text{\hspace{1em}(1.12.19)}$$

的解 $\mathbf{\alpha }$ 可以以 $1-\delta$ 的概率精确求出，从而高维离散时间向量 $\mathbf{x}$ 可以从低维采样向量 $\mathbf{y}$ 以 $1-\delta$ 的概率重构。

从定理 1.12.1 可以得出以下结果：
(1) 感知基 $\mathbf{\Phi }$ 和表示基 $\mathbf{\Psi }$ 之间的相干性越小，所需要的测量样本数 $m$ 就越少。
(2) 虽然低速率只采样了 $m$ 个数据，它比用 Nyquist 速率采样的信号长度 $n$ 少得多，但是并不会造成任何信息的丢失，因为信号可以高概率地精确恢复或者重构。如果 $\mu (\mathbf{\Phi },\mathbf{\Psi })$ 等于或者接近 1，则只要用 $K\log n$ 数量级的 $m$ 个测量数据即可。

综上所述，压缩感知包含了以下两个关键步骤：
(1) 通过非二次型凸优化问题：

$$\min \Vert \mathbf{\alpha }{\Vert }_0\text{subject to}\mathbf{y}=\mathbf{V}\mathbf{\alpha }\text{\hspace{1em}(1.12.20)}$$

的求解，估计稀疏的系数向量 $\mathbf{\alpha }$。
(2) Nyquist 速率的采样数据向量通过 $\mathbf{x}=\mathbf{A}\mathbf{\alpha }$ 重构。

压缩感知的采样速率不再取决于信号的带宽，而主要取决于稀疏性和非相干性（也称等距约束性）。压缩感知问题主要包括了以下三个问题：
(1) 具有稀疏表示能力的过完备字典 $\mathbf{\Psi }\in {\mathbb{R}}^{n\times n}$ 的设计。
(2) 满足与过完备字典 $\mathbf{\Psi }$ 非相干或等距约束性准则的感知矩阵 $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ 或者感知基 $\mathbf{\Phi }\in {\mathbb{R}}^{n\times n}$ 的设计。
(3) 非二次型凸优化问题式 (1.12.20) 的求解。

注意，由于 $\mathbf{\alpha }\in {\mathbb{R}}^n$ 是一个 $K$-稀疏向量，不需要对其 $n-K$ 个 “0” 元素进行存储，也不对它们进行任何运算，从而大大节省内存空间和计算时间。因此，稀疏向量计算的复杂性和代价仅仅取决于稀疏向量的非零元素的个数。

人脸识别的稀疏表示

假定共有 $c$ 类目标，每一类目标的脸部的每一幅训练图像的矩阵表示结果已经向量化，表示成 $m\times 1$ 向量 ($m=R_1\times R_2$ 为一幅图像的采样样本数目)，并且每一列都归一化为单位 Euclidean 范数。

于是，第 $i$ 类目标的脸部在不同照度下拍摄的 $N_i$ 个训练图像即可表示成 $m\times N_i$ 维数据矩阵${\mathbf{D}}_i=[{\mathbf{d}}_{i,1},{\mathbf{d}}_{i,2},\cdots ,{\mathbf{d}}_{i,N_i}]\in {\mathbb{R}}^{m\times N_i}$。

给定一足够丰富的训练集 ${\mathbf{D}}_i$，则第 $i$ 个实验对象在另一照度下拍摄的新图像 $\mathbf{y}$ 即可以表示成已知训练图像的一线性组合 $\mathbf{y}\approx {\mathbf{D}}_i{\mathbf{\alpha }}_i$，其中 ${\mathbf{\alpha }}_i\in {\mathbb{R}}^m$ 为系数向量。

如果我们大致知道或者猜测到新的测试样本是 $c$ 类目标中的某类目标的信号，就可以将这 $c$ 类目标的训练样本构造的字典合写成一个训练数据矩阵$\mathbf{D}=[{\mathbf{D}}_1,\cdots ,{\mathbf{D}}_c]$。

其中 $N={\sum }_{i=1}^c{N}_i$ 表示所有 $c$ 类目标的训练图像的总个数。于是，待识别的人脸图像 $\mathbf{y}$ 可以表示成线性组合

$$\mathbf{y}=\mathbf{D}{\mathbf{\alpha }}_0=[{\mathbf{d}}_{1,1},\cdots ,{\mathbf{d}}_{1,N_1},\cdots ,{\mathbf{d}}_{c,1},\cdots ,{\mathbf{d}}_{c,N_c}]\left[\begin{array}{c}{0}_{N_1}\\ ⋮\\ 0_{N_{i-1}}\\ {\mathbf{\alpha }}_i\\ 0_{N_{i+1}}\\ ⋮\\ 0_{N_c}\end{array}\right]$$

其中 $0_{N_k},k=1,\cdots ,i-1,i+1,\cdots ,c$ 为 $N_k$ 维零向量。

现在，人脸识别便变成一个矩阵方程的求解问题或者线性求逆问题：已知数据向量 $\mathbf{y}$ 和数据矩阵 $\mathbf{D}$，求矩阵方程 $\mathbf{y}=\mathbf{D}{\mathbf{\alpha }}_0$ 的解向量 ${\mathbf{\alpha }}_0$。

通常 $m<N$，且解向量必须是稀疏向量，故人脸识别问题可以描述成一个优化问题

$$\min \Vert {\mathbf{\alpha }}_0{\Vert }_0\text{subject to}\mathbf{y}=\mathbf{D}{\mathbf{\alpha }}_0$$

这是一个典型的 $L_0$ 范数最小化问题。这一问题的求解将在第 6 章中详细讨论。