稀疏恢复中的相干性恢复保证

在许多科学和工程领域，我们都面临着从不完整的测量数据中重建信号或图像的挑战。稀疏恢复的突破性进展表明，如果我们寻求的信号具有简单的结构——即仅由少数几个基本元素构成——这是可能实现的。但这也带来了一个关键问题：我们如何能确定我们的测量过程能够唯一地识别出这少数几个元素，而不会被模糊性所迷惑？本文通过引入一个基础概念来填补这一知识空白：基于相干性的恢复保证。

接下来的章节将引导您深入了解这一强大的思想。在“原理与机制”一章中，我们将从数学上定义互相关性，探讨这个衡量测量向量之间“差异性”的简单度量如何为成功的信号恢复带来具体、可证明的保证。我们将揭示相干性与矩阵更深层次性质（如 spark）之间的优雅联系。然后，在“应用与跨学科联系”一章中，我们将看到该理论的实际应用，见证相干性如何为从单像素相机的设计、科学传感器的最优布置，到机器学习中高级字典学习算法的开发等各个方面提供指导。

想象一下，你是一名侦探，正在处理一桩奇特的案件。你唯一的证据是一张模糊的现场监控照片，照片上显示了几个涉案人员重叠的影子。你的任务是从一大群嫌疑人中找出他们。如果所有潜在的嫌疑人几乎都是同卵双胞胎，这个任务就不可能完成。他们影子的模糊组合什么信息也提供不了。但是，如果人群中的每个人都截然不同——一个高而瘦，一个矮而胖，第三个戴着一顶巨大的帽子——那么你就有机会了。即使从他们重叠模糊的影子里，你也可能推断出投下影子的究竟是哪些人的独特组合。

这正是我们在稀疏恢复中试图实现的核心目标。我们的“模糊照片”就是测量数据集 $y$。“嫌疑人”则是构成我们信号的基本特征，即​​原子​​。这些原子是我们测量矩阵 $A$ 的列向量 $a_j$。我们想要恢复的信号 $x$ 告诉我们哪些嫌疑人在场（非零项）以及他们的“量”是多少（这些项的值）。核心假设，也是使不可能变为可能的信念飞跃，是实际上只有少数几个嫌疑人在现场。我们称这个信号是​​稀疏的​​。

我们的核心挑战是设计一组尽可能彼此不同的“嫌疑人”——即我们的测量矩阵 $A$。我们需要一个系统，其中任何一个原子都不会轻易地被误认为是另一个原子，或者其他原子的组合。捕获这种“差异性”概念的简单、优雅且强大的思想就是​​相干性​​。

我们如何从数学上捕捉原子（它们只是高维空间中的向量）的“差异性”这一概念？最自然的工具是​​内积​​（或点积）。对于两个向量，内积衡量它们指向同一方向的程度。

在开始比较之前，有一个关键的整理步骤。一个高个子嫌疑人和一个矮个子嫌疑人是不同的，但如果其中一个只是另一个的放大版呢？为了确保对它们的基本形状进行公平比较，我们必须首先将它们归一化到相同的“尺寸”。在向量术语中，我们强制矩阵的每一列 $a_j$ 都具有单位长度，具体来说是单位 ​​$\ell_2$-范数​​：$\|a_j\|_2 = 1$。这一步不仅仅是为了数学上的便利，它是至关重要的。如果我们使用像 $\ell_1$-范数这样的非加权惩罚来寻找“最简单”的解，未归一化的列会隐式地使我们的搜索产生偏好，偏爱范数较大的原子，因为它们需要较小的系数来解释数据。归一化，或使用精心加权的目标函数，确保我们对“稀疏”的定义是公平且无偏的 [@problemid:3433076]。

当所有原子都归一化为单位长度后，它们的内积 $\langle a_i, a_j \rangle$ 的值就在 $-1$ 和 $1$ 之间。值为 $0$ 意味着它们完全​​正交​​——尽可能地不同。值为 $1$ 或 $-1$ 意味着它们相同（或方向完全相反），使它们无法区分。

现在我们可以定义一个单一的数字来表征我们整个测量系统。我们查看所有可能的不同原子对，并找到最相似的那一对。这种最坏情况下的相似性被称为矩阵 $A$ 的​​互相关性​​，记作 $\mu(A)$：

