傅里叶子空间、托普利茨矩阵和指数和的最优结构化逼近

《Linear Algebra and its Applications》：Optimal Structured Approximation of Fourier Subspaces, Toeplitz Matrices, and Exponential Sums

　　

# 摘要

本文研究三个结构化逼近问题：(1) 从单次观测中恢复傅里叶矩阵的值域；(2) 恢复被破坏的低秩Toeplitz/Hankel矩阵；(3) 从含噪样本中恢复有限指数和。这三个问题在计算上都具有挑战性，因为其结构性约束难以直接施加。我们证明，通过应用用于频谱估计的Gradient-MUSIC算法，所有三个任务都可以高效且最优地求解。以秩为 $r$ 的Toeplitz矩阵 $T \in \mathbb{C}^{n \times n}$ 为例，该矩阵满足正则性假设，并受到任意扰动 $E \in \mathbb{C}^{n \times n}$（满足 $\|E\|_2 \leq \alpha \cdot n$），我们的算法输出一个秩恰好为 $r$ 的Toeplitz矩阵 $T^\sharp$，使得 $\|T - T^\sharp\|_2 \leq C \cdot \|E\|_2$，其中 $C, \alpha > 0$ 为绝对常数。这一性能保证在 $n$、$r$ 和 $\|E\|_2$ 方面是最小最大最优的。对于另外两个结构化逼近问题，我们也提供了在样本数量、秩/稀疏度和噪声水平方面均达到最小最大最优的算法。本文的核心是一个定量转导原理，展示了如何将频谱估计的计算方法和理论转化为上述三个问题的对应方法和理论。

# 引言

采样与逼近理论研究如何从有限数量的信息（如测量值、样本）重建一个对象（如函数、矩阵等）。一个基本例子是指数和 $f : \mathbb{R} \to \mathbb{C}$，$f(t) = \sum_{k=1}^{r} a_k e^{itx_k}$，$t \in \mathbb{R}$，其中每个频率 $x_k \in \mathbb{T} := \mathbb{R}/2\pi\mathbb{Z}$ 位于连续统上，每个振幅 $a_k \in \mathbb{C}$ 非零。若 $f$ 在整数时刻 $t = 0, \ldots, n-1$ 处采样，并受到加性噪声 $z \in \mathbb{C}^n$ 的扰动，则模型变为 $\tilde{y} := y + z$，$y := \Phi(x)a$，$\Phi(x) := \Phi_n(x) = [e^{ijx_k}]_{j=0,\ldots,n-1;\, k=1,\ldots,r}$。通过缩放论证，不失一般性地，我们假设对所有 $j$ 有 $|a_j| \geq 1$。

频谱估计问题是从样本 $\tilde{y}$ 中恢复频率 $x$。与傅里叶级数的设定不同，未知函数并非在固定频率网格上带限，频谱节点本身也是离散的，必须从数据中推断，这使得 $x$ 的逼近本质上是一个非线性反问题。最小间隔 $\Delta(x) = \min_{j \neq k} |x_j - x_k|_{\mathbb{T}}$ 控制着该反问题的稳定性。大致而言，我们说 $x$ 是良好分离的，如果对于足够大的 $\beta \geq 1$，有 $\Delta(x) \geq 2\pi\beta/n$。在这种情况下，傅里叶矩阵 $\Phi_n(x)$ 的条件数具有均匀界[2]，并且可以通过Gradient-MUSIC算法[15]实现 $x$ 的最小最大最优估计。

在本文中，我们以频谱估计为核心问题，以Gradient-MUSIC为选择的算法，来展示如何以最小最大最优的方式求解以下三个结构化逼近问题。在此我们指出，本文的组织方式使得读者可以独立地理解以下三个问题中的任何一个。

**1.** 傅里叶子空间是形如 $U(x) := \text{range}(\Phi_n(x)) \subseteq \mathbb{C}^n$ 的子空间。给定测量 $\tilde{y}$，傅里叶子空间估计要求找到一个维数为 $r$ 的傅里叶子空间 $\tilde{U} \subseteq \mathbb{C}^n$，以逼近 $U$（相对于谱范数或Frobenius距离）。该问题之所以非平凡，仅因为 $\tilde{U}$ 必须是傅里叶子空间的结构性要求。

许多数据分析和信号处理中的过程主要依赖于主导子空间而非完整矩阵。例如，在阵列信号处理的经典子空间方法[22]、主成分分析以及数据科学中的许多谱方法[9]中均如此。

