1 压缩感知的简介

1.1 提出

D． Donoho、E． Candes 及华裔科学家 T． Tao等人提出了一种新的信息获取理论 － 压缩感知（Compressive Sensing）

Donoho D L． Compressed sensing［J］ ． IEEE Transactions on Information Theory， 2006， 52( 4) : 1289 － 1306

1.2 评价

• 突破了香农-奈奎斯特采样定理的限制。
• 实现对信号采样的同时完成压缩的过程。
• 并不直接测量信号本身， 它使用非自适应线性投影（感知矩阵）来获得信号的整体构造从而直接得到重要的信息， 忽略那些在有损压缩中会被丢弃的信息。

2 压缩感知的数学模型

给定输入信号 X ∈ R N × 1 \boldsymbol{X} \in \mathbb{R}^{N\times1} X∈RN×1，最终想要得到压缩信号 A ∈ R M × 1 \boldsymbol{A} \in \mathbb{R}^{M\times1} A∈RM×1， K < < N K<<N K<<N

2.1 压缩过程（感知过程）分为（稀疏变换和投影测量）

2.1.1 稀疏变换（稀疏表示、稀疏过程）

找到一个基或者过完备字典 Ψ \boldsymbol{\Psi} Ψ，使得信号 X \boldsymbol{X} X在 Ψ \boldsymbol{\Psi} Ψ域是稀疏的，（参考补充材料稀疏）满足下面的公式
X = Ψ Y \boldsymbol{X}=\boldsymbol{\Psi} \boldsymbol{Y} X=ΨY
因为是规范正交基所以实现变换系数也就是压缩信号： Y = Ψ T X \boldsymbol{Y} = \boldsymbol{\Psi}^T \boldsymbol{X} Y=ΨTX，其中 Y \boldsymbol{Y} Y 是 X \boldsymbol{X} X 的等价或逼近的稀疏表示。变换基 Ψ \boldsymbol{\Psi} Ψ的选择可以为某
种已被广泛应用的基，如小波基、傅里叶基、局部傅里叶基等。另外，可以使用紧框架（原子字典）来对信号进行稀疏表示， 如曲线波和轮廓波， 这两类变换基具有更好的方向性，并且各向异性，少量系数即可有效地捕捉图像的边缘轮廓，在边缘表示方面优于小波。

2.1.2 投影测量（测量过程）

观测矩阵 Φ ∈ R M × N \boldsymbol{\Phi} \in \mathbb{R}^{M\times N} Φ∈RM×N，观测矩阵也叫测量矩阵，感知矩阵，实现的功能是对信号进行降维和压缩
A = Φ X \boldsymbol{A} = \boldsymbol{\Phi}\boldsymbol{X} A=ΦX
同时也是对在 Ψ \boldsymbol{\Psi} Ψ域上的稀疏投影 Y \boldsymbol{Y} Y进行投影测量
A = Φ Ψ Y \boldsymbol{A} = \boldsymbol{\Phi}\boldsymbol{\Psi} \boldsymbol{Y} A=ΦΨY
矩阵 Φ \boldsymbol{\Phi} Φ需要满足的性质（需要保证稀疏向量 Y \boldsymbol{Y} Y 从 N N N维降到 K K K 维时重要信息不被破坏。）

变换基 Ψ \boldsymbol{\Psi} Ψ不相关（会在之后的blog中有叙述）

有限等距性（Restricted Isometry Property，RIP）（会在之后的blog中有叙述）

2.1.3 感知过程（压缩过程）总结

A = Φ X = Φ Ψ Y = Θ Y \boldsymbol{A} =\boldsymbol{\Phi}\boldsymbol{X} = \boldsymbol{\Phi}\boldsymbol{\Psi} \boldsymbol{Y} = \boldsymbol{\Theta}\boldsymbol{Y} A=ΦX=ΦΨY=ΘY

Θ \boldsymbol{\Theta} Θ即为感知过程的核心命名为感知矩阵

符号	含义	维度	属性
X \boldsymbol{X} X	输入信号；待压缩信号	R N × 1 \mathbb{R}^{N\times1} RN×1	未知，需要恢复
Φ \boldsymbol{\Phi} Φ	观测矩阵；测量矩阵	R M × N \mathbb{R}^{M \times N} RM×N	已知（非自适应性）
Ψ \boldsymbol{\Psi} Ψ	变换矩阵；变换基矩阵；稀疏基矩阵；稀疏矩阵；正交基字典矩阵	R N × N \mathbb{R}^{N\times N} RN×N	已知（非自适应性）
Y \boldsymbol{Y} Y	正交基变换后的稀疏表示	R N × 1 \mathbb{R}^{N\times1} RN×1	未知，需要恢复
Θ \boldsymbol{\Theta} Θ	感知矩阵	R M × N \mathbb{R}^{M\times N} RM×N	已知（非自适应性）
A \boldsymbol{A} A	观测压缩所得到压缩信号	R M × 1 \mathbb{R}^{M\times1} RM×1	已知

2.2 恢复过程：重构算法的数学表示

在得到已经压缩完的采样信号 A \boldsymbol{A} A后，根据确定的固定性观测矩阵 Φ \boldsymbol{\Phi} Φ和稀疏矩阵 Ψ \boldsymbol{\Psi} Ψ的先验信息进行恢复，数学表达如下
X ˇ = f ( A , Θ ) \boldsymbol{\check{X}}=f(\boldsymbol{A},\boldsymbol{\Theta}) Xˇ=f(A,Θ)
若 N = M N=M N=M，正定方程有唯一解

而 M < < N M<<N M<<N，欠定方程

一般可以抽象为如下求解任务
min ⁡ ∥ Ψ T X ∥ 0 s . t . Θ X = Φ Ψ X = A \min \left\| \boldsymbol{\Psi}^{T} \boldsymbol{X}\right\|_{0} \\s.t. \boldsymbol{\Theta} \boldsymbol{X}=\boldsymbol{\Phi}\boldsymbol{\Psi}\boldsymbol{X}= \boldsymbol{A} min∥∥∥​ΨTX∥∥∥​0​s.t.ΘX=ΦΨX=A

注意

若 N = M N=M N=M，则可轻松由 A \boldsymbol{A} A解出 X \boldsymbol{X} X和 Y \boldsymbol{Y} Y

而 M < < N M<<N M<<N，可根据稀疏表示下的信号 Y \boldsymbol{Y} Y和矩阵所具有的RIP特性重构