约束等距性

假设我们有：

其中x∈R^n是我们希望重建的对象，y∈R^m是可用的测量，并且Φ是已知的m×n矩阵。 在这里，我们感兴趣的是方程数比未知数更少的欠定情况，即m <n，问题是是否有可能以良好的精度重建x。 因此，问题当然是不适定的（ill-posed），但现在假设x已知稀疏或几乎稀疏，因为它仅依赖于较少数量的未知参数。 这个前提从根本上改变了问题，使搜索解决方案变得可行。 事实上，我们已经证明解决方案x*为：

可以准确地恢复x，给定 1）x足够稀疏2）矩阵Φ服从被称为有限等距性质的条件。我们将对这个条件进行介绍。

为了说明这个问题，我们首先回顾有限等距常数（restricted isometry constants）的概念。

定义1.1：对于每个整数s = 1,2，...，将矩阵Φ的有限等距常数\delta_s定义为最小数，使得：

适用于所有s-稀疏（s-sparse）向量。 如果向量具有最多s个非零条目（entries），则称该向量是s-稀疏的。

这一定义不仅涉及稀疏矢量，而是涉及所有矢量x∈R^n。并且为了测量重建的质量，我们将比较重建x *与最佳稀疏近似，后者如果人们确切知道x的s-largest的位置和幅度，可以很容易获得，我们在之后将用x_s表示，即矢量x除了s-largest的条目之外的所有条目都设置为零。

定理1.1（无噪声恢复）假设\delta_{2s}<√2 - 1.然后x*的解服从：

其中C_0是下面明确给出的一些常数。 特别是，如果x是s-稀疏的，则恢复是准确的。

当我们把讨论限制在x稀疏的情况，实际上我们想要找到Φ\tilede{x} = y的最稀疏解并求解（注意此时l_1变为l_0）：

这是一个很难求解的问题。 但是，通过定理1.1我们可以断言，l_0和l_1问题在以下意义上实际上是相等的：

• 如果\delta_{2s}<1，则l_0问题具有唯一的s-稀疏解;
• 如果\delta_{2s}<√2 - 1，那么l_1问题的解是l_0问题的解。

实际上，如果\delta_{2s}<1，任何s-稀疏解都是唯一的。 在另一个方向上，假设\delta_{2s}= 1.那么Φ的2s列可以是线性相关的，在这种情况下存在2s-稀疏矢量h服从Φh= 0。然后可以将h分解为x-x‘，其中x和x都是 x’是s稀疏的。 这给出Φx=Φx‘，这意味着不能通过任何方法重建所有s稀疏矢量。

总结一下，RIP性质只要要求0<\delta<1就可以了，而RIC是指满足RIP的最小\delta。整个式子可以视为信号跟传感矩阵的相似程度，也就是做完转换后的能量，要被RIP限制住。

[描述来源：Candes, E. (2008). The restricted isometry property and its implications for compressedsensing. Comptes Rendus Mathematique. 346(8-9): 589-592.]

发展历史

RIP是压缩感知领域的一个重要概念，主要可以被用来分析还原算法的表现好坏。

2005年，Emmanuel Candès、陶哲轩提出了当\delta_{2s}<1时可以保证(P0)有唯一解，并且用反证法对此问题进行了证明，大概思路是假设有两个解，会发现从RIP性质的不等式中可以得出这两个解是相等的。2006年，Emmanuel Candès、陶哲轩和David Donoho证明了在已知信号稀疏性的情况下，可能凭借较采样定理所规定更少的采样数重建原信号，这一理论也是压缩感知的基石。

2007年，Richard Baraniuk等人提出了一种简单的技术，用于验证压缩感知基础的随机矩阵的RIP性质。 2008年，Emmanuel Candès证明了当\delta_{2s}<1时可以保证零范数问题有唯一的稀疏解，而当\delta_{2s}s<sqrt(2)-1时则可以保证零范数（l_0）和1范数（l_1）等价。零范数求解为NP-hard问题，在此前提下将其转化为1范数求最优化问题，这时是个凸优化，对于求解很有帮助。

主要事件

发展分析

瓶颈

RIP是一种性质，其本身不存在瓶颈，但是在其主要应用的感知压缩领域，我们往往面临着许多困难，例如重建的过度复杂性，存储的大量空间需求，以及没有有效的算法来验证感测矩阵是否满足具有小RIC值的RIP属性。

未来发展方向

RIP 的提出是在当时数据获取模式先采样再压缩，需要大量的时间压缩和空间存储数据的背景下，因此任何能够有助于高速信号处理的发展的算法都是值得研究的。

Contributor: Yuanyuan Li