限定等距性是什么？保证压缩感知能准确恢复稀疏信号的条件

限定等距性（Restricted Isometry Property，RIP）是压缩感知理论中的一个核心概念，它描述了一个测量矩阵需要满足的条件：只要满足这个条件，就可以从远少于信号长度的测量中，准确地恢复出原本稀疏的信号。这一概念由 Emmanuel Candès 和陶哲轩在 2005 年前后提出。

从压缩感知说起

传统的信号采样遵循奈奎斯特-香农采样定理：要完整地记录一个信号，采样的频率至少要是信号最高频率的两倍。但很多实际的信号是“稀疏”的：在某种表示方式下，它的绝大部分系数都是零或者接近零，只有少数几个系数比较大。比如一张自然图像在小波变换之后，大部分系数都很小，这正是 JPEG 等图像压缩能够大幅减少数据量的原因。既然信号的真正信息量远小于它的长度，那么能不能在采样的时候就直接进行“压缩”，用很少的测量就把它记录下来？压缩感知理论给出了肯定的回答。2006 年前后，Candès、陶哲轩、Justin Romberg 和 David Donoho 等人奠定了这一理论。

在压缩感知中，用一个测量矩阵乘以原始的信号，得到数量少得多的测量值。从这些测量值反推原始信号，是一个方程数量少于未知数数量的问题，一般来说有无穷多个解。但如果知道原始信号是稀疏的，就可以在所有的解中寻找最稀疏的那一个。直接寻找最稀疏的解在计算上非常困难，但可以证明，在一定的条件下，求解一个 L1 范数最小化的凸优化问题，就能得到同样的结果。限定等距性就是保证这一切能够成立的关键条件之一。

限定等距性说的是什么

“等距”的意思是保持长度不变。如果一个矩阵乘以任何向量之后，向量的长度都保持不变，它就是一个等距变换，比如旋转。限定等距性的要求要宽松一些，“限定”体现在两个方面：第一，它只要求对那些稀疏的向量，也就是非零元素不超过 k 个的向量，近似地保持长度；第二，允许长度有一定的变化，变化的幅度被一个常数 δ 控制，矩阵作用后向量长度的平方，落在原来长度平方的 1 减 δ 倍到 1 加 δ 倍之间。δ 越小，矩阵越接近对稀疏向量的“等距”。

直观地理解：如果测量矩阵对所有稀疏向量都近似地保持长度，那么两个不同的稀疏信号，经过测量之后得到的结果也一定是不同的，而且差别不会被过度压缩，这样就能从测量结果中把它们区分开来，唯一地恢复出原始的信号。Candès 等人证明，如果测量矩阵满足 2k 阶的限定等距性，并且 δ 足够小，那么任何 k 稀疏的信号都可以通过 L1 最小化精确地恢复；即使信号只是近似稀疏、测量中带有噪声，恢复的误差也能被控制住。

什么样的矩阵满足这个条件

验证一个具体的矩阵是否满足限定等距性，在计算上是非常困难的。但一个重要的结论是：随机的矩阵，比如每个元素都独立地服从正态分布的矩阵，或者随机取正负 1 的矩阵，只要测量的数量与稀疏度乘以对数因子成比例，就以极高的概率满足限定等距性。这意味着随机地进行测量，反而是一种非常有效的压缩采样方式。

应用

压缩感知被应用于医学成像，尤其是核磁共振成像，减少扫描所需的测量次数，从而缩短扫描时间，美国食品药品监督管理局在 2017 年批准了基于压缩感知的快速核磁共振技术；以及单像素相机、雷达成像、天文观测、无线传感器网络等领域。限定等距性的思想也与机器学习中的随机投影降维，比如 Johnson-Lindenstrauss 引理，以及稀疏学习、Lasso 回归的理论分析密切相关。