较小的 $\mu(A)$ 意味着我们所有的原子都很好地相互分离；这个字典是​​非相干的​​。较大的 $\mu(A)$ 意味着我们至少有一对原子危险地相似，这使得我们的侦探工作更加困难,。

那么，我们设计了一个具有极小相干性 $\mu(A)$ 的测量矩阵 $A$。这给我们带来了什么？它给我们带来了一个​​保证​​。一个保证，即如果真实信号 $x_0$ 足够稀疏，那么像​​基追踪（BP）​​（寻找具有最小 $\ell_1$-范数的解）或​​正交匹配追踪（OMP）​​（一种贪婪的迭代方法）这样的算法将能精确地找到它。

将相干性与恢复联系起来的优美而著名的结果是一个简单的不等式。如果信号中的非零项数量，即其稀疏度 $k$，满足

那么恢复就得到了保证,。

让我们来解读一下这个不等式。如果我们的字典完全非相干，即所有原子都是正交的，那么 $\mu(A) = 0$。不等式的右边会趋于无穷大，这告诉我们可以恢复任何稀疏度的信号，这是合理的，因为这只是一个标准基。更实际地看，如果 $\mu(A)$ 很小，比如 $\mu(A)=0.01$，那么 $1/\mu(A)=100$，我们可以恢复稀疏度高达 $k < \frac{1}{2}(101) = 50.5$ 的信号。因此，任何具有 50 个或更少非零项的信号都保证能被找到。如果相干性很差，比如 $\mu(A)=0.5$，那么 $k < \frac{1}{2}(1+2) = 1.5$，这意味着我们只能保证恢复 1-稀疏信号。

举一个具体的例子，考虑一个简单的 $3 \times 3$ 矩阵，其相干性为 $\mu(A) = \frac{1}{4}$,。条件变为 $k < \frac{1}{2}\left(1 + \frac{1}{1/4}\right) = \frac{1}{2}(1+4) = 2.5$。这个凭证以数学上的确定性告诉我们，任何用该系统测量的 1-稀疏或 2-稀疏信号都可以被完美恢复。

这个不等式并非魔法；它是通往我们测量矩阵几何学更深层次真理的一条巧妙捷径。确保一个 $k$-稀疏向量是 $y=Ax$ 的唯一最稀疏解的真实条件是一个组合性条件。它涉及到一个称为矩阵​​spark​​的属性，记作 $\mathrm{spark}(A)$。spark 是指 $A$ 中线性相关的列的最小数量。

为保证任意两个不同的 $k$-稀疏向量 $x_1$ 和 $x_2$ 產生不同的測量結果（即 $Ax_1 \neq Ax_2$），你需要确保它们的差 $x_1 - x_2$（最多是 $2k$-稀疏的）不在 $A$ 的零空间中。如果 $A$ 的任意 $2k$ 列都是线性无关的，这一点就能得到保证。换句话说，你需要 $\mathrm{spark}(A) > 2k$。

这是一个绝佳且直观的条件。问题在于，计算 spark 是一项极其艰巨的任务，形式上是 NP-hard 问题。它需要检查所有 $s=1, 2, \dots$ 的 $\binom{n}{s}$ 个列子集的线性相关性。对于任何有实际意义大小的矩阵来说，这在计算上都是不可行的。

这正是相干性之美闪耀之处。虽然计算 spark 很困难，但计算互相关性却很简单——它只涉及计算内积。而且关键的是，两者之间有直接的联系：

这个不等式为难以找到的 spark 提供了一个易于计算的下界。现在我们看到了恢复保证背后的逻辑。通过要求 $k < \frac{1}{2}\left(1 + \frac{1}{\mu(A)}\right)$，我们确保了 $2k < 1 + \frac{1}{\mu(A)}$。将其与 spark 不等式结合，我们得到 $2k < \mathrm{spark}(A)$。因此，这个易于检查的相干性条件作为一个实用的替代品，一个充分条件，服务于那个真实但难以处理的 spark 条件。

相干性是一个强大而直观的工具，但它有一个关键特征：它是一个​​最坏情况​​的度量。它基于字典中相关性最高的一对原子来评判整个字典。这有时可能过于悲观。

