前言
 
最近因为科研需要，又开始重新研究压缩感知（CS）与稀疏恢复（SR）理论。本人系初学，很多东西都没有学明白，姑且先摸着石头过河，仿照网上的例子，用matlab编程实现最基本的例子，写下了这篇笔记。
 
原理
 
关于压缩感知与稀疏恢复的原理就不再赘述，网上有很多博主写的很详细，这里推荐https://zhuanlan.zhihu.com/p/22445302
 这篇文章原理写的通俗易懂。本文在这篇文章的基础上结合https://blog.csdn.net/xiahouzuoxin/article/details/38820925所给出的代码，形成了我自己的理解。
 
信号模型
 
这里选择比较简单的信号形式：一些单音正弦信号叠加。选取两个单音正弦信号，频率为10Hz和15Hz，幅度分别为1.5V和1V，当然这些参数在代码中都是可调的。两个信号时域图如下所示：
 
 叠加后时域图如下：
 
 信号的最大频率为15Hz，根据奈奎斯特采样定理，最小采样速率为两倍最大频率，即N_fs=30Hz。事实上，计算机中无法处理模拟信号，上面两张图是用非常高的采样速率（3kHz）得到的，因此看起来像是模拟信号。
 
为了减少计算机的工作量，将采样速率降低为fs=600Hz，采样时宽为T=5s。信号采样结果如下所示（时间截断到1s）。和上图相比，看起来没什么信息损失。
 
 用fft加fftshift的方法（不知道的可以翻我的matlab专栏关于画频谱的），绘制该信号的双边频谱如下图所示（只显示100Hz以内）。
 

 可以看到大约在10Hz和15Hz有两根谱线，幅度对应大约0.75和0.5，这正是我们设定的两个单音正弦信号叠加。（双边频谱非0频处幅度要乘以2）
 数据不准确（栅栏效应）以及下方旁瓣效应是因为采样频率和时宽不够大，深层次的原因是计算机中无法真正仿真模拟信号和无限长信号。
 
符号定义
 
为了方便理解文章和代码，我使用的是压缩感知理论中惯用符号说明，正如知乎中“稍有常识的人”说写的：
 
 
$x$——时域信号，长度为N
 $y$——观测信号，长度为M，应有M<<N
 $S$——频域信号，具有稀疏性（本例中只有两个频率）
 $\Psi$（Psi）——稀疏基矩阵N$\times$N，这里表示频域转换到时域，有$x=\Psi S$
 $\Phi$（Phi）——观测（测量）矩阵M$\times$N，表示压缩的过程，后面细讲。
 $\Theta$（Theta）——传感矩阵（亦称感知矩阵）M$\times$N，有$\Theta =\Phi \Psi$，这样等式就可以简化为$y=\Theta S$
 
矩阵向量应该加粗非斜体的，懒得弄了凑合看吧
 
稀疏基矩阵的构建
 
在本例中，$\Psi$的构建代码为Psi=inv(fft(eye(N,N)));
 表示对单位阵求离散傅里叶变换后再求逆。
 先讲一点前置知识，对于长度为N的时域离散信号$x$来说，其离散傅里叶变换为$S$，那么它可以写成$S=\text{fft}(x)$，也可以写成$S=\text{fft}(I)x$，其中$I$表示N$\times$N的单位阵。根据离散傅里叶变换的定义可知，它是从0到N-1的乘积求和累加，而求和累加的过程可以视为矩阵中行向量乘以$x$列向量。而由于单位阵，稀疏基矩阵中只有旋转因子$W_N^k$，因此时域信号左乘$\text{fft}(I)$就相当于做了傅里叶变换。
 因此，将傅里叶变换的矩阵求个逆，就是逆傅里叶变换，即$x=\Psi S$
 
稀疏矩阵的物理意义，就是把要采样的信号变换到另一个域中，而在这个域中，信号是稀疏的。在本例中，信号在时域并不稀疏，通过傅里叶变换变换到频域后就成为稀疏信号了。同理，也可以使用小波变换、余弦变换等，只要变换后的向量是稀疏的即可。
 
