布赖恩是当场的。但我认为添加一些压缩感知上下文是有帮助的。

首先，请注意所谓的 0 norm $\|x\|_0$ - 基数函数，或$x$中非零值的数量-不是 norm。最好把它写成$\mathop{\textbf{card}}(x)$之类的东西，除了最随意的上下文。不要误会我的意思，当你使用$\|x\|_0$速记时，你是一个很好的伙伴，但我确实认为它会引起混乱。

人们早就知道，最小化$\ell_1$范数$\|x\|_1$往往会产生稀疏解。这有一些与线性互补性有关的理论原因。但最有趣的不是解是稀疏的，而是它们通常是最稀疏的。也就是说，在某些有用的情况下，最小化$\|x\|_1$ 确实为您提供了最小基数解决方案。（当最小基数问题是 NP-hard 时，他们是如何计算出来的？通过用已知的稀疏解构建人为问题。）这不是线性互补理论可以预测的。

当研究人员开始识别矩阵上的条件时，压缩感知领域诞生了，这将允许他们提前保证\解也是最稀疏的。例如，参见Candés、Romberg 和 Tao的最早论文，以及其他关于受限等距属性或 RIP的讨论。如果您真的想深入了解一些理论，另一个有用的网站是Terence Tao 的压缩感知页面。$A$$\ell_1$

我们希望能够解决

$\min \| x \|_{0}$

英石

$Ax=b$

、和具有压缩感知中典型的大小时，在实践中解决它是不切实际的。可以有效解决$A$$x$$b$

$\min \| x \|_{1}$

英石

$Ax=b$

在理论上（可以在多项式时间内完成）和计算实践中，即使是压缩感知中出现的相当大的问题。我们使用作为 \| 的“代理。中非零条目较少的解决方案），以及更复杂的理论理由（形式为“如果具有 k 稀疏解，则最小化将很有可能找到该解决方案。” $\| x \|_{1}$$\| x \|_{0}$$x$$Ax=b$$\| x \|_{1}$

在实践中，由于数据经常是嘈杂的，精确的约束经常被替换为。 $Ax=b$$\| Ax - b \|_{2} \leq \delta$

处理约束问题的变分形式也很常见，例如我们可以最小化。$\min \| Ax - b\|_{2}^{2} + \lambda \| x \|_{1}$

对于 Brians 和 Michaels 关于与的解释，我没有什么要补充的。但由于问题似乎是关于压缩感知我想补充我的观点：压缩感知既不是关于解决 也不是关于 Compressed Sensing 更像是一种范式，可以非常粗略地表述为$\ell^1$$\ell^0$

可以从几次测量中识别稀疏信号。

压缩传感实际上是尽可能少地进行测量来识别某一类信号中的信号。

一个朗朗上口的短语是：

为什么你的 5 兆像素相机真的要测量 1500 万个值（每个像素三个），而当它只存储大约 2 兆字节（压缩后）时，它会花费你 15 兆字节的数据？
是否可以立即测量 2 兆字节？

可能有完全不同的框架：

• 线性测量
• 非线性的（例如“无相”的）
• 矢量数据，矩阵/张量数据
• 稀疏性只是非零的数量
• 稀疏性为“低等级”甚至“低复杂性”）。

还有更多计算稀疏解决方案的方法，如匹配追踪（正交匹配追踪 (OMP)、正则化正交匹配追踪 (ROMP)、CoSaMP 等变体）或基于消息传递算法的更新方法。

如果人们仅用 - 或 -最小化来识别压缩感知，那么在处理实际数据采集问题时就会失去很大的灵活性。$\ell^1$$\ell^0$

然而，如果一个人只对获得线性系统的稀疏解感兴趣，那么可以做一些我称之为稀疏重建的事情。