考虑一下我们在现代压缩感知中喜欢使用的大型​​随机矩阵​​。对于这些矩阵，可以证明其互相关性通常在 $\mu(A) \approx \sqrt{\frac{\log n}{m}}$ 的量级。将此代入我们可靠的恢复公式，表明我们只能恢复稀疏度上限为 $k \approx \sqrt{m/\log n}$ 的信号。这不错，但并不算好。可恢复元素的数量仅随测量次数 $m$ 的平方根增长。事实证明，这是一种悲观的看法。一种更复杂的分析方法，即​​限制等距性质（RIP）​​，它研究列组的集体行为，表明这些相同的随机矩阵实际上可以恢复稀疏度高达 $k \approx m/\log n$ 的信号,。这是一种近線性的關係，要好得多。对于随机矩阵，简单的成对相干性保证并不能反映全貌。

但相干性的观点总是悲观的吗？惊人的是，并非如此。存在一些高度结构化的确定性矩阵，对于这些矩阵，基于相干性的保证不僅好，而且是​​完全紧密的​​。一个很好的例子是​​正单纯形框架​​，它由 $\mathbb{R}^m$ 中的 $m+1$ 个向量组成，这些向量之间的距离尽可能远。对于这种构造，相干性为 $\mu(A) = 1/m$。我们的保证预测对于 $k < \frac{1}{2}(1+m)$ 的情况可以恢复。同时，已知该矩阵的 spark 恰好是 $\mathrm{spark}(A) = m+1$。基于 spark 的基本限制是 $2k < m+1$，即 $k < \frac{1}{2}(m+1)$。这两个条件是相同的！对于这个特殊的矩阵，简单易算的相干性揭示了该矩阵恢复能力的全部、未经修饰的真相。

这揭示了一个深刻的原理：保证的质量取决于它所描述的对象。对于随机、非结构化的系统，最坏情况下的成对分析通常过于保守。而对于高度结构化、对称的系统，同样的分析可能精确无比。我们还有​​Welch界​​，这是一个基本定理，指出对于任何 $m \times n$ 矩阵，其相干性永远不会小于 $\sqrt{\frac{n-m}{m(n-1)}}$。这为“差异性”设定了一个硬性下限，并告诉我们，从一个仅仅基于互相关性的保证中，我们所能期望的最好结果就是 $k \approx \sqrt{m}$ 的尺度关系。

对于随机矩阵而言，成对相干性是悲观的，这一事实表明，成对地看待原子过于简单化了。如果我们考察小组的集体行为会怎样？这引出了相干性的一个自然扩展。

与其问“任意两个原子间的最大相关性是多少？”，我们可以问“一个原子与另外 $s$ 个原子组成的集合之间的最大总相关性是多少？”。这就引出了​​累积相干性​​（也称为巴别函数），$\mu_1(s)$:

这个函数衡量了集合 $\Lambda$ 外部的一个原子 $a_j$ 可能从该集合内部 $s$ 个原子组成的群组接收到的最大“干扰”。这带来了一个更强的恢复条件。例如，对于正交匹配追踪（OMP），如果 $\mu_1(s-1) < 1$，则保证可以恢复一个 s-稀疏信号。

这种更精细的度量可以更清晰地描绘出矩阵的能力。考虑一个仅含有一对相关原子，而所有其他原子都正交的矩阵。成对相干性只看到那一个高相关性，并给出一个悲观的保证。然而，累积相干性看到的是，这种相关性是孤立的，且集体干扰很低。在一个具体例子中，一个相干性为 $\mu(A)=0.4$ 的矩阵，其可恢复稀疏度的保证可能从互相关性条件下的 $s=1$ 跃升到累积相干性条件下的 $s=4$。这告诉我们，通过对我们测量系统的几何结构提出更复杂的问题，我们可以得到更强大、更准确的答案，从而为更深入地理解使稀疏性发挥作用的美妙数学铺平道路。

在我们之前的讨论中，我们揭示了互相关性的原理。其核心是一个极其简单的思想：为了确保你能区分出信号中稀疏的关键成分，你用来测量它的构建模块——也就是传感矩阵 $A$ 的列向量——应该尽可能地彼此不同。相干性 $\mu(A)$ 就是衡量这些构建模块中任意两者之间最坏情况相似性的一个度量。小的 $\mu(A)$ 是一个好的传感矩阵的标志。