观测矩阵的构建
 
观测矩阵这里面有很深的学问，我还没了解清楚。我找到了一篇学长的硕士毕业论文以供参考
 【吴赟.压缩感知测量矩阵的研究[D]. 西安电子科技大学硕士学位论文，2012】
 大致来讲（可能说的不对，还请批评指正）
 Candes、Romberg和Tao指出，要想能解出$y=\Theta S$，传感矩阵$\Theta$需要满足有限等距性质(Restricted Isometry Property,Rip)
 参考自：
 E．Candes，J．Romberg，T．Tao．RobuSt uncertainty principles：Exact signal reconstruction from highly incomplete frequency information．IEEE Transactions on Information Theory,2006，v01．52，no．3，PP．489-509．
 
E．Candes，T．Tao．Decoding by
 linear programming．IEEE Transactions on Information Theory,2005，v01．51，no．12，PP．4203-4215．
 
但是，上述只是一个理论设想，实际上要直接验证矩阵是否满足RIP条件是一件很困难的事情。在实际应用中，我们可以用RIP准则的一种等价情况，即非相干性来指导测量矩阵的设计。所谓非相干性(Incoherence)，是指矩阵$\Phi$的行向量不能用矩阵$\Psi$中的列向量稀疏表示。
 
而Donoho等人指出，服从高斯分布的随机矩阵可以很大概率上满足上述条件，因此随机高斯测量矩阵是常用的测量矩阵，本例中也使用该测量矩阵。
 
 截图源自学长的论文
 
matlab生成随机高斯测量矩阵的代码：Phi=sqrt(1/M)*randn(M,N);
 
上述知乎文章中提到，这个测量矩阵的物理意义是对时域信号的随机亚采样(不等间距采样)，但是我搜集了很多资料，还是不能理解这个测量矩阵是如何做到随机采样的，而且比较疑惑测量向量$y$是如何得出来的。现有代码中都是提前知道了$x$,然后用$y=\Theta S$得出，但是实际中得到$x$的过程本身就已经完成了过采样，那还要压缩感知做什么？
 如果测量矩阵$\Phi$是一个N$\times$N的单位阵，那么压缩感知就退化成了普通的采样过程。
 
稀疏恢复
 
好，现在问题来了。已知测量向量$y$和传感矩阵$\Theta$，且有$y=\Theta S$，如何求解出稀疏向量$S$？
 这就是稀疏恢复问题。
 我之前发过的一篇论文研究过这个稀疏恢复问题，当时是使用极大极小值优化算法，感兴趣的可以了解一下：
 J. Chen et al., “A Sparsity Based CFAR Algorithm for Dense Radar Targets,” 2020 IEEE Radar Conference (RadarConf20), 2020, pp. 1-6, doi: 10.1109/RadarConf2043947.2020.9266526.
 本例中等式不含噪声，我就偷个懒，用matlab的CVX凸优化工具箱。这个工具箱需要安装，先在官网上下载，然后百度一下教程，很容易就安装好了。
 
由于信号在频域稀疏，即$S$是一个稀疏信号，因此优化的目标函数可以是$S$的零范数或者一范数，一范数更好求解一些，因此一范数更常用，具体的数学原理我也不会不讲 。
 
最终求解的问题如下
 $$min||S|{|}_1$$
 $$subjecttoy=\Theta S$$
 
matlab代码如下：
 
%%使用cvx凸优化工具箱
cvx_startup;
cvx_begin
    variable Sp(N) complex;%定义待求解的变量
    minimize(norm(Sp,1));%一范数约束表示提高稀疏性
    subject to
        Theta*Sp==y;%约束条件
cvx_end
 
优化结果$S_p$并不是真正稀疏的，其中大部分值都是极其接近于0而不等于0，这些显然应该为0的值，需要我们手动置零来避免其干扰。判定哪些值需要置零而哪些值不需要置零，需要我们设定一个阈值，我这里简单的用$3\sigma$法则设定，即threshold=3*std(abs(Sp));别问为什么，问就是一切皆高斯分布
 
