If $p$ is a polynomial in $t$ of degree $n$, say $$ p(t) = a_nt^n + \cdots + a_1t + a_0, $$ then if we choose $n+1$ distinct points $t_0, \dots, t_n$, the $a_k$s are completely determined by the values of $p(t_0), \dots, p(t_n)$.

If we define $$ c(t) = a_0e^{i\omega_0t} + \cdots + a_ne^{i\omega_nt}, $$ can we determine the $a_k$s and $\omega_k$s by looking at the values of $c$ on finitely many choices of $t$?


$c(t) = \sum_{m=1}^n a_m e^{i w_m t}$ the $w_m$ are distinct and the $a_m$ are non-zero.

The shifts of the functions $e^{i w_m t}$ generate a vector space of dimension $n$, the same as the vector space generated by the shifts of $c(t)$.

Pick some $t_1,\ldots,t_n$ such that the $c(t+t_j)$ are linearly independent, we get some $B_{m,j}$ such that $$\forall m, \forall t, \qquad e^{i \omega_m t} = \sum_{j=1}^n B_{m,j} c(t+t_j)$$

from there we have the linear maps $$\pmatrix{c(t+T+t_1)\\ \vdots \\ c(t+T+t_n)} = B^{-1} e^{i \text{ diag}(w) T} B \pmatrix{c(t+t_1)\\ \vdots \\ c(t+t_n)}$$

Your question reduces to sample finitely many values of $c$ to recover $ B^{-1} e^{i \text{ diag}(w)} B$ and $ B^{-1} e^{i \text{diag}(w) T} B$ with say $T=\pi$, diagonalize those matrices to recover $i w \bmod 2i \pi$ and $i w T\bmod 2i \pi$ from which we know $w$ and hence $a$.

For the concrete implementation see the MUSIC algorithm.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.