这似乎是一个纯粹抽象的条件，是理论家们的乐园。但一个强大科学思想的魔力不在于其抽象性，而在于其在现实世界中的“不合理的有效性”。相干性这个看似朴素的概念，结果却成了一把万能钥匙，为科学和工程领域中一系列惊人的应用开启了洞见之門。它指导我们建造更好的仪器，设计更高效的实验，并理解我们所能测量的基本极限。让我们踏上一段旅程，亲眼看看这个原理的实际应用。

想象一下，你正在制造一台“单像素相机”。它没有数百万个像素点，只有一个，但你可以将一系列图案投射到场景上，并记录下每个图案反射回来的总光量。你的目标是从这为数不多的几次测量中重建一幅精细的图像。这是一个经典的压缩感知问题。

你投射的图案构成了你的“传感基” $\mathbf{\Phi}$。一个流行且高效的选择是来自 Walsh-Hadamard 矩阵的一组黑白图案，这些图案彼此之间具有良好的正交性。到目前为止，一切顺利。

与此同时，你知道自然图像在小波基（如 Haar 基 $\mathbf{\Psi}$）中是“稀疏”或“可压缩”的。这意味着大多数图像可以仅由少数几个小波分量构建而成。这就是你的“稀疏基”。

单独来看，Hadamard 基和 Haar 基都非常出色；它们是标准正交系统，是行为良好构建模块的典范。当你用其中一个来感知在另一个基中稀疏的信号时，会发生什么呢？这就是相干性发挥作用的地方。关键量是传感系统和稀疏系统之间的互相关性 $\mu(\mathbf{\Phi}, \mathbf{\Psi})$。如果我们为我们的相机计算这个值，会得到一个惊人的结果：$\mu(\mathbf{\Phi}, \mathbf{\Psi}) = 1$！

相干性为 1 是最坏可能的值。这意味着在 $\mathbf{\Phi}$ 中至少有一个传感图案与 $\mathbf{\Psi}$ 中的一个小波完全相同。这对我们的相机意味着什么？这意味着存在一个简单的 1-稀疏信号——即单个小波——它看起来与我们的一个测量图案完全一样。如果为了节省时间，我们决定不使用那个特定的测量图案，我们的相机将对那个小波完全“失明”。所有的测量值都将为零，我们的重建算法將自信地報告一張空白圖像。场景中一个真实存在的特征变得完全不可见。这两个“好”的基共同作用造成了一场灾难性的失败，而这场失败被简单的相干性度量以完美的清晰度预测了出来。

单像素相机的例子说明了一个关键教训：选择正确的基至关重要。但在许多科学问题中，稀疏基是由自然赋予我们的。例如，一个物理场的行为在使用 Legendre 多项式表示时可能本质上是稀疏的。那么问题就变成了：如果信号的语言是固定的，我们如何才能最好地设计我们的测量过程来理解它？

假设你是一位研究一维场的物理学家，比如一根杆上的温度分布。你知道其内在物理规律决定了温度分布可以用少数几个 Legendre 多项式来描述。你只有有限数量的温度计，比如说 $m$ 个，但你需要估计 $N$ 个可能的多项式系数，其中 $m < N$。你应该把温度计放在哪里才能得到最好的重建结果？

这是一个在结构化的确定性矩阵上进行稀疏恢复的问题——这个矩阵是一个通过在你选择的测量点上计算 Legendre 多项式的值而形成的 Vandermonde 矩阵。你可以把温度计放在等间距的位置上。这看起来很公平，但这是一个糟糕的选择。对于高阶多项式，所得的传感矩阵的列向量变得几乎平行，导致互相关性接近于一。恢复注定会失败。

然而，如果你将传感器放置在一组特殊的点上，即所谓的 Chebyshev-Lobatto 节点，这些节点在杆的两端更密集地聚集，那么奇妙的事情就会发生。传感矩阵的相干性会急剧减小。为什么？因为 Legendre 多项式在这些特定点上采样时，其行为方式更加“正交”。相干性提供了定量的解释：这种聪明的采样策略最小化了传感矩阵列之间的最坏情况相似性，从而使得区分不同多项式的贡献并成功恢复稀疏系数成为可能，即使测量次数很少。