低于阈值以下的值置零，就可以更准确的得到稀疏向量解$S_p$。
 最后用ifft将频域解变换到时域（或者左乘$\Psi$也行），恢复出最终的时域采样结果。
 
仿真结果分析
 
对上述信号进行压缩感知与稀疏恢复处理，恢复出的结果$S_p$与真值$S$进行比较，得到下图：
 
 可以看到恢复精度还是很高的。稀疏恢复解有一些毛刺，阈值处理可以很好的消除。
 转换到时域观察结果
 
 曲线几乎完全重合，使用均方根误差(RMSE)来评估精度，计算出RMSE=0.070639
 由于使用的是随机高斯测量矩阵，因此每次试验的值都不一样，但总体RMSE是很低的，表明恢复良好。
 
之前提到，奈奎斯特采样频率为N_fs=30Hz，时宽为T=5s，因此采样点数为150个点，这是经典理论中要求最少的采样点数。
 稀疏恢复理论中指出，观测长度M>=K*log(N/K),K是稀疏度,N信号长度,可以近乎完全重构。在本例中K=2，N=3000，计算出M最小为15。由于要采样的信号不是真正的模拟信号，频域并不是完全稀疏，因此M应该大一些，本例设置为M=30。
 
对比压缩感知与经典采样理论可以发现，前者只需要长度为30的观测向量，而后者需要长度为150的采样点。压缩感知可以减少80%的采样点，而恢复精度很高，这无疑是一个巨大的进步。
 
代码
 
https://download.csdn.net/download/weixin_42845306/20325903
 
本人尚在初学阶段，难免会有理解错误。如有问题或建议，欢迎评论区留言！

 原文链接：http://blog.csdn.net/chulefei/article/details/51251916
 

 
 
 一、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哪些是真实信息，也就是决定信号是否可以压缩以及压缩后是否可以恢复，Φ可以是随机的矩阵。

压缩感知——简介
 
压缩感知，compressed sensing又称compressed sampling，是在采样过程中完成了数据压缩的过程。
 压缩感知在信号采样的过程中，用很少的采样点，实现了和全采样一样的效果。
 
压缩感知——信号采样
 
学过通信原理或信号与系统的都知道奈奎斯特采样定理，即想让采样之后的数字信号完整保留原始信号中的信息，采样频率必须大于信号中最高频率的2倍。原因是时域以τ为间隔进行采样，频域会以1/τ为周期发生周期延拓。那么如果采样频率低于两倍的信号最高频率，信号在频域频谱搬移后就会发生混叠。
 2004年，Candes，陶哲轩和Donoho提出了压缩感知理论，该理论认为：如果信号是稀疏的，那么它可以由远低于采样定理要求的采样点重建恢复。
 突破的关键就在于采样的方式。当我们说“采样频率”的时候，意味着做的是等间距采样，数字信号领域通常都是做等间距采样，也服从奈奎斯特采样定律。
 
 但是压缩感知采用不等间距采样，比如采用随机亚采样（图b上方的红点），那么这时候频域就不再是以固定周期进行延拓了，而是会产生大量不相关（incoherent）的干扰值。如图c，最大的几个峰值还依稀可见，只是一定程度上被干扰值覆盖。这些干扰值看上去非常像随机噪声，但实际上是由于三个原始信号的非零值发生能量泄露导致的（不同颜色的干扰值表示它们分别是由于对应颜色的原始信号的非零值泄露导致的）
 之所以随机亚采样会有这样的效果，可以理解成随机采样使得频谱不再是整齐地搬移，而是一小部分一小部分胡乱地搬移，频率泄露均匀地分布在整个频域，因而泄漏值都比较小，从而有了恢复的可能。
 
压缩感知——信号恢复
 
压缩感知——两个前提条件
 
刚刚的例子之所以能够实现最终信号的恢复，是因为它满足了两个前提条件：
 
