更多细节可参考第5章和图1.8的数例。
虽然全顶级窗口在实践中工作良好，但是由于g是确定的，理论保证在现在可行性会稍微受限。作为一个与压缩感知理论并存的选择项，我们可以随机选取例如，一个独立±1项的伯努利向量。在这种情况下，如果s ≤ Cm/ lnm，g?Cm，
一个s级稀疏向量x?Cm可从y?Bx?Cm中还原。更多的信息见12章的注释部分。
抽样法理论
从样品的离散集中重建某连续时间信号是许多科学技术应用中的重要任务。包括图像处理、一般的传感器技术，以及模数转换，例如，出现在音频娱乐系统或移动通信设备。目前，大多数采样技术依靠香农采样定理，这表明一个带宽B的函数为了保证重建必须以2B比例采样。
数学术语表示，连续时间信号的傅里叶变换f?L1(R)（表示由
?(?)?f(t)e?2?it?dt, ??R定义f(t)dt??） f??RR如果f的取值范围[?B,B]，f是关于带宽B受带限。 香农取样原理陈述这样的f可以通过公式
从它的离散集取样来重组。
其中sinc函数以形式给出。
为方便压缩感知对比，我们将香农取样原理设置在一个有限维中。我们考虑三角多项式的最大度数M，即，函数类型
用度数M代替带宽B。因为三角形多项式最大度数M存在维度N = 2M + 1，则期望f可以由N = 2M + 1个信号重建。实际上，附录中的 C.1定律表明
其中狄利克雷DM由公式：
给出
因为维度原因，从少于N = 2M + 1样本中将最大维度M的三角形多项式重建是不可能的。然而，实践证明度数M的需求量可能很大，因此信号的样本数量也很大，有时候显著大于实际上的信号数。所以问题在于是否可通过利用附加的假设减小信号的数量。例如傅里叶域的可压缩性在很多现实情况下是合理的假设。实际上，如果(1.6)中傅里叶系数f的向量x?CN是稀疏（可压缩的），很少的信号就可以满足准确的（或近似的）重建。
精确来说，给予一个信号点集{t1, . . . , tm} ? [0, 1]，我们可以用向量
表示
y=Ax （1.7）
其中是一个傅里叶矩阵带有项
问题从M信号的向量Y中还原出F降为找到系数向量X。这意味着解一个当
m < N时的不定线性方程组。利用稀疏假设，我们得到标准压缩感知问题。可运用一些算法，如最小化来解决问题。关键性的问题集中在信号点的选取。由前面
可知，随机性可起作用。实际上，我们在第12章中看到，在[0, 1]中一致独立地随机选取信号t1, . . . , tm，如果m ≥ Cs ln(N)，则从信号f(t1), . . . , f(tm)中重建f的可能性最大。因此，如果S很小，少量的信号就足够了。这已经在图1.2和1.3中证明。
稀疏逼近
压缩感知以经验观测值为基础，许多不同种类的信号可以通过稀疏信号使之近似。在这种情况下，压缩感知可以被理解为系数逼近的子域。在稀疏逼近中有一个类似于标准压缩感知问题特殊的问题：当m 假设一个向量 （通常是应用中的一个信号或图像）可用规定元素 的线性组合表示。这样跨度为 。系统 (a1, . . . , aN)一般称为一个程序库。因为已知N > m，注意到系统可能线性相关（多余的）。当线性无关限定过多时，我们需要多余性。例如，时间频率分析中，时间频率基础改变元素只有在产生很少的时间频率才成为可能，即巴里安–低定理。很多基准的组合也很有趣。这种情况下，其表达式 不是唯一的。传统上来说，通过用最小数量的项也就是最稀疏替代来改进它。 让我们以a1, . . . , aN 构造矩阵 。找到Y的最稀疏表示意味 着解决了 如果我们允许一个表示误差η，然后考虑到轻微的改变最佳选择问题 问题(P0)和先前部分遇到的是一样的。一般来说两种最优问题(P0) 和(P0,η)是非确定性多项式困难问题，但是所有出现在这本书中标准压缩感知问题算法包括l1最小化，可应用于这种环境下，去克服计算上的瓶颈。确保了最稀疏向量x的精确或逼近还原的情况A将在第4、5和6章中被导出，它仍然是适用的。 然而对比压缩感知问题，稀疏逼近在原理上有许多不同之处，稀疏逼近一般设计任意的 含有适当特性的矩阵A，同时A一般考虑到稀疏逼近的环境，像压缩感知一样依赖随机性是不可取的。因为它很难证明在最优参数方法中确保稀疏还原（s中m的线性取决于对数因子），理论保证不足于解随机矩阵。这个法则的例外之处在14章谈到。其复原保证来自于随机选取的信号。 稀疏逼近和压缩感知的第二个不同之处出现在目标错误估计。压缩感知中，我们一般关心系数水平中的错误 ，其中X和 是各自初始的和重建系 ，所 数向量，而在稀疏逼近中，目标是近似给予的Y和稀疏扩张以我们对 感兴趣。关于 的估计让步于 的估计，但是反过来一般不对。 最后我们简单的讨论一些信号和图像进程的稀疏逼近应用。 ? = Ax?的稀疏逼近y?。接着?压缩。假设我们找到了一个信号Y和系数向量x?意味着只用存储非零系数x?。由于x?是稀疏的，相比原始信号Y项的存储，存储y?只需要非常小的内存。 x? = y + e，e表示噪音向量其?去噪。假设我们研究一个信号Y的噪音版本y中e??，接下来任务是去除噪音和原始信号Y的较好逼近。一般来说，如果对y一无所知，这个问题是不适定的。然而，假设y可以利用稀疏扩张很好表示。一 ?的一个稀疏逼近。更精确的，我们理论上选取la最小种合理的方法包含在选取y?。??Ax?作为降噪?中的y来代替已知的信号y化问题(P0,η)的解x接着我们构造y后y的版本。对于一个便于处理的计算方法，它通过一种压缩感知（稀疏逼近）算法代替了非确定性多项式困难问题(P0,η)，例如，l1最小化变量重点考虑噪音，或者叫做基追踪降噪问题。 ?数据分离。假设一个向量 是两个或多个成分的组成。这个问题 出现在一些信号进程任务中。例如，天文学家想在图像的细微处分离点体系（星， 星系团）。一个声音处理任务包含从短波中分离和声部分（纯正弦波）。没有附加的假设，这些分离问题是不适定的。然而，如果两种组分y1 和 y2在程序库中有不同特性（例如正弦波和尖峰信号）的分开的表达方式(a1, . . . , aN1)和(b1, . . . , bN2)。接着环境变化了。我们可以写 其中矩阵向量 条件下确定系数向量X，以此导出两种组分 。 有纵列a1, . . . , aN1 , b1, . . . , bN2。 稀疏。压缩感知方法允许在一定 和 数据纠正 在一般现实数据传输装置中，偶尔会出现部分数据错误。为了克服这种不可避免的事情，一种策略是收集这这些错误确保他们以后不经常出现。 假设我们要传输一个向量 。一种标准策略是编码长度N=n + m， B?RN?n的向量v?Bz?RN。直观的，B（考虑到N >n）中可以帮忙辨认出传输 错误。数目m反应出余部的总量。 假设接收测量w?V?x?Rm 其中x表示传输错误。假设在转化成x的稀疏度时传输错误不会经常发生，表示为x0?s。对于编码部分，我们构建一个矩阵 A?Rm?N叫做广义校验矩阵，令AB = 0，也就是说，所有行的A和所有列的B垂直 相交。然后我们构建广义校验 y=Aw=A（v+x）=ABz+Ax=Ax 我们使用矩阵A得到标准压缩感知问题和稀疏错误向量X。在适当的条件下，这本书中的方法允许还原X和相应的原始传输向量v = w – x。然后解过定方程