一、The Shannon-Nyquist Sampling Theorem

问题：原始数据是连续函数，是否能用有限个采样百分之百重现原始数据？

香农回答了这个问题：如果原始数据中最大频率为f，如果采样频率为2f，即每隔1/(2f)秒取一次样，则可完全恢复原始数据。



陆吾生教授2010年的视频中给出了非常直观的解释：



图a是采样和恢复过程，图b表示原始函数的傅里叶变换得到的频域分布，图c表示取样后的频域分布，可以看到是原始频域分布复制粘贴，且按采样频率位移，因为频率分布不能重叠，否则信息就会丢失，这个用公式表示就是下图的关系，所以可以很容易得到采样频率和原始频率的关系，图d是低通滤波器，图e是低通部分，即原始数据的频率分布。





最终的恢复公式就是，可以看成是采样后的信号与sinc函数卷积的结果：



其中sinc(x)部分是，它的图示曲线是：



 

二、Sparse and Compressible Signals

（我的理解）如果信号是由某种分布或者几种分布构成，则信号是可以被压缩的。

比如离散余弦变换DCT和离散小波变换DWT，本质上即是预先设定的两组正交基，通过θ=C’x或θ=W‘x即可将原始向量解释为预设空间中的坐标。将θ中接近0的部分设为0，得到θ‘，则转换后的数据x' = Cθ'或x' = Wθ'，其中C'和W’分别为C和W的转置。

 



[plain] view plain copy

 
 


%Below is a MALAB code to generate matrix DCT.   
	
function C = gen_dct(n)   
	
alp = [sqrt(1/n) sqrt(2/n)*ones(1,n-1)];   
	
ind = (1:2:(2*n-1))*pi/(2*n);   
	
C = zeros(n,n);   
	
for k = 1:n,   
	
C(k,:) = alp(k)*cos((k-1)*ind);   
	
end   




[plain] view plain copy

 
 


%Our second example is about an orthonormal basis based on discrete wavelet transform <span style="font-family: Arial, Helvetica, sans-serif; font-size: 12px;">DWT.</span>  
	
% Suppose signal length n= 2^p  
	
%for some integer p, then the basis matrix Wof size nby n  
	
%associated with Daubechies’ orthogonal discrete wavelets can be readily constructed in MATLAB   
	
%using Toolbox Uvi_Wave toolbox as follows:   
	
% n -- signal length, must be a power of 2.   
	
% L -- length of Daubechies wavelet, must be an even integer.   
	
% W -- orthonormal DWT matrix of size n x n.   
	
function W = gen_wave(n,L)   
	
p = log2(n);   
	
[h0,h1,f0,f1] = daub(L);   
	
I = eye(n,n);   
	
W = I;   
	
for i = 1:n,   
	
Ii = I(:,i);   
	
W(:,i) = wt(Ii,h0,h1,p);   
	
end   


 



 

 

上面两图为余弦变换和小波变换的结果，50,100为对应的阈值，可以看出不同的正交基得到的结果不尽相同。

陆吾生教授的视频里小波变换讲得非常好，想学习的一定要去看看。

三、Sensing a Sparse Signal

小波变换W，θ= W‘x，其实可以理解为用W中基底解释x的过程，x的稀疏性取决于W基底的”完备性“。这个可以理解为W是一个字典，W中的基底就是字典中的词，词越多你对原句的解释就可以越简洁，比如”上海“可以解释为”上“+”海“，也可以解释为”沪“，因此增加一个矩阵得到[I W]，可以得到更好的稀疏性。字典可以用其他已知的基底构成，比如单位矩阵I，离散余弦变换DCT，离散小波变换DWT，离散傅里叶变换DFT，Hadamard-Walsh矩阵等等。

现在问题变为Dθ= x，D是n*l的字典，θ是l*1的解，x是输入向量，如何找到最稀疏的θ？