这个信号在频域只有3个非零值，所以可以较轻松地恢复出它们。
采用了随机亚采样机制，因而使频率泄露均匀地分布在整个频域。
 这两点对应了CS的两个前提条件——稀疏性（sparsity）、不相关性（incoherence）。
 稀疏性可以简单直观地理解为：若信号在某个域中只有少量非零值，即信号在某个域中非零点远远小于信号总点数，那么它在该域稀疏，该域也被称为信号的稀疏域。
 因此，第一个前提条件要求信号必须在某一个变换域具有稀疏性。比如例子中，信号在频域是稀疏的，因而可以通过所述的重建方法轻松地在稀疏域（频域）复原出原信号。
 然而通常信号在变换域中不会呈现完全的稀疏性。其实只要它近似满足稀疏性，即大部分值趋于零，只有少量大的非零值，就可以认为它是可压缩信号，可以对它进行CS亚采样。
 对于之前讲的例子，如果它在频域中不稀疏，我们可以做DWT、DCT等，找到它的稀疏变换。
 
前提条件1——稀疏性
 
前提条件2——非相关性/等距约束性
 
在讲第二个前提条件之前，需要引入必要的数学表达。
 
 上面这张图把亚采样的过程用矩阵的方式表达出来：
 如图，x是为长度N的一维信号，也就是原信号，稀疏度为k。此刻它是未知的。
 Φ为观测矩阵，对应着亚采样这一过程。它将高维信号x投影到低维空间，是已知的。
 y=Φx为长度M的一维测量值，也就是亚采样后的结果。显然它也是已知的。
 因此，压缩感知问题就是在已知测量值y和测量矩阵Φ的基础上，求解欠定方程组y=Φx得到原信号x。
 然而，一般的自然信号x本身并不是稀疏的，需要在某种稀疏基上进行稀疏表示。令x=Ψs，Ψ为稀疏基矩阵，s为稀疏系数。
 于是最终方程就变成了：y=ΦΨs。已知y、Φ、Ψ，求解s。
 y=ΦΨs有点长，我们把ΦΨ合并成一个矩阵，称之为传感矩阵。即令Θ=ΦΨ ，则y=ΘS。问题即为，已知y和Θ，求解S。
 对应到一开始的例子中：
 x就是三个正弦信号叠加在一起的原信号a；
 稀疏矩阵Ψ就是傅里叶变换，将信号变换到频域S；
 观测矩阵Φ就是我们采用的随机亚采样方式；
 y就是最终的随机亚采样的结果c。
 
 求解出S后，由x=Ψs即可得到恢复出的原信号x。
 然而在正常情况下，方程的个数远小于未知数的个数，方程是没有确定解的，无法重构信号。但是，由于信号是K稀疏，如果上式中的Φ满足有限等距性质(RIP)，则K个系数就能够从M个测量值准确重构（得到一个最优解）。
 陶哲轩和Candès证明了RIP是观测矩阵要满足的准确要求。但是，要确认一个矩阵是否满足RIP非常复杂。于是Baraniuk证明：RIP的等价条件是观测矩阵和稀疏表示基不相关（incoherent）。即压缩感知的第二个前提条件。
 
 
 那怎样找到不相关的观测矩阵呢？陶哲轩和Candès又证明： 独立同分布的高斯随机测量矩阵可以成为普适的压缩感知测量矩阵。
 于是满足高斯分布的随机测量矩阵就成了CS最常用的观测矩阵。
 对于二维信号，往往就采用二维高斯随机测量采样矩阵对图像进行亚采样。
 对于一维信号，采用前文提到的随机不等间距的亚采样即可。
 
压缩感知——重建方法
 
