Prony 有限幂和重构 | Codeboy's Blog

给出一串数，问它能不能写成几个几何数列的叠加，比“已知递推式求下一项”多了一层困难：连递推式也不知道。Prony方法把这层未知拆开。先解一个线性系统找出会消掉所有分量的多项式，再求它的根，最后才计算每个分量的权重。每一步都有可复核的等式，但这些等式的效力取决于输入究竟是精确模型还是带误差的观测。

形式陈述

输入是连续的一段，不是任意挑选的若干时刻

固定整数 $r\ge1$ 。考虑序列

y_k=\sum_{\ell=1}^r w_\ell z_\ell^k,\qquad k=0,1,2,\ldots, \tag{1}

其中节点 $z_\ell$ 是两两不同的复数，振幅 $w_\ell\ne0$ 。允许 $z_\ell=0$ ，约定其零次幂为一；这一分量只在 $k=0$ 留下一个值。若要把每个节点解释为连续指数 $e^{\alpha_\ell h}$ ，则节点必须非零。

已知准确的 $y_0,\ldots,y_{2r-1}$ 和阶数 $r$ ，定义

H=(y_{i+j})_{i,j=0}^{r-1},\qquad h=(y_r,\ldots,y_{2r-1})^{\mathsf T}. \tag{2}

$H$ 的反对角线上数值相同，这种矩阵称为Hankel矩阵。解 $Hc=h$ ，并令

q(t)=t^r-\sum_{j=0}^{r-1}c_jt^j. \tag{3}

在上述模型条件下， $H$ 可逆， $q$ 的根恰为 $z_1,\ldots,z_r$ ，且全部简单。恢复根以后，再解

\sum_{\ell=1}^r w_\ell z_\ell^k=y_k, \qquad k=0,\ldots,r-1. \tag{4}

这两次线性求解连同多项式求根，给出唯一的 $r$ 节点表示，唯一性只差节点的排列。它没有预先给出根的数值算法或误差证书；有理系数需要严格实根时，可以接已有的实根隔离。

从任意数据出发时，要保留验收分支

如果一段数据并未附带模型保证，方法应报告检查结果： $H$ 不可逆时，当前阶数的这套非退化步骤不能继续； $H$ 可逆但 $q$ 有重根时，普通“不同节点幂和”模型被拒绝；若根确实不同，则式(4)恢复的权重均非零，并且重构恰好匹配这 $2r$ 个值。最后这一结论仍只是一份有限段表示，没有证明尚未观察的尾部继续遵守它。

若另有观测 $y_{2r},\ldots,y_N$ ，应逐项核对递推或直接重构。一次失败就足以拒绝该精确模型；全部有限检查通过，也不能排除下一项出现偏离。若只知道节点数至多 $r$ ，还需允许真实阶数更低，并相应改变所解系统，而不是把奇异矩阵强行求逆。

直觉

先找到“同时让所有节点归零”的多项式

设 $V_{i\ell}=z_\ell^i$ ， $0\le i<r$ 。由式(1)逐项展开，

H=V\operatorname{diag}(w_1,\ldots,w_r)V^{\mathsf T}. \tag{5}

这里是普通转置，不是共轭转置，因为数据是 $z^{i+j}$ ，并不是 $\overline{z}^{i}z^j$ 。因此复Hankel矩阵不自动半正定；有符号实振幅也没有正定保证。

Vandermonde行列式给

\det H=\left(\prod_\ell w_\ell\right) \prod_{a<b}(z_b-z_a)^2\ne0. \tag{6}

令真正的节点多项式为 $\prod_\ell(t-z_\ell)$ 。把它写成式(3)，对每个节点都有 $z_\ell^r=\sum_jc_jz_\ell^j$ ，乘 $w_\ell z_\ell^k$ 后相加，得到

y_{k+r}=\sum_{j=0}^{r-1}c_jy_{k+j}\qquad(k\ge0). \tag{7}

取 $k=0,\ldots,r-1$ ，正好就是 $Hc=h$ 。可逆性说明该系统算出的 $q$ 必然是真正节点多项式；第二次Vandermonde求解再唯一确定振幅。

这解释了为什么用 $2r$ 个连续值：前 $r$ 个提供初始条件，后 $r$ 个提供确定递推系数的线性方程。不是把每个未知根直接塞进一个非线性最小化问题。

反向检查和最小阶也能完整证明

对任意输入段，假设 $H$ 可逆、算出的 $q$ 有 $r$ 个不同根。先由前 $r$ 个值求权重，令 $\widetilde y$ 为这些节点产生的幂和。它满足式(7)，而原数据由 $Hc=h$ 也满足式(7)的前 $r$ 次。因此从同样的初值逐项推进，得到 $\widetilde y_k=y_k$ ， $0\le k<2r$ 。若某个权重为零，式(5)的秩就小于 $r$ ，与 $H$ 可逆矛盾。

在完整模型内，阶数还不能再降低。若一个非零多项式 $a$ 给出恒成立的消去关系，则

\sum_{\ell=1}^r w_\ell a(z_\ell)z_\ell^k=0 \qquad(k\ge0).

只取最初 $r$ 个 $k$ ，Vandermonde可逆便迫使每个 $a(z_\ell)=0$ 。 $r$ 个不同根要求 $\deg a\ge r$ 。这就是从 $k=0$ 起对全部移位成立的最小湮灭多项式次数，也把逆向重构接回旧页的常系数线性递推。