这个思想延伸到了更复杂的领域。在不确定性量化等领域，科学家使用“多项式混沌展开”来模拟复杂系统的行为，其中函数对随机参数的依赖性用 Hermite 多项式基来表示。为了表征该系统，他们必须通过在少数选定的参数设置下运行模拟来估计这个展开的系数。问题又来了：你选择哪些设置？

在这里，基于相干性的思维方式引出了统计学中的一个深刻概念：最优实验设计。事实证明，你不应该均匀地采样参数空间。相反，你应该在 Hermite 多项式基函数值 cenderung besar (tend to be large) 的区域进行更频繁的采样。这种非均匀采样策略（可以通过数学推导得出）的效果是使每个测量点大致具有同等的“影响力”，这一特性被一个称为杠杆分数（leverage scores）的概念所捕捉。通过使这些分数均匀化，你正在驯服测量系统的最坏情况行为，这反过来又以高概率最小化了有效传感矩阵的相干性。你不仅仅是在选择点；你正在设计一个完整的测量概率分布，以使其对于稀疏恢复达到最大效率。

在前面的例子中，稀疏基是固定的。但如果我们能设计稀疏性本身的“语言”呢？如果我们能构建一个由原子或“单词”组成的自定义字典 $\mathbf{D}$，使其完美地适应我们的信号呢？

理想与现实

首先，让我们问：一个“完美”的字典会是什么样子？从相干性的角度来看，它应该是一个原子之间尽可能接近正交的字典。对此存在一个基本限制，一个被称为 Welch 界的正交性“速度极限”。它为任何一个位于 $m$ 维空间中包含 $n$ 个原子的字典的相干性给出了一个最低下界。

令人惊奇的是，存在一些特殊的字典，称为等角紧框架（Equiangular Tight Frames, ETFs），它们能够达到这个界。在一个 ETF 中，任意两个不同原子之间内积的绝对值是相同的，并且是理论上可能的最小值。这些是具有极高数学美感的对象，位于几何学、组合数学和信号处理的交叉点。它们代表了稀疏表示字典的柏拉图式理想。不幸的是，像许多完美的事物一样，它们极为罕见，并且只存在于非常特定的维度中。

从经验中学习

如果我们不能总是找到一个“完美”的字典，也许我们可以从数据中学习一个非常好的字典。这是现代机器学习和信号处理的基石。考虑处理海底地震图像的任务。地质学家知道这些图像由平坦地层、断层和曲线等特征组成。一个通用的字典，比如余弦和曲波原子的组合，可以表示这些特征，但效率不高。描述一个单一的地质结构可能需要许多不同的原子，而这些原子之间可能高度相关——即字典具有高相干性。

相反，我们可以收集大量的真实地震数据块，并使用机器学习算法来学习一个字典，其原子是地震学语言中反复出现的“单词”。这个学习到的字典 $\mathbf{D}_{\mathrm{learned}}$ 是为数据中的特定结构量身定制的。它提供了更稀疏的表示，因为它的原子更能代表内容。这种效率有一个直接的几何后果：学习到的原子彼此之间的相关性更低。

在一个实际场景中，一个通用的固定字典 $\mathbf{D}_{\mathrm{fixed}}$ 可能具有非常高的相干性，比如 $\mu(\mathbf{D}_{\mathrm{fixed}}) \approx 0.9$，而一个学习得到的字典则可以达到 $\mu(\mathbf{D}_{\mathrm{learned}}) \approx 0.2$。当我们将它们与一个测量过程（如部分傅里叶采样 $\mathbf{\Phi}$）结合时，这种优势通常仍然存在。有效传感矩阵 $\mathbf{A}_{\mathrm{learned}} = \mathbf{\Phi D}_{\mathrm{learned}}$ 的相干性可能为 $\mu(\mathbf{A}_{\mathrm{learned}}) \approx 0.12$。对于恢复一个稀疏度为 $s=4$ 的信号，一个标准的保证要求 $\mu(\mathbf{A}) < \frac{1}{2s-1} \approx 0.143$。学习得到的字典满足这个条件；而固定字典的有效相干性 $\mu(\mathbf{A}_{\mathrm{fixed}})$ 约为 0.65，则不满足。通过为数据学习正确的语言，我们设计了一个系统，使得稀疏恢复现在能够保证成功。

