稀疏性
如果一个信号的大部分组成均为零称之为稀疏。经验观察到许多真实世界的信号是可压缩的，在这个意义上，一般经过适当的基础变化它们近似于稀疏信号。这就解释了为什么压缩技术，如JPEG，MPEG，或MP3在实践中应用很好。例如，JPEG依赖于存在于离散余弦原则或小波原则图像中的稀疏度且只有存储最大时会成功压缩。
什么是压缩感知？
离散余弦或小波系数。其他系数简单地设置为零。我们参考图1.1做自然影
像在小波域中是稀疏的证明。
让我们再次考虑信号的采集和数据测量结果。使用额外知识这个信号是稀疏的或可压缩的，传统方法采用信号测量至少同等长度似乎在浪费资源：首先，测量所有信号的输入需要巨大的气力，然后大部分的相关系数在压缩版中被弃用。相反，我们可能想通过开发信号的稀疏性或可压缩性“直接”以明显较少的测量数据获得一个信号的压缩版。换句话说，我们想压缩感知可压缩的信号！这是压缩感知的基本目标。
我们强调在这里主要的困难存在于非零向量的输入位置在事先是不知道的。如果他们在那个位置，他们会通过位置设置检索轻易的减少矩阵的纵列。线性方程的解变成超定从而可以解决非零信号的输入。不知道重建的非零向量的位置提出了一些非线性因为s-sparse向量（那些有最多s非零系数）形成了一个非线性集。实际上，加入两个Ss-sparse向量通常会有一个2S-s-sparse向。因此，任何成功的重建方法都必须是非线性的。
直观地说，复杂性或压缩信号“固有的“信息内容比信号长度小得多（否则压缩不可能）。所以人们可能认为对比信号长度，所需的数据量（测量数目）更应该是与固有信息内容成比例的。不过，怎样在这种方案下成功重建还不是很快可知的。
通过对稀疏向量
在欠定测量
重建
的标准压缩感知问题仔细查看，可以基本确定两个问题：如何设计线性测量过程？换句话说，什么矩阵
是合适的？
?如何从y = ax中重建x？换句话说，什么是有效的重建算法？
这两个问题都不是完全独立的，由于重建算法需要考虑到A，但我们会发现从分析算法中单独分析矩阵A。
我们注意到第一个问题目前是不重要的。实际上，压缩感知并不适宜任意矩阵
。比如，如果A组成单位矩阵的组，则y = Ax简单的挑选了
一些X的输入，因此，它包含大部分的零输入。特别是关于在Y中X的非零输入将没有信息被获取，同时重建将不可能出现在如此的矩阵A中。
图1.2
底部：时域信号实部16个信号复原算法-设计测量矩阵的第一个问题是同样重要和微妙的。我们也强调矩阵A理论上同时为所有信号x设计，伴随一个非适应性测量过程，在某种意义上来说数据前观察到的数据论性能。
（如第j列的A）的测量方法不依赖于以
。结果显示，一般自适应测量不展现出更好的理
算法
为了实用的目的，合理有效的快速重建算法是必不可少的。这个特征无疑为压缩感知带来了如此多的关注。进入脑海的第一种算法可能是符号
最小化。引入
表示某向量的非零输入数量，很自然的试着重建X作为组合最优化优
化问题的一个解决方案。
图1.3 上：通过2-最小化简单重建
下：通过精确重建。
换句话说，我们寻找与实测数据并存的最稀疏向量y = Ax。不幸的是，最小化问题一般是困难的非确定性多项式问题。因此，令人吃惊的是确实存在快速和有效可证的建算法。一个非常受欢迎的和现在很好理解的方法是基追最小化，这个问题以寻找
的较小值为主要部分。因为
是一个凸函数。这个最优化问题
最小化的凸松弛。可选
可通过凸面最优化的有效方法解决。基追踪可解释为
择的重建方法包括贪心算法如正交匹配追踪，以及基于阀值的方法包括迭代硬阈值法。我们会发现通过适当的假设这些方法确实重建了稀疏向量。