信号采样后需要将其恢复。CS的重建也就是求解欠定方程组y=ΘS的方法。这是一个零范数（l0）最小化问题，是一个NP完全问题（没有快速解法的问题），因此往往转换成一范数（l1）最小化的求解，或者用一些近似估计的算法。
 匹配追踪是一种典型的算法。以上文中的例子为例：
 (1) 由于原信号的频率非零值在亚采样后的频域中依然保留较大的值，其中较大的两个可以通过设置阈值，检测出来（图a）。
 (2) 然后，假设信号只存在这两个非零值（图b），则可以计算出由这两个非零值引起的干扰（图c）。
 (3) 用a减去c，即可得到仅由蓝色非零值和由它导致的干扰值(图d），再设置阈值即可检测出它，得到最终复原频域（图e）
 (4) 如果原信号频域中有更多的非零值，则可通过迭代将其一一解出。
 
 
扩展：图像压缩与压缩感知
 
信号的稀疏性已经在图像压缩领域有了很广泛的应用。利用信号的稀疏性，可以对信号进行压缩。如图像压缩领域的JPEG格式，就是将图像变换到离散余弦域，得到近似稀疏矩阵，只保留较大的值，从而实现压缩。
 图像压缩和压缩感知这两个概念有着本质上的区别。
 图像压缩是先进行了全采样，然后再变换域丢弃小系数，完成压缩；
 而压缩感知不同，它的思想其实从图像压缩中借鉴了很多：既然全采样了还要再丢弃，我们为什么不能直接少采样一些点？因此，压缩感知直接进行了亚采样，然后再用算法消除亚采样导致的伪影。可以说，压缩感知直接在采样时就完成了压缩。
 
 这种直接减少采样点，采集完后重建的方式，相比于图像压缩的全采用之后再压缩的方式，对于很多情形，比如照相机拍摄照片，并没有优势。因为所有像素的采集在一瞬间就都完成了。但是对于一些采集比较慢的情形，比如核磁共振成像，CS就可以发挥巨大优势。原本一副MRI图像常常需要几十秒，速度慢也是MRI的一大缺陷。而应用CS技术后，只需要采集全采样几分之一的数据，就可以重建出原图。这样就可以把成像速度提高好几倍，同时对图像质量影响不大。
 
总结
 
什么是压缩感知：
 如果一个信号在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号。
 压缩感知理论主要包括三部分：
 （1）信号的稀疏表示；
 （2）设计测量矩阵，要在降低维数的同时保证原始信号x的信息损失最小；
 （3）设计信号恢复算法，利用M个观测值无失真地恢复出长度为N的原始信号。
 
从06年提出至今，已经发展出了很多算法，原来的基于l1 minimization的BP算法很慢，现在都是快速算法，而且求解算法也从纯优化方面扩展到了estimation方面，有很多基于贝叶斯估计的方法了，目前最火的也是Donoho他们组搞得AMP算法，是用Graph model里面的message passing算法通过近似求解MMSE（MAP）解。在测量矩阵方面，也已经设计出了各种矩阵，除了i.i.d. Gaussian的矩阵还有很多正交的矩阵，比如partial random DFT/DCT 矩阵。对信号的要求也从稀疏变成了存在某种结构，比如low rank，group sparse等等。（2017年进展）
 
压缩感知和矩阵填充
 
矩阵填充的要领是通过低秩矩阵中的已知要素还原出该矩阵的其他未知要素的进程。这几年，关于矩阵填充方法的理论研究成为压缩感知技术的一个研究热点。在实际的应用领域中涉及对高维数据的分析与处理，可以运用矩阵填充的方法来解决。其过程主要是：通过观测到的局部数据来准确填充缺失数据,从而获得完整数据矩阵的过程。
 压缩感知和矩阵填充都是稀疏约束下的反问题，压缩感知利用信号本身或在变换域中的稀疏约束性求解欠定方程，矩阵填充利用矩阵的低秩约束性求解欠定方程。
 压缩感知理论的核心问题是信号的稀疏表示、观测矩阵的设计和重构算法，信号本身或在变换域中的系数越稀疏，观测矩阵和稀疏基构成的压缩感知矩阵的受限等距常数越小，则压缩感知的性能越好。
 矩阵填充理论的核心问题是矩阵的低秩特性、非相干特性和重构算法，寻找性能良好的重构算法一直是矩阵填充理论中的一个研究重点。此外，压缩感知的应用领域已经拓展得较为广泛，但矩阵填充的应用尚处于起步阶段，挖掘矩阵填充的应用，进而将矩阵填充和压缩感知结合起来进行应用方面的探索，是非常重要和有意义的课题。
 压缩感知的性能取决于3个要素：信号的稀疏性、压缩感知矩阵的非相干性和重构算法的快速有效性。
 矩阵填充性能也取决于3个要素：矩阵的低秩性、矩阵的不相关性和重构算法的快速有效性。
 
低秩矩阵
 
还记得我们怎么手工求矩阵的秩吗？为了求矩阵A的秩，我们是通过矩阵初等变换把A化为阶梯型矩阵，若该阶梯型矩阵有r个非零行，那A的秩rank(A)就等于r。从物理意义上讲，矩阵的秩度量的就是矩阵的行列之间的相关性。如果矩阵的各行或列是线性无关的，矩阵就是满秩的，也就是秩等于行数。回到上面线性方程组来说吧，因为线性方程组可以用矩阵描述嘛。秩就表示了有多少个有用的方程了。上面的方程组有3个方程，实际上只有2个是有用的，一个是多余的，所以对应的矩阵的秩就是2了。
 OK。既然秩可以度量相关性，而矩阵的相关性实际上就表示了矩阵的结构信息。如果矩阵之间各行的相关性很强，那么就表示这个矩阵实际可以投影到更低维的线性子空间，也就是用几个向量就可以完全表达了，它就是低秩的。所以我们总结的一点就是：如果矩阵表达的是结构性信息，例如图像、用户-商品推荐表等等，那么这个矩阵各行之间存在这一定的相关性，那这个矩阵一般就是低秩的。
 如果X是一个m行n列的数值矩阵，rank(X)是X的秩，假如rank (X)远小于m和n，则我们称X是低秩矩阵。低秩矩阵每行或每列都可以用其他的行或列线性表出，可见它包含大量的冗余信息。利用这种冗余信息，可以对缺失数据进行恢复，也可以对数据进行特征提取。
 
应用
 
矩阵填充越来越多的应用在协同滤波、系统识别、无线传感网络、视频去噪、人脸识别、医学成像等领域，正在发挥着巨大的作用。特别是在室内定位中的 应用越来越多，是当下的研究热点之一。
 
参考网址：
 形象易懂讲解算法II——压缩感知（非常好）
 AndyJee：浅谈压缩感知系列——博客园（非常丰富）
 压缩感知理论
 机器学习——低秩矩阵分解中低秩的意义、矩阵填补、交叉验证

1. 稀疏表示与字典学习
 
当样本数据为稀疏矩阵时，对学习任务有不少好处：
 
可以使许多问题变得线性可分
使存储更为高效
稀疏矩阵：矩阵的 每一行/列都包含大量的零元素， 且这些零元素没有出现在同一行/列中。（非零元素远小于零元素）
 
字典学习：侧重于为普通稠密表达的样本找到一个合适的矩阵
 
稀疏表示：将样本转化为合适的稀释表示形式，从而使学习任务变得简单
 
变量交替优化策略
2. 压缩感知
 
压缩感知在前些年也是风风火火，与特征选择、稀疏表示不同的是：通过欠采样信息来恢复全部信息。在实际问题中，为了方便传输和存储，我们一般将数字信息进行压缩，这样就有可能损失部分信息，如何根据已有的信息来重构出全部信号，这便是压缩感知的来历，压缩感知的前提是已知的信息具有稀疏表示。
 
通过已知的欠采样信息求出稀疏样本表示，然后通过稀疏基求得原信号。
 
压缩感知分为“感知测量”和“重构恢复”两部分：
 
感知测量：关注如何对原始信号进行处理以获得稀疏样本表示
重构恢复：关注的是如何基于稀疏性从少量观测样本中恢复原信号
>> 矩阵补全的方法