下载文档原格式
压缩感知，又称压缩采样，压缩传感。
它作为一个新的采样理论，它通过开发信号的稀疏特性，在远小于Nyquist 采样率的条件下，用随机采样获取信号的离散样本，然后通过非线性重建算法完美的重建信号[1]。
压缩感知理论一经提出，就引起学术界和工业界的广泛关注。
他在信息论、图像处理、地球科学、光学/微波成像、模式识别、无线通信、大气、地质等领域受到高度关注，[2]并被美国科技评论评为2007年度十大科技进展。
编辑本段基本知识现代信号处理的一个关键基础是Shannon 采样理论：一个信号可以无失真重建所要求的离散样本数由其带宽决定。
但是Shannon 采样定理是一个信号重建的充分非必要条件。
在过去的几年内，压缩感知作为一个新的采样理论，它可以在远小于Nyquist 采样率的条件下获取信号的离散样本，保证信号的无失真重建。
压缩感知理论一经提出，就引起学术界和工业的界的广泛关注。
[3]压缩感知理论的核心思想主要包括两点。
第一个是信号的稀疏结构。
传统的Shannon 信号表示方法只开发利用了最少的被采样信号的先验信息，即信号的带宽。
但是，现实生活中很多广受关注的信号本身具有一些结构特点。
相对于带宽信息的自由度，这些结构特点是由信号的更小的一部分自由度所决定。
换句话说，在很少的信息损失情况下，这种信号可以用很少的数字编码表示。
所以，在这种意义上，这种信号是稀疏信号（或者近似稀疏信号、可压缩信号）。
另外一点是不相关特性。
稀疏信号的有用信息的获取可以通过一个非自适应的采样方法将信号压缩成较小的样本数据来完成。
理论证明压缩感知的采样方法只是一个简单的将信号与一组确定的波形进行相关的操作。
这些波形要求是与信号所在的稀疏空间不相关的。
压缩感知方法抛弃了当前信号采样中的冗余信息。
它直接从连续时间信号变换得到压缩样本，然后在数字信号处理中采用优化方法处理压缩样本。
这里恢复信号所需的优化算法常常是一个已知信号稀疏的欠定线性逆问题。
压缩感知简介 压缩感知（也称为压缩感知、压缩采样或稀疏采样）是⼀种信号处理技术，通过寻找⽋定线性系统的解决⽅案来有效地获取和重构信号。
这是基于这样的原理，即通过优化，可以利⽤信号的稀疏性从⽐Nyquist-Shannon 采样定理所需的样本少得多的样本中恢复它。
有两种情况可以恢复。
第⼀个是稀疏的，这要求信号在某些域中是稀疏的。
第⼆个是不相⼲性，它通过等距属性应⽤，这对于稀疏信号来说已经⾜够了。
概述 信号处理⼯程领域的⼀个共同⽬标是从⼀系列采样测量中重建信号。
⼀般来说，这项任务是不可能的，因为在未测量信号的时间内⽆法重建信号。
然⽽，通过对信号的先验知识或假设，可以从⼀系列测量中完美地重建信号（获取这⼀系列测量称为采样）。
随着时间的推移，⼯程师们对哪些假设是实⽤的以及如何推⼴它们的理解有所提⾼。
信号处理的早期突破是奈奎斯特-⾹农采样定理。
它指出，如果真实信号的最⾼频率⼩于采样率的⼀半，则可以通过sinc 插值完美地重构信号。
主要思想是，利⽤关于信号频率约束的先验知识，重构信号所需的样本更少。
⼤约在 2004 年，Emmanuel Candès、Justin Romberg、Terence Tao和David Donoho证明，在了解信号稀疏性的情况下，可以使⽤⽐采样定理所需更少的样本来重建信号。
这个想法是压缩感知的基础。
历史 压缩传感依赖于其他⼏个科学领域在历史上使⽤过的技术。
在统计学中，最⼩⼆乘法由L1-norm，由Laplace引⼊。
随着线性规划和Dantzig单纯形算法的介绍，L1-norm ⽤于计算统计。
在统计理论中，L1-norm 被George W. Brown和后来的作者⽤于中值⽆偏估计量。
它被Peter J. Huber 和其他从事稳健统计⼯作的⼈使⽤。
L1-norm 也⽤于信号处理，例如，在 1970 年代，地震学家根据似乎不满⾜Nyquist-Shannon 标准的数据构建了地球内反射层的图像。
压缩传感实现方法的研究的开题报告一、选题背景及意义在现代工业生产和智能化控制中，传感器的应用越来越广泛，传感器的性能对系统的精度和可靠性起着至关重要的作用。
传感器数据的精度和可靠性是评估传感器性能的主要指标之一，因此传感器信号压缩技术的研究具有重要的实际意义。
传感器信号压缩不仅可以有效提高数据传输效率，减少数据存储所需的空间，还可以减小干扰和误差，提高传感器的动态响应性能，提高数据采集和处理的效率，降低系统成本等。
二、研究现状目前传感器数据压缩技术主要有基于小波的压缩方法、基于压缩感知的压缩方法和基于自适应压缩的压缩方法等。
其中，基于小波的压缩方法是传感器压缩技术中应用最广泛的一种方法，它通过对信号进行小波变换，将其转换为频域信号，在保证一定误差范围内的前提下，通过对高频信号的压缩和削弱，达到数据压缩的目的。
基于压缩感知的压缩方法则是通过构造小样本矩阵，利用随机测量矩阵将传感器数据线性压缩成远小于原始数据容量的稀疏向量。
而基于自适应压缩的压缩方法则是在压缩过程中根据信号特征动态调整压缩参数。
三、研究内容及目标本研究将基于小波的压缩方法和自适应压缩的方法进行结合，提出一种改进的传感器信号压缩方案，并对其进行优化和分析。
具体研究内容包括：1、研究小波变换在传感器信号压缩中的特点及应用；2、分析自适应压缩方法在传感器信号压缩中的特点及应用；3、提出一种基于小波的自适应压缩方法，并进行仿真分析；4、结合示例进行性能评估和优化研究；5、开展实验验证，并与其他方法进行比较分析。
本研究目标是在传感器信号数据压缩中提高数据处理效率和信号压缩比例，提高数据的可靠性和精度，减少传感器信号数据传输和存储所需的空间和成本，为工业生产和智能控制提供有效支撑。
四、研究方法本研究采用实验和仿真相结合的方法，首先对传感器性能进行评估和比较分析，然后针对传感器数据的特点，结合小波变换和自适应压缩方法，提出一种压缩方案，并进行性能分析和优化，最后进行实验验证。
压缩传感●中国压缩传感资源（China Compressive Sensing Resources） (1)一、引论与综述 (1)二、理论分析与观测矩阵 (1)三、恢复算法 (2)四、信号与图像处理 (2)五、物理与化学 (3)六、博客分享 (3)七、程序与软件包 (3)●压缩感知 compressive sensing 的一点背景 (3)●Compressed sensing (4)●中国压缩传感资源（China Compressive Sensing Resources）/viewthread.php?tid=861902为了进一步促进中国压缩传感理论的研究和资源共享，为了进一步方便研究者查找相关文献，也为了激发广大科研工作者对该领域的研究热情，我们将列出所有中国学者（包括香港、澳门和台湾）在该领域的贡献，其形式包括：期刊论文，会议论文，研究报告，笔记，程序，软件包，个人博客等等。
所有资源的尽量以时间为先后顺序，贡献不分大小。
如发现连接错误，或者想提供建议和新的资源连接，请与我们联系。
我们将持续更新此页面，直到该领域在中国的发展已全面展开。
请大家不要回复该帖子。
我们的联系方式：wsha@eee.hku.hk。
目前列出论文约30篇，到150篇时，此贴将不再更新（因为国内研究工作已经全面展开）。
一、引论与综述1 石光明，刘丹华，高大化，刘哲，林杰，王良君，压缩感知理论及其研究进展，/grid2008/de ... 027&dbname=CJFQTEMP2 李树涛，魏丹，压缩传感综述，/qikan/manage/wenzhang/2008-0751.pdf3 喻玲娟，谢晓春，压缩感知理论简介，/Periodical_dsjs200812005.aspx4 沙威，压缩传感引论，http://www.eee.hku.hk/~wsha/Free code/Files/Compressive_Sensing.pdf5 Dai Qi and Wei E.I. Sha, The Physics of Compressive Sensing and the Gradient-Based Recovery Algorithms, /abs/0906.1487二、理论分析与观测矩阵1 方红，章权兵，韦穗，基于非常稀疏随机投影的图像重建方法，/Periodical_jsjgcyyy200722008.aspx2 方红，章权兵，韦穗，基于亚高斯随机投影的图像重建方法，/Periodical_jsjyjyfz200808016.aspx3 Lianlin Li, Yin Xiang, and Fang Li, Theoretical Analysis of Compressive Sensing via Random Filter, /abs/0811.01524 Xiao Z. Wang and Wei E.I. Sha, Random Sampling Using Shannon Interpolation and Poisson Summation Formulae, /abs/0909.2292三、恢复算法1 方红，章权兵，韦穗，改进的后退型最优正交匹配追踪图像重建方法，/Periodical_hnlgdxxb200808005.aspx2 傅迎华，可压缩传感重构算法与近似QR分解，/grid2008/detail.aspx?filename=JSJY200809033&dbname=CJFQ20083 Lianlin Li and Fang Li, Novel Algorithm for Sparse Solutions to Linear Inverse Problems with Multiple Measurements, /abs/0905.32454 Lianlin Li and Fang Li, A Novel Algorithm for Compressive Sensing: Iteratively Reweighed Operator Algorithm (IROA) , /abs/0903.49395 Yin Xiang, Lianlin Li, Fang Li, Compressive sensing by white random convolution, /abs/0909.2737v16 范晓维，刘哲，刘灿，分块可压缩传感的图像重构模型，/kns50/detail.aspx?QueryID=17&CurRec=1四、信号与图像处理1 李波，谢杰镇，王博亮，基于压缩传感理论的数据重建，/grid2008/detail.aspx?filename=WJFZ200905006&dbname=CJFQTEMP2 宋琳，曹吉海，基于随机滤波的雷达信号采样和目标重建方法，/Periodical_kjdb200813014.aspx3 Jianwei Ma, Compressed sensing by inverse scale space and curvelet thresholding, /files/cs/Iss_Curvelet.pdf4 Wen Tang, Jianwei Ma, and Felix J. Herrmann, Optimized compressed sensing for curvelet-based seismic data reconstruction, /files/cs/OPCRSI3.pdf5 Jianwei Ma, Improved iterative curvelet thresholding for compressed sensing, /files/cs/ISTcs2.pdf6 Gerlind Plonka and Jianwei Ma, Curvelet-wavelet regularized split bregman iteration for compressed sensing, http://www.uni-due.de/~hm0029/pdfs/SPB_IST7.pdf7 练秋生，郝鹏鹏，基于压缩传感和代数重建法的CT图像重建，/grid2008/detail.aspx?filename=GXJS200903029&dbname=CJFQ20098 方红，王年，章权兵，韦穗，基于稀疏贝叶斯学习的图像重建方法，/Periodical_zgtxtxxb-a200906009.aspx9 刘丹华，石光明，周佳社，高大化，吴家骥，基于Compressed Sensing框架的图像多描述编码方法，/grid2008/detail.aspx?filename=HWYH200904013&dbname=CJFDTEMP10 刘长红，杨扬，陈勇，基于压缩传感的手写字符识别方法，/grid2008/detail.aspx?filename=JSJY200908017&dbname=CJFDTEMP11 练秋生，高彦彦，陈书贞，基于两步迭代收缩法和复数小波的压缩传感图像重构，/Periodical_yqyb200907017.aspx12 刘兆霆，何劲，刘中，基于压缩感知的高分辨频率估计，/kns50/detail.aspx?QueryID=90&CurRec=113 侯颖妮，李道京，洪文，基于稀疏阵列和压缩感知理论的艇载雷达运动目标成像研究，/kns50/detail.aspx?QueryID=90&CurRec=2五、物理与化学1 Lianlin Li, Wenji Zhang, and Fang Li, Compressive Diffraction Tomography for Weakly Scattering, /abs/0904.26952 Lianlin Li, Wenji Zhang, Yin Xiang, and Fang Li, The Design of Compressive Sensing Filter, /abs/0811.26373 Lianlin Li, Wenji Zhang, and Yin Xiang, The Design of Sparse Antenna Array, /abs/0811.07054 Jianwei Ma and Francois-Xavier Le Dimet, Deblurring from highly incomplete measurements for remote sensing, /files/cs/CS_Deblurring.pdf5 Jianwei Ma, Single-pixel remote sensing, /files/cs/GRSL.pdf六、博客分享1 李廉林，/2 马坚伟，/dynctr/faculty/teacher.asp?id=363 桂冠，/4 刘翼鹏，/yipengliu/blog5 沙威，/waveletlegend七、程序与软件包1 正交匹配算法为信号重建，沙威，http://www.eee.hku.hk/~wsha/Freecode/Files/CS_OMP.rar2 图像压缩传感通过正交匹配追踪和正交小波变换，沙威，http://www.eee.hku.hk/~wsha/Freecode/Files/Wavelet_OMP.zip压缩感知 compressive sensing 的一点背景采样定理（又称取样定理、抽样定理）是采样带限信号过程所遵循的规律，1928年由美国电信工程师H.奈奎斯特首先提出来的，因此称为奈奎斯特采样定理。
“压缩传感”引论香港大学电机电子工程学系高效计算方法研究小组沙威 2008年11月20日Email: wsha@eee.hku.hkPersonal Website: http://www.eee.hku.hk/~wsha到了香港做博士后，我的研究领域继续锁定计算电磁学。
我远离小波和计算时谐分析有很长的时间了。
尽管如此，我仍然陆续收到一些年轻学者和工程人员的来信，和我探讨有关的问题。
对这个领域，我在理论上几乎有很少的贡献，唯一可以拿出手的就是几篇网上发布的帖子和一些简单的入门级的代码。
但是，从小波和其相关的理论学习中，我真正懂得了一些有趣的知识，并获益良多。
我深切地感到越来越多的学者和工程师开始使用这个工具解决实际的问题，我也发现互联网上关于这方面的话题多了起来。
但是，我们永远不能只停留在某个阶段，因为当今学术界的知识更新实在太快。
就像我们学习了一代小波，就要学习二代小波；学习了二代小波，就要继续学习方向性小波（X-let）。
我也是在某个特殊的巧合下不断地学习某方面的知识。
就像最近，我的一个友人让我帮她看看“压缩传感”（Compressive Sensing）这个话题的时候，我的兴趣又一次来了。
我花了一个星期，阅读文献、思考问题、编程序、直到写出今天的帖子。
我希望这篇帖子，能对那些没进入且迫切想进入这个领域的学者和工程师有所帮助。
并且，我也希望和我一个星期前一样，对这个信号处理学界的“一个大想法”（A Big Idea）丝毫不了解的人，可以尝试去了解它。
我更希望，大家可以和我探讨这个问题，因为我到现在甚至不完全确定我对压缩传感的某些观点是否正确，尽管我的简单的不到50行的代码工作良好。
在这个领域中，华裔数学家陶哲轩和斯坦福大学的统计学家David Donoho 教授做出了重要的贡献。
在这个引言中，我用简单的关键字，给出我们为什么需要了解甚至是研究这个领域的原因。
那是因为，我们从中可以学习到，下面的这些：矩阵分析、统计概率论、拓扑几何、优化与运筹学、泛函分析、时谐分析（傅里叶变换、小波变换、方向性小波变换、框架小波）、信号处理、图像处理等等。
压缩传感总结报告摘 要 随着信息技术的不断发展，人们对信息需求量越来越大，这给信号采样、传输和存储的实现带来的压力越来越大。
传统的采样方法容易造成信息的冗余，因此，人们寻求新的方法避免信息的冗余。
压缩传感的问世，打破了常规的信号处理的思路，它将压缩和采样合并进行，突破了香农采样定理的瓶颈。
本文主要围绕稀疏表示、编码测量、重构算法三个方面对压缩传感进行基本的介绍。
最后介绍了压缩传感的应用以及展望。
关键词 压缩传感，稀疏表示，编码测量，重构算法1 引言传统的信号获取和处理过程主要包括采样、压缩、传输和解压缩四个部分。
其采样过程必须满足香农采样定理, 即采样频率不能低于模拟信号频谱中最高频率的2倍。
在信号压缩中,先对信号进行某种变换,如离散余弦变换或小波变换, 然后对少数绝对值较大的系数进行压缩编码, 舍弃零或接近于零的系数。
通过对数据进行压缩,舍弃了采样获得的大部分数据, 但不影响“感知效果”[1]。
但是，信号压缩实际上是一种严重的资源浪费，因为大量的采样数据在压缩过程中被丢弃了，而它们对于信号来说是不重要的或者只是冗余信息。
从这个意义而言，可得到以下结论：带宽不能本质地表达信号的信息，基于信号带宽的Nyquist 采样机制是冗余的或者说是非信息的。
如果信号本身是可压缩的, 那么是否可以直接获取其压缩表示(即压缩数据),从而略去对大量无用信息的采样呢？换句话说，是否存在一种基于信息的采样理论框架，使得采样过程既能保持信号信息，又能只需远少于Nyquist 采样定理所要求的采样数目就可精确或近似精确重建原始信号？Cand és 在2006年从数学上证明了可以从部分傅立叶变换系数精确重构原始信号, 为压缩传感奠定了理论基础。
Cand és 和Donoho 在相关研究基础上于2006年正式提出了压缩传感的概念。
其核心思想是将压缩与采样合并进行,首先采集信号的非自适应线性投影(测量值), 然后根据相应重构算法由测量值重构原始信号[7]。
“压缩传感”引论香港大学电机电子工程学系高效计算方法研究小组沙威 2008年11月20日Email: wsha@eee.hku.hkPersonal Website: http://www.eee.hku.hk/~wsha到了香港做博士后，我的研究领域继续锁定计算电磁学。
我远离小波和计算时谐分析有很长的时间了。
尽管如此，我仍然陆续收到一些年轻学者和工程人员的来信，和我探讨有关的问题。
对这个领域，我在理论上几乎有很少的贡献，唯一可以拿出手的就是几篇网上发布的帖子和一些简单的入门级的代码。
但是，从小波和其相关的理论学习中，我真正懂得了一些有趣的知识，并获益良多。
我深切地感到越来越多的学者和工程师开始使用这个工具解决实际的问题，我也发现互联网上关于这方面的话题多了起来。
但是，我们永远不能只停留在某个阶段，因为当今学术界的知识更新实在太快。
就像我们学习了一代小波，就要学习二代小波；学习了二代小波，就要继续学习方向性小波（X-let）。
我也是在某个特殊的巧合下不断地学习某方面的知识。
就像最近，我的一个友人让我帮她看看“压缩传感”（Compressive Sensing）这个话题的时候，我的兴趣又一次来了。
我花了一个星期，阅读文献、思考问题、编程序、直到写出今天的帖子。
我希望这篇帖子，能对那些没进入且迫切想进入这个领域的学者和工程师有所帮助。
并且，我也希望和我一个星期前一样，对这个信号处理学界的“一个大想法”（A Big Idea）丝毫不了解的人，可以尝试去了解它。
我更希望，大家可以和我探讨这个问题，因为我到现在甚至不完全确定我对压缩传感的某些观点是否正确，尽管我的简单的不到50行的代码工作良好。
在这个领域中，华裔数学家陶哲轩和斯坦福大学的统计学家David Donoho 教授做出了重要的贡献。
在这个引言中，我用简单的关键字，给出我们为什么需要了解甚至是研究这个领域的原因。
那是因为，我们从中可以学习到，下面的这些：矩阵分析、统计概率论、拓扑几何、优化与运筹学、泛函分析、时谐分析（傅里叶变换、小波变换、方向性小波变换、框架小波）、信号处理、图像处理等等。
所以，我们有什么理由，拒绝这个有意思的东西呢？让我们开始吧。
传统思路——正交变换对于一维的信号1×∈N R x ，大多数情况下，信息是冗余的。
我们可以通过正交变换的方法来压缩它。
正变换：x y Ψ=，反变换y x H Ψ=。
这里，I H H =ΨΨ=ΨΨ，N N C ×∈Ψ，I 是单位矩阵。
对于1×∈N C y ，能量较x 集中，本质上去除了x 中的相关性。
因此，我们只保留K 个较大的分量，而把其它K N −个置为零。
通过反变换，我们能够近乎完美的重建原始信号。
因为，那K N −个变换域系数的贡献，实在微乎其微。
具有这样性质的信号被称为K “稀疏”（Sparsity）的。
于是，我们有了如下编码解码的策略： 编码：构造Ψ，做正变换x y Ψ=，保留y 中最重要的K 个分量，和其对应的位置。
解码：把K 个分量放回到对应的位置，其它位置填0，构造H Ψ，反变换y xHˆˆΨ=。
而解码能否近乎得到原始信号呢？显然，我们希望δ≤−=−22||ˆ||||ˆ||y y xx ，δ是一个小的常数。
但更有效的是用相对误差δ≤−22||||/||ˆ||y yy 。
但这种编码解码方法有些缺点：1、考虑到香农（Shannon）采样定理，为了获得很好的信号分辨率，采样间隔会很小，造成了原始信号长度会很长，因此变换过程会消耗很长的时间。
2、K 个需要保留的重要分量的位置，是随着信号的不同而不同的。
因此，这种策略是“自适应”（Adaptive）的，且需要分配多余的空间存储这些位置。
3、一旦在传输过程中K个分量中的某几个丢失了，后果可想而知。
如果我们制作一个音频设备，1将带来电力的消耗和用户的不满，2将带来存储空间的增加，3将带来较差的抗干扰能力。
新的思路——压缩传感压缩传感（Compressive Sensing）是一个很有意思的新的方向。
它也正成为信号处理领域的“A Big Idea”。
对于信号1×∈N Rx ，我们可以找到它的M 个线性测量（Liner Measurement），x s Φ=。
N M R ×∈Φ。
这里，Φ的每一行可以看作是一个传感器（Sensor）,它与信号相乘，拾取（Acquisition）了信号的一部分信息。
拥有了这M 个测量和Φ，我们就可以近乎完美的重构原始信号了。
听起来“相当”传奇，事实上，它基于如下严格的数学最优化（Optimization）问题：目标函数0||ˆ||min y ，且满足等式约束s y H =ΦΨˆ 或者，可以写成 02||ˆ||||ˆ||min y ys H λ+ΦΨ−求解该最优化问题，得到变换域的yˆ，然后反变换，便可以得到时域的x ˆ。
公式中的2是我们熟悉的2-范数，而0是什么呢？是0-范数，也就是向量yˆ中非零元素的个数。
看起来很有道理，因为yˆ是待求的变换域向量，它是K 稀疏的。
使y ˆ非零元素的个数尽量小，也就是保留了尽量少的重要的K 个分量，显然这几个分量可以近乎完美重构x 。
我们回到传统的思路，这K 个分量是我们在变换域“自适应”找的，而该优化算法也可以使我们找到这K 个分量。
这就足够了吗？显然不行，我们仍然没有探讨测量矩阵Φ需要满足的性质。
我们用极限分析法。
如果我们把Φ构造成和HΨ极端相似（Coherence）的矩阵，也就是拿出Ψ的前M 行。
用这个算法求y ˆ，我们将得到⎟⎟⎠⎞⎜⎜⎝⎛=×−×1)(10ˆM N M s y ，这显然是错误的。
也就是说，你强迫的认为前M 个变换域分量是重要的。
而事实是，重要的K 个分量的位置我们事先是不知道的，是随着信号的不同而不同的。
当然，你可以将Φ恰好构造成对应最重要分量的K 行，得到正确的结果。
而这种的做法要付出的概率代价K NC 1。
也就是说，你必须穷举K N C 次，才能得到你想要的结果。
但是，即使你有幸碰到了它，也并不能肯定这个结果就是对的。
因此，我们选择Φ和HΨ极端不相似（Extremely Incoherence）。
于是，Φ很大程度上和随机（Randomness）这个词相联系，它可以是满足高斯分布的白噪声矩阵，或贝努里分布的1±矩阵（也称作Noiselet ）等等。
除此之外，我们希望线性测量有稳定的能量性质：δδ+≤ΦΨ≤−1||ˆ||||ˆ||122yy H ，也就是它要保持K 个重要分量的长度。
综合上面的，我们有了如下编码解码的策略：编码：构造Φ，生成测量x s Φ=，保留s 。
解码：构造同样的Φ，构造任一种正交变换H Ψ，根据s 重构x 。
压缩传感的优势：1、非自适应（Non-Adaptive）的，一开始就可以传输长度较短的信号，甚至突破采样定理的极限。
2、抗干扰，s 中任何一项都是重要的，或者说不重要的。
丢失了某几项，仍然可以完美重构。
它的缺点：1、实际中，s 的长度一般是重要分量长度的4倍，才能近乎完美重构。
数学上更严格的，K M 4≈或者)(log 2KN K M ≥。
2、重构（恢复）算法是NP 问题。
即使将0-范数转化为1-范数，由于其不可微性（Indifferentiable），算法的计算复杂度仍然很高。
它的应用前景广泛：低成本数码相机和音频采集设备；节电型音频和图像采集设备；天文（图像本身就稀疏，例如天空的星星）；网络；军事（用很简易的摄像机随机记录场景，可以完全重构军事地图）；超宽带（雷达信号处理）。
这里，值得指出的是，美国的工程学家已经设计出了实际的产品。
快速算法——正交匹配追踪对于0-范数的优化问题，实际上是NP 问题，就是在多项式时间内难以求解，甚至无法验证解的可靠性。
于是，我们必须将0-范数换一下，变成1-范数。
为什么不是2-范数呢，那样就会简单多了。
毕竟2-范数的优化问题可以转化成2次型问题，而1-范数，∑=i i y y|ˆ|||ˆ||1，在0点处不可导，因此无论是梯度算法、矩阵求导等等手段都变得相形见绌。
因此，基于1-范数的优化算法需要特殊处理，且复杂度很高。
下面我们来解释下为什么要用1-范数，而不是2-范数。
我们令恢复（Recovery）矩阵H T ΦΨ=，则等式约束可重写为：s y T =ˆ。
y ˆ中未知数有N 个，方程只有M 个，且N M <<。
因此，方程有无穷多解。
从几何上说，0ˆ=−s yT 是一个超平面，为了简化，在2-D 问题中（1=K ，y ˆ只有两个元素待求）可认为它就是一条直线。
而范数约束呢？0-范数是一个十字架，因此它的最外侧（范数的最小值）是4个点。
所以其和直线的交点，必然在坐标轴上。
也就是说，能使yˆ产生更多的0，这正是我们想要的“稀疏”的结果。
2范数是一个圆，因此它的最外侧边界和直线的交点（就是切线的概念），以压倒性的概率不在坐标轴上，除了直线的斜率恰好为0或者无穷大。
其实直线的斜率恰好为0或者无穷大，是不可能的，因为Φ和HΨ极端不相似。
只有Φ取Ψ的某一行时，两者相似，才会发生斜率恰好为0或者无穷大的情况（因此，你的胜算只有12/1C ，但你不知道哪个是对的。
）。
依上所述，用2-范数优化的结果，使yˆ几乎没有0，这是我们不期望的。
而1-范数是一个菱形，四个角都在坐标轴上，因此它和直线的交点以压倒性的概率落在坐标轴上。
这就是我们要用1-范数的原因。
事实上，p 范数满足，10<≤p ，它的外边界都向中心凹（Concave）。
而1>p ，外边界向外凸（Convex）。
所以前者的外边界和直线的交点无疑落在坐标轴上。
根据这个几何解释，我们可以将问题转化成：12||ˆ||||ˆ||min y yT s λ+−这显然是一个非线性（Non-Linear）的凸（Convex）优化问题。
众所周知，对于优化问题，我们一般用梯度的方法来求解。
而对1||ˆ||y，在0点导数不存在，因为这个点正好位于两条直线的交点上，左右导数不相等。
这也正是很多数学方法的考虑。
像子梯度（Subgradient）法、平滑近似法（Smooth Approximation）等等。
我们暂不谈这些方法，因为它需要特殊的数学背景。
我们谈一谈工程领域最常用的正交匹配追踪法（Orthogonal Matching Pursuit）。
它的思想本质上还是来自于这个K“稀疏”。
我们绕了一圈，还是为了找这K 个关键的分量。
既然是关键，显然它的系数的绝对值应该比其它K N −个分量大得多。
为了简单起见，我们先假设1=K ，唯一非零元素q y ˆ在y ˆ中对应的位置在q 。
于是y T ˆ就是恢复矩阵T 的第q 列q T 与y ˆ中的非零元素q y ˆ的乘积，即q q q s y T =ˆ。