**2.** 考虑一个秩为 $r$ 的Toeplitz矩阵，满足分解 $T = \Phi_n(x)\,\text{diag}(a)\,\Phi_n(x)^* \in \mathbb{C}^{n \times n}$。若 $E$ 是任意扰动，给定 $M := T + E \in \mathbb{C}^{n \times n}$，低秩Toeplitz矩阵逼近问题是找到一个秩为 $r$ 的Toeplitz矩阵 $\tilde{T}$，以逼近 $T$（相对于谱范数或Frobenius范数）。该问题之所以非平凡，仅因为要求 $\tilde{T}$ 也是Toeplitz的。同样的问题也可以针对Hankel矩阵 $H$ 而非Toeplitz $T$ 提出，且它们是完全等价的问题。

> Toeplitz和Hankel矩阵都编码了平移不变的采样关系，在去卷积、系统辨识、阵列处理、逆散射、谱压缩感知以及相关成像问题中具有基础性地位，参见[8], [20], [24], [26], [30], [31], [43], [44], [45]。这些工作中利用的一个底层原理是Toeplitz和Hankel矩阵通常近似低秩且具有额外的代数结构。尽管这一计算逼近问题引起了广泛关注，参见[11], [12], [16], [29], [36]，但我们并未了解到该问题的最优算法。

**3.** 给定测量 $\tilde{y}$，从含噪数据逼近指数和问题是找到一个恰好有 $r$ 项的指数和 $\tilde{f}$，以逼近 $f$（在 $L^2([0,n])$ 或 $\ell^2(\{0,1,\ldots,n-1\})$ 范数下）。该问题之所以非平凡，是因为第一个要求 $\tilde{f}$ 是一个指数和，而指数和并非函数空间的线性子空间。

对该问题的兴趣可由经典的Whittaker–Nyquist–Shannon采样定理激发，该定理涉及在整数上采样的带限函数。然而，在许多现代反问题中，未知对象不仅带限，还由少量频谱参数描述。

三个问题与频谱估计之间的关系可由图1总结。此处外层三角形代表本文解决的另外三个结构化逼近问题。采样/插值是源头：指数和的有限样本编码了连续参数。结构化低秩矩阵逼近通过将样本排列为Toeplitz或Hankel矩阵而产生。傅里叶子空间估计通过提取Vandermonde列空间而产生。频谱估计位于中心，因为在良好分离的区间内，它将近似子空间信息转化为精确的频率信息，然后可用于求解另外两个结构化逼近问题。

---

一般情况下，向量和矩阵用粗体表示。我们使用下标表示向量或矩阵的条目，例如 $a_j$ 和 $A_{j,k}$ 分别表示向量 $a$ 的第 $j$ 个条目和矩阵 $A$ 的 $(j,k)$ 个条目。

对于 $v \in \mathbb{C}^n$，令 $\text{diag}(v)$ 为以 $v$ 为对角元素的 $n \times n$ 对角矩阵，顺序与 $v$ 一致。对于 $\mathbb{C}^n$ 中同维子空间 $U$ 和 $V$，令 $\sin(U,V)$ 为包含其主角度正弦值的对角矩阵。

对于矩阵 $A$，$\|A\|_2$ 和 $\|A\|_F$ 分别表示其谱范数和Frobenius范数。$A$ 的Moore-Penrose伪逆记为 $A^\dagger$，共轭转切记为 $A^*$。我们使用简写 $A^{\dagger,*} := (A^\dagger)^*$。对于向量 $u$，$\|u\|_p$ 表示其 $p$-范数，其中 $p \in [1,\infty]$。若存在普适常数 $C > 0$ 使得 $a \leq Cb$，则写 $a \lesssim b$。

若 $z = x + iy$，其中 $x, y$ 是独立的、均值为零、方差为 $\sigma^2/2$ 的正态随机变量，则称 $z$ 是均值为零、方差为 $\sigma^2$ 的复正态随机变量。

---

# 主要结果与贡献

本文的主要贡献是基于Gradient-MUSIC频谱估计的定量转导原理，如图2所示，该原理与其他三个问题具有定量关联。

**（上界转导机制）** 我们展示了如何对Gradient-MUSIC算法和理论进行简便修改，以产生其他三个结构化逼近问题的方法和性能保证。示意性表述为：

$$\text{经验噪声} \longrightarrow \text{子空间误差} \longrightarrow \text{频谱误差} \longrightarrow \text{傅里叶矩阵和子空间}$$

全文中 $n$ 为固定整数。尽管各种定义将隐式依赖于 $n$，我们将抑制其对 $n$ 的依赖以减少冗余。