允许零节点时，最早一项仍参与这些等式，上述最小次数结论仍正确；若只要求某个尾部满足递推，零节点消失后次数可以降低。递推的常数系数可能为零，无法从未来唯一倒推过去。若丢掉 $k=0$ 开始从 $k=1$ 采样，这个零节点分量便完全不可见。

例子与边界

质量、递推和节点都能精确列出

给出六个值

(y_0,\ldots,y_5)=(1,1/2,3/2,5/2,11/2,21/2).

取 $r=3$ ，得到

H=\begin{pmatrix}1&1/2&3/2\\1/2&3/2&5/2\\3/2&5/2&11/2\end{pmatrix}, \qquad h=(5/2,11/2,21/2)^{\mathsf T}.

其行列式为一，解为 $c=(0,2,1)^{\mathsf T}$ ，因此

q(t)=t^3-t^2-2t=t(t+1)(t-2).

三个节点为 $-1,0,2$ ，解式(4)得权重 $1/6,1/2,1/3$ 。逐项重构六个值，并预测 $y_6=2y_4+y_5=43/2$ 。这只是模型的预测；在正测度问题中，真正多给这一项且验证相等，才会形成平坦矩唯一性证书。

前六个值已经足够唯一识别“三个不同节点的幂和”。它们却没有声明别的、更多节点甚至连续分布不能分享这些有限矩；必须区分已知模型中的唯一性与所有正测度中的唯一性。

有符号抵消不是零信号

取 $y_k=1^k-2^k$ ，前四项为 $0,-1,-3,-7$ 。此时

H=\begin{pmatrix}0&-1\\-1&-3\end{pmatrix},\quad \det H=-1,\quad q(t)=t^2-3t+2.

方法恢复节点 $1,2$ 和权重 $1,-1$ ，完全正常。总和 $y_0=0$ 不意味着整个序列为零。它却不能是非零正测度的矩表，因为正测度的总质量为零会使所有矩都为零；把一般Prony系统误当作正定矩系统，会在这里丢掉合法输入。

重根要求扩大模型，而不是重复写同一个节点

序列 $y_k=(k+1)2^k$ 的前四项为 $1,4,12,32$ 。二阶系统可逆，但算出

q(t)=t^2-4t+4=(t-2)^2.

它不可能是两个不同节点、非零振幅的普通幂和。把“节点2”写两次也无济于事，两项 $w_12^k+w_22^k$ 会合并成一个几何分量。真正需要的是含 $k^jz^k$ 的合流模型，与旧递推页的重根项相应；本页不把合流求解伪装成原算法的成功。

从离散节点回到连续指数，还剩混叠

若 $y_k=\sum w_\ell e^{\alpha_\ell kh}$ 、 $h>0$ ，Prony只能恢复 $z_\ell=e^{\alpha_\ell h}$ 。对任意整数 $n$ ， $\alpha_\ell+2\pi in/h$ 给同一个节点。两个连续指数还可能采样成相同节点，使阶数下降；若对应振幅抵消，该分量甚至消失。没有带宽或虚部区间等额外约束，不能把选一个复对数分支说成唯一恢复连续频率。

推论与应用

近碰撞把准确可逆变成数值困难

取正权重各 $1/2$ 、节点 $1-\delta,1+\delta$ 。前四项为

1,\quad1,\quad1+\delta^2,\quad1+3\delta^2,

而二阶Hankel行列式是 $\delta^2$ 。每个非零 $\delta$ 都有两个不同节点和准确的二阶模型；令 $\delta$ 很小，四个值却接近单节点序列 $1,1,1,1$ 。固定小数精度无法把“准确秩一”和“十分接近秩一”自动分开。

若 $\widehat H=H+E$ 、 $\widehat h=h+e$ ，并且 $\|H^{-1}E\|<1$ ，线性系统扰动界实际给出

\|\widehat c-c\| \le\frac{\|H^{-1}\|}{1-\|H^{-1}E\|} \bigl(\|e\|+\|E\|\,\|c\|\bigr). \tag{8}

这还只控制递推系数；从系数到根又有另一层条件性。SVD截断、扩大采样窗口和最小二乘可以是有用的近似方法，但阈值必须来自噪声与模型合同，不能只因软件输出三个奇异值就宣称有三个真实分量。式(8)的前提和根分离条件也不能略掉。

复核证书的顺序

一份精确交付应包含：阶数与连续样本区间、Hankel系统、非零行列式或等效可逆性证据、首一多项式、全部不同根及完整性依据、Vandermonde权重、所有已给样本的匹配。若有新数据，则继续列出每个递推残差。多项式根的十位小数并不是“全部不同根”的证明。

在正实矩问题中，下一页会补上正性和最后一项平方范数，从而把有限模型识别升级为对全部正测度的判断。对于一般复振幅，本页没有这种升级：有限样本之外的行为仍须由原始模型负责。

参考资料

Daniel Potts、Manfred Tasche，Parameter estimation for exponential sums by approximate Prony method，作者2009年稿，§2的Hankel核、经典Prony步骤与伴随矩阵；发表于 Signal Processing 90 (2010), 1631–1642。本文证明的是精确、已知阶数版本，不采用该文近似算法的数值结论。

形式陈述 ​

输入是连续的一段，不是任意挑选的若干时刻 ​

从任意数据出发时，要保留验收分支 ​

先找到“同时让所有节点归零”的多项式 ​

反向检查和最小阶也能完整证明 ​

质量、递推和节点都能精确列出 ​

有符号抵消不是零信号 ​

重根要求扩大模型，而不是重复写同一个节点 ​

从离散节点回到连续指数，还剩混叠 ​

近碰撞把准确可逆变成数值困难 ​

复核证书的顺序 ​

反向链接