Dθ = x其实是一个方程数小于变量数的线性方程组，所以这个方程的解一定是特解加通解的形式，特解是类似于广义逆的形式，θ1 = D‘inv(DD')x，通解需要对D进行SVD分解D=UΛV，U是n*n的特征向量矩阵，Λ是n*l特征值矩阵，V是l*l的特征向量矩阵，θ2 = Vn*δ，Vn是V后(l-n)列，即l*(l-n)的矩阵，δ是(l-n)*1的自由变量（随便是啥），问题就变成了如何选择δ确定的解空间中寻找最稀疏的θ1+θ2。

最优化问题形式化为：



其中0-norm表示θ中非0元素的个数，可是这个问题是NP-hard问题，不过可以转化为：



1-norm就是绝对值的和，上面问题就可以转化为另一个不带绝对值的线性规划问题，这个问题可以用sedumi这个工具求解（具体过程请看陆教授的视频），得到的解比直接用DWT要好很多。

四、Compressed Sensing

 

按照香农的理论，假设采样频率为f=n，则一秒钟需要采样n个数据，从线性代数的角度来看，是将无限维原始数据映射到n维正交空间。DCT和DWT或者他们构成的字典提供了巧妙的正交基，使得新向量变得稀疏。现在有个想法，为什么不直接采样到好空间？换句话说，能否在采样时不是按照原始数据的频率，而是按照原始数据信息的频率。

假设信号在Ψ空间中是r-sparse，转化为压缩信号θ：



现在有另外一个空间Φ，采样x：



Φ^{\hat}是Φ随机抽取m行的结果，y是m*1，Φ^{\hat}是m*n，x是n*1，m<n，所以这里是压缩采样。

已知y重建x的过程就是最优化一个最稀疏的θ，然后用上面的公式求出x



当m满足下面公式时，可以保证信号可以恢复：



可以简化为：





压缩感知的Matlab tool可以用CalTech的l1-MAGIC。

Ψ的选择很重要，直接确定原始数据中哪些信息是noise哪些是真实信息，也就是决定信号是否可以压缩以及压缩后是否可以恢复，Φ可以是随机的矩阵。

在本例中，原始稀疏向量。假设，中的非零向量数目为10。

如果不对数据压缩，直接用一个矩阵对数据进行变换，得到全观测数据：

    (1)

这里，为线性变换矩阵，本文中假设其为离散傅里叶（DCT）变换矩阵，原始稀疏向量和对其进行DCT变换之后和全观测数据如下图所示：



在压缩感知中，我们希望通过对的线性变换减少观测数据的数目。例如，令矩阵，使得，并假设矩阵是由矩阵随机选择行元素所生成。利用矩阵对原始稀疏数据进行线性变换之后得到压缩之后的观测数据：

    (2)

不失一般性，我们假设，即我们观测到40%的数据。这些数据如下图所示。



其中，为了便于对比，把的数据进行了重新排序，使得其数据与的数据位置对位。例如，矩阵的第行数据在矩阵中的位置为第行，则。这样，我们得到一个与全观测数据对位的压缩数据。

实时上，如果不进行排序对位，M=80个数据取决于随机产生的A中的行向量，如下图（第2个子图）所示



如果给定压缩之后的观测数据，如何恢复原始数据呢？

为了恢复，我们构建如下的稀疏恢复优化问题：

    (3)

然而，上述优化问题是非凸优化问题，其求解为NP-hard，难以直接求解。为了求解，我们将它转化为优化问题：

    (4)

该问题为凸优化问题，因而可以有效求解。求解方法有多种，我们采用最经典的算法，即将其转化为线性规划求解。具体而言，可以将范数转化为如下等效表示方式：

    (5)

这样，问题（4）可以转化为：

(6)

 问题（6）是线性规划，可以很容易求解得到最优解。则问题（4）的最优解为：

      (7).

应用上述算法，得到如下图所示的恢复结果。



如果改变M的数值，恢复效果如何呢？下面我们改变M的数值，可以看到，当M<40时，无法精确恢复原始信号。

 



 

Summary： 利用压缩感知，可以大幅度减少采样数据点，从而实现稀疏数据量的压缩。当然，这种压缩不是任意小，而是要有最小观测数据量的保证。最后，给出一张本次实例的全家福。

本质上是两个问题。如果一定要找联系，两者都涉及数据的稀疏表达。



压缩感知解决“逆问题”：Ax=b。对于欠定的线性系统，如果已知解具有稀疏性（sparsity），稀疏性可以作为约束或者正则项，提供额外的先验信息。线性逆问题和稀疏性在这类问题中的应用有相对完整的理论体系，楼上 yang liu推荐的 Michael Elad的书是很好的入门教材。


另一类关系密切的问题是低秩矩阵恢复(low-rank matrix recovery)，使用low-rank作为先验知识，解关于矩阵的线性逆问题，发展出一套理论。


压缩感知的思想被应用在了更多的领域，比如非线性逆问题。相关的理论正在快速的发展，但是应用已经领先一步。我个人感兴趣的是双线性逆问题（bilinear inverse problem），比如盲反卷积（blind deconvolution）、矩阵分解(matrix factorization)。


在应用压缩感知的过程中，我们发现大部分信号本身并不是稀疏的（即在自然基下的表达不是稀疏的）。但是经过适当的线性变换后是稀疏的（即在我们选择的另一组基（basis）或者框架（frame，我不知道如何翻译）下是稀疏的）。比如谐波提取（harmonic retrieval）中，时域信号不稀疏，但在傅里叶域信号是稀疏的。再比如大部分自然图像不是稀疏的，但经过DCT（离散余先变换）或者wavelet transform（小波变换），可以得到稀疏的表达。一个一度非常热门的研究课题是字典学习（Dictionary Learning）和变换学习（Transform
 Learning），通过大量的信号实例，自适应地学习稀疏性表达。



深度学习是机器学习的一种手段，参见楼上Stephen Wang的解释。深度学习中通常都涉及非线性环节。这里数据表达的目的通常不再是数据恢复（recovery），而是分类（classification）等机器学习的任务。



下面是我理解的区别：

在信号处理中的稀疏表达学习（sparse representation learning）侧重对信号建模，即目标是获取原信号的一个忠实的表达（faithful representation）。我们通常需要变换和逆变换，来实现信号的重建（reconstruction）。即使在不需要重建的问题中，我们也需要这种表达能够很好地区分有意义的信号和无意义的噪声（discriminate signal against noise）。所以这类变换通常有很多良好的性质（可逆、很好的条件数（condition numer）等）。

深度学习或者更广泛的机器学习中，数据表达的目标因问题而异，但是通常我们都不需要这种表达过程的可逆性。比如在分类问题中，我们的目标是把数据变换到有“意义”的空间，实现不同类别信号的分离。这种变换可以是线性或非线性的，可以是可逆或不可逆的，可以变换到稀疏的表达或其他有意义的便于分类的表达。

压缩感知笔记
CS理论认为，我们可以从比奈奎斯特采样所需的更少的样本中恢复某些信号。如果信号在原始域或变换域中是稀疏的（完全恢复）或可压缩的（近似恢复），我们可以用比奈奎斯特采样所需的更少的采样样本对其进行采样，并保持原信号的绝大部分信息。
**核心

**压缩感知（CS）主要利用测量矩阵和表示矩阵之间的非相干性（incoherence）。在CS框架下测量矩阵和表示矩阵之间的低相干性表示可以用更少的采样重建原始信号。
s-稀疏

如果一个信号只有s个非零系数，则称该信号为s-稀疏信号。如果大部分映射系数小到可以忽略不记，则称该信号是可压缩的（compressible）。
限制等距性(RIP)

被广泛用于评估压缩感知重建算法性能的工具。
随机测量

只要φ满足以下条件，就可以对任意基的s-稀疏信号进行随机测量：
                       	  m = s*log(n/s)

基追踪

根据现有文献，测量矩阵φ可以是高斯、伯努利、傅里叶或非相干测量矩阵。对于一类被称为基追踪的重构算法表明，大多数s稀疏信号都可以精确恢复，只要确保
		                      m >= 4*s

重建模型
在接收端采用一种非线性算法重建原始信号。这种非线性重建算法需要了解信号稀疏(精确恢复)或可压缩(近似恢复)的表示基(原始域或转换域)，即最终目的是得到x，用已知的Ψ恢复出X。感兴趣信号为X，则可用表示基表示为：
							  Ψx = X

其中x是s-稀疏向量，表示X在Ψ上的投影稀疏。

因此测量向量Y可以写成x的形式：
							   Y = Θx

其中Θ = ΦΨ，是m×n维的重建矩阵。CS中的重构算法，尝试求解上式，并利用解是稀疏的这一事实，通常通过最小化解空间上的l0、l1或l2范数。根据经典的最小二乘解（l2范数的最小化），重建解可表示为：



类似地，通过使用l1最小化或BP，正如在CS文献中所知，通过线性规划解决一个简单的凸优化问题，信号可以从’ m '测量值精确恢复。一些重构技术是基于l0最小化的。


然而，由于现实世界中绝大多数信号都不是稀疏的，而是可压缩的，l2最小化通常不能给出较好的结果。另一方面，l0最小化则能给出较为准确地结果，但这是一个NP难题，因此很多文献采用l1最小化，因为它在很多情况下能给出与l0相同的结果。
虽然最小化的基本概念是所有求解框架的共同概念，但在求解范数最小化方程的方法中存在着变量。
重建算法
文献中存在许多有效的算法，它们不是同时找到“m”个最大的系数，而是尝试迭代地找到这些系数。为了对CS稀疏信号恢复的重构算法进行概述，这些算法大致可以分为六种，如下图：