RIP 如何保证稀疏解的唯一恢复大号1L1最小化?

信息处理 凸优化 压缩传感
2022-02-10 20:38:13

我们有一个传感矩阵Φ, 满足受限等距属性 (RIP)和稀疏信号x. 我们想恢复x^从测量y=Φx通过使用l1-最小化。

我想知道,RIP如何保证恢复的稀疏向量解的唯一性x^.

在幻灯片 4 上,01:15 分钟,Mark Davenport 在他关于压缩感知的演讲中说:

RIP 是我们需要确保的,该超平面以某种方式定向,向我们保证,该超平面中实际上只有一个稀疏向量。因此,我们将保证得到正确的答案。

但这是为什么呢?我看不到 RIP 可以保证这一点。

例如,考虑下面这张图片。这是链接演示文稿中的一张幻灯片。蓝色超平面还与至少一个其他轴相交。我们怎么能确定,这个其他稀疏向量不是实际的解决方案,即是我们以前的信号x?

Mark Davenports 幻灯片的屏幕截图

1个回答

压缩感知理论(例如参见Candès & Wakin,2008 年)指出,如果您有足够的测量值y,如图1最小化问题恢复x恰好有很高的概率。这意味着您的正确解决方案必须具有最小的可能1规范。

如图所示;这 ”1球”与给定的平面相交Φx=y在这一点上x用最小的1规范。正如您所提到的,还有其他稀疏解决方案 - 即平面与其他两个轴相交的解决方案。正如我们从图中可以想象的那样,这些点具有更大的1规范,因此不是正确的解决方案。