这凸显了一个关键点：字典 $\mathbf{D}$ 的性质只有在不被测量算子 $\mathbf{\Phi}$ 破坏的情况下才有用。最终有效矩阵 $\mathbf{A} = \mathbf{\Phi D}$ 的相干性才是真正决定恢复效果的关键。幸运的是，对于许多常见的测量方案，如随机傅里叶采样，一个好的字典通常会导出一个好的有效矩阵。

矩阵的减材制造

有一种更直接的方法来工程化相干性：如果字典中的某些原子引起了问题，就直接去掉它们！想象一下，你有一个字典，其中有少数几个原子与许多其他原子令人讨厌地相似。你可以识别出“罪魁祸首”——即与所有其他原子平均相关性最高的那个原子——然后简单地将其从字典中移除。通过重复这个“剪枝”过程，你可以系统地降低字典的整体相干性，从而提高其在稀疏恢复任务中的性能。这种贪婪的、减法式的方法是相干性驱动设计的一个简单而有力的例证。

相干性的力量超越了单个矩阵，可以用来描述整个系统的行为，并应对高度非线性测量的挑战。

数量就是力量？视情况而定。

想象一下，你有一个由 $L$ 个传感器组成的网络，它们都在尝试测量同一个稀疏信号。直观上，更多的传感器应该意味着更好的测量。相干性使我们能够精确化这种直觉，并揭示了一个令人惊讶的转折。我们可以将所有 $L$ 个传感器的测量数据捆绑成一个巨大的传感矩阵。这个聚合矩阵的相干性将决定整个系统的性能。

如果不同传感器的随机测量矩阵彼此相关，会发生什么？如果相关性是正的——例如，如果传感器物理上很近，并且受到相似的环境噪声影响——那么增加更多传感器的好处就会减少。有效的独立传感器数量减少了。在极端情况下，如果所有 $L$ 个传感器都完全相关（即它们都在进行完全相同的测量），那么拥有 $L$ 个传感器并不比只有一个更好。

但如果传感器矩阵是负相关的呢？那么就会发生一些非凡的事情。一个传感器的测量变化会主动抵消另一个传感器的变化。这会产生一个比传感器完全独立时相干性更低的聚合矩阵。负相关实际上是有益的！相干性提供了一个框架来理解和量化这种系统级效应，表明分布式网络的质量不仅取决于节点的数量，还取决于它们之间的统计关系。

在黑白世界中观察

当我们的测量极其粗糙时会发生什么？考虑 1-bit 压缩感知，我们只记录每次测量的符号（$+1$ 或 $-1$），丢弃了所有的幅度信息。这是一个严苛的非线性过程。相干性，一个源于线性代数的概念，在这里还能有什么用武之地吗？

答案是肯定的，但方式却异常巧妙。符号函数本身很难处理。但是，如果我们在测量值被量化为 1-bit 之前，有意地添加少量随机噪声——一种称为“抖动（dithering）”的技术——情况就变了。这个看似违反直觉的加噪步骤实际上是有帮助的。它将符号函数的突变平滑成一条连续的曲线。

这种平滑是关键。它意味着我们 1-bit 测量的*期望值*现在在局部上表现得像线性测量。抖动不会改变底层矩阵 $A$ 的相干性，这是一个固定的几何属性。相反，它将非线性测量问题转化为一个近似線性的問題，从而使得基於相干性的强大分析工具能够重新发挥作用。它提高了恢复的鲁棒性，不是通过改变矩阵的几何结构，而是通过使测量过程本身变得更良态和可分析。

我们的旅程到此结束。我们从一个简单的几何概念开始——一个向量集合中向量之间的最大夹角。我们已经看到，这一个单一的思想提供了一个强大的透镜，通过它可以观察广阔的科学问题领域。它解释了一台简单相机中的灾难性故障，指导了研究物理场的传感器的优化布局，为从数据中学习更好的表示提供了标准，并量化了分布式系统的集体行为。它甚至为我们理解棘手的非线性测量世界提供了一个立足点。

这是一个深刻物理原理的特征。它提供了一条统一的线索，连接了看似无关的现象，并揭示了一个支撑着复杂性的简单而优雅的结构。相干性的故事是一个美丽的证明，证明了何学和抽象概念在启发和塑造我们对所测世界的理解方面所具有的力量。