$x$ 的最小间隔控制了频谱估计对噪声的稳定性。事实上，[2, Theorem 1]表明，对于任何 $\beta > 1$：

$$\Delta(x) \geq 2\pi\beta/n \implies \sqrt{n}(1-\beta^{-1}) \leq \sigma_{\min}(\Phi_n(x)) \leq \sigma_{\max}(\Phi_n(x)) \leq \sqrt{n}(1+\beta^{-1})$$

注意，分离条件 $\Delta(x) \geq 2\pi\beta/n$ 隐式地意味着 $n \geq \beta r$，其中 $r$ 表示 $x$ 的基数。通过略加强假设……

---

# 问题形式化

## 傅里叶子空间估计

我们以谨慎的方式建立傅里叶子空间估计问题。假设我们观测到形如 $y + z \in \mathbb{C}^n$ 的向量，其中噪声 $z$ 足够小，且对于某个 $(x, a)$，$y = \Phi_n(x)a$。因此，$y$ 位于傅里叶子空间 $U(x) := \text{range}(\Phi_n(x))$ 中。我们能否找到一个同维的傅里叶子空间 $\tilde{U} \subseteq \mathbb{C}^n$，以高精度逼近底层的 $U$？这里逼近使用以下任一度量：

$$\|\sin(U,\tilde{U})\|_2 \quad \text{或} \quad \|\sin(U,\tilde{U})\|_F$$

乍看之下，这个问题似乎是不可能的。即使没有……

## 低秩Toeplitz/Hankel矩阵逼近

我们首先讨论该问题并以谨慎的方式加以设定。假设我们观测到一个矩阵 $M = T + E \in \mathbb{C}^{n \times n}$。这里，我们假设 $T$ 是秩为 $r < n$ 的Toeplitz矩阵，$E$ 是任意矩阵。正确的秩 $r$ 是未知的。我们对 $E$ 不作任何结构性假设（例如，我们不断言它是Toeplitz的），且 $M$ 不一定也是Toeplitz的。

从 $M$ 中恢复 $T$ 的一般性困难在[11], [12], [38]中有讨论。为了更深入地研究该问题，我们需要对 $T$ 做出一些假设。该……

## 指数和逼近

考虑以下具有 $r$ 个非零项的指数和集合：

$$\mathcal{E}(h,r) := \left\{f : \mathbb{R} \to \mathbb{C} : f(t) = \sum_{k=1}^{r} a_k e^{ix_k t},\; (x,a) \in \mathcal{P}(h,r)\right\}$$

其中 $x$ 表示频率，$a$ 表示振幅。$h > 0$ 下界频率之间的间距，$r$ 是 $f$ 中指数项的数量。所有定义在 $\mathbb{R}$ 上的指数和的集合为 $\bigcup_{h>0}\bigcup_{r \geq 1} \mathcal{E}(h,r)$。

对于给定整数 $n \geq 1$，结构化逼近问题是关于误差 $\|\tilde{f} - f\|_{L^2([0,n])}$ 用另一个指数和 $\tilde{f}$ 逼近 $f \in \mathcal{E}(h,r)$。

---

# 数值模拟

我们将Gradient-MUSIC Toeplitz估计器与交替投影法进行比较，后者是矩阵问题的标准计算方法。关于Gradient-MUSIC的更多细节参见[15]，关于交替投影法的工作原理参见[11]。Gradient-MUSIC Toeplitz估计器的实现及复现本文结果的代码可在WL的Github仓库中找到。

> 为设置此实验，对于给定矩阵大小 $n$ 和秩……

---

# 展望与讨论

本文将四个主题联系起来：频谱估计、傅里叶子空间估计、结构化低秩Toeplitz/Hankel逼近以及指数和逼近。共同的代数对象是傅里叶/Vandermonde矩阵 $\Phi_n(x) = [e^{ijx_k}]$，共同的分析问题是在有限采样下该矩阵的稳定性。在良好分离的区间内，即 $\Delta(x) \gtrsim n^{-1}$ 时，这种稳定性使得定量地在线性样本、子空间、结构化矩阵和频率之间进行转换成为可能。

---

# 致谢

两位作者感谢Wenjing Liao富有洞察力和价值的讨论。我们感谢匿名审稿人的意见和建议，这些意见大大改进了本文的范围和呈现方式。我们特别感谢一位审稿人慷慨地提供了引理B.1的证明建议，这促使本文第一版中定理4.3和定理5.2得到了改进。WL的部分工作由NSF-DMS资助#2309602及PSC-CUNY第56周期资助提供。

Albert Fannjiang | Weilin Li