压缩感知进阶——有关稀疏矩阵

上一篇《初识压缩感知Compressive Sensing》中我们已经讲过了压缩感知的作用和基本想法，涉及的领域，本文通过学习陶哲轩对compressive sensing（CS）的课程，对压缩感知做进一步理解，针对其原理做出讲解。本文较为理论性，代码请参考《“压缩感知”之“Hello world”》。

Keywords: 压缩感知 compressive sensing, 稀疏（Sparsity）、不相关（Incoherence）、随机性（Randomness）

主要内容

===============================

回忆传统压缩

压缩感知概念 &线性度量

压缩感知适合解决什么问题？

压缩感知是否可行？

怎样恢复原信号？

Basis Pursuit & RIP

噪声

线性编码应用——single pixel camera

===============================

回忆传统压缩

对于原始信号x∈C(N*1)，传统压缩是构造正交矩阵D∈C（N*N）,正变换为y=Dx, 反变换x=D^-1y= D^Ty, D^-1= D^T。

将初始信号x变换到y∈C(N*1)后，将保留其中的K个分量（K人工指定），对其他N-K个分量置零，这样的信号y就称为K稀疏（K-Sparse）的。于是得到编码策略如下：

Code（编码）：构造正交矩阵D，做正变换y=Dx, 保留y中最重要的K个分量及其对应位置。

Decode（解码）：将K个分量及其对应位置归位，其他位置置零，得到y，构造D，并用x=D^-1y恢复x。

换句话说，传统压缩就是构造正交阵进行编解码，将所有N维信号全部存储下来。其弊端是，

1. 由于香农定理的限制，采样频率很大，这样造成了原始信号很长（N很大），消耗时间和空间。

2. K个重要分量要分别存储其位置，多分配空间。

3. K中分量（在传输过程中）丢失的话不好恢复。

 [ S-sparse ]:A model case occurs when x is known to be S-sparse for some 1≤S≤n, which means that at most S of the coefficients of x can be non-zero.

===========&