How to obtain the coefficients of a trigonometric polynomial by evaluating at well-chosen points?

Question

Suppose that we are given the trigonometric polynomial $$ P_M(t)=a_0 +\sum_{m=1}^M a_m \cos(mt)+b_m\sin(mt),\quad t\in[-\pi, \pi]. $$

Question. How to find nodes $t_1, t_2\ldots t_K\in [-\pi, \pi]$ and coefficients $\theta_1, \theta_2\ldots \theta_K$ such that $$a_0=\sum_{k=1}^K \theta_k P(t_k)\quad ?$$ Of course, the less nodes the better.

It would probably help to notice that $$a_0=\frac{1}{2\pi}\int_{-\pi}^\pi P_M(t)\, dt.$$ This suggests to apply a quadrature method to approximate the integral, and if the order of the method is high enough, the approximation will be exact. (Unfortunately I am not familiar with these things).

Bonus question. Suppose that all sine coefficients and all odd cosine coefficients vanish; that is $$P_M(t)=a_0+\sum_{j=1}^J a_{2j}\cos(2jt).$$ Can one exploit this structure to reduce the number of nodes?

Answer 1

Perhaps the complex form is easier to work with. In that case, \begin{eqnarray*} p\left(t\right) & = & \sum_{k=-M}^{M}\hat{p}\left(k\right)e^{ikt} \end{eqnarray*} where $\hat{p}(k)$ is the Fourier coefficients. Then \begin{eqnarray*} \hat{p}\left(k\right) & = & \frac{1}{2M+1}\sum_{n=-M}^{M}p\left(nh\right)e^{-inh},\quad h=\frac{2\pi}{2M+1}\\ & = & \frac{1}{2M+1}\left[p\left(0\right)+\sum_{n=1}^{M}2p\left(nh\right)\cos\left(nh\right)\right]. \end{eqnarray*}

So this holds when p is even. Otherwise replace p by its even/odd parts.

Thanks Giuseppe, that's a very nice interpretation. Just a quick comment to your last point. Assume $f$ is $2\pi$-periodic, so $f\in L^{2}\left(\mathbb{T}\right)$, and it has Fourier series expansion \begin{align*} f\left(x\right) & =\sum_{n\in\mathbb{Z}}\hat{f}\left(k\right)e^{ikx},\quad\hat{f}\left(k\right):=\frac{1}{2\pi}\int_{\mathbb{T}}f\left(x\right)e^{-ikx}dx. \end{align*} By sampling $f$ at $h\mathbb{Z}_{N}$, $h:=2\pi/N$, there is an $N$-periodic extension in $\hat{f}$ as follows: \begin{align*} f\left(n\frac{2\pi}{N}\right) & =\sum_{n\in\mathbb{Z}}\hat{f}\left(k\right)e^{i\frac{2\pi}{N}kn}\\ & =\sum_{n\in\mathbb{Z}_{N}}\left(\sum_{m\in\mathbb{Z}}\hat{f}\left(k+mN\right)\right)e^{i\frac{2\pi}{N}kn}. \end{align*} This is because $k\longmapsto e^{i\frac{2\pi}{N}kn}$ is $N$-periodic. Then, in terms of discrete Fourier transform, this means \begin{equation} \sum_{m\in\mathbb{Z}}\hat{f}\left(k+mN\right)=\frac{1}{N}\sum_{n\in\mathbb{Z}_{N}}f\left(n\frac{2\pi}{N}\right)e^{-i\frac{2\pi}{N}kn}.\tag{1} \end{equation} But if $\hat{f}$ is band-limited, say $f=p$ from above, then $\hat{f}\left(k\right)=0$ for all $k\notin\left\{ -M,\cdots,M\right\} $. In this case, as long as $N\geq2M+1$, the l.h.s. of (1) coincides with $\hat{f}$, so that \begin{align*} \hat{f}\left(k\right) & =\frac{1}{N}\sum_{n\in\mathbb{Z}_{N}}f\left(n\frac{2\pi}{N}\right)e^{-i\frac{2\pi}{N}kn}. \end{align*} That is, with $f=p$, $N=2M+1$, the last equation gives \begin{align*} \hat{p}\left(k\right) & =\frac{1}{2M+1}\sum_{n\in\mathbb{Z}_{2M+1}}p\left(n\frac{2\pi}{N}\right)e^{-i\frac{2\pi}{N}kn}\\ & =\frac{1}{2M+1}\sum_{n=-M}^{M}p\left(n\frac{2\pi}{N}\right)e^{-i\frac{2\pi}{N}kn}. \end{align*} $N=2M+1$ is the minimum sampling period; otherwise the l.h.s. of (1) would have overlaps, or aliasing.

Answer 2

I would like to add a couple remarks to the good answer provided by James and to the comment of LutzL. First remark is that this falls under the problem of the trigonometric interpolation; we are requiring to find an interpolating trigonometric polynomial that equals the given one.

The solution given by James can be interpreted in terms of the discrete Fourier transform (for which I just discovered an excellent introduction at the end of the first volume of Princeton's lectures in analysis).

Preliminaries. We consider the additive group $\mathbb Z /N\mathbb Z$, in which integers are identified if they are equal modulo $N$; that is, $k= h \mod N\iff k=h+nN$ for some $n\in\mathbb Z$. We write $L^2(\mathbb Z/N\mathbb Z)$ for the space of complex valued functions on $\mathbb Z/N\mathbb Z)$, to remark that we have a scalar product given by $$(F, G)=\frac{1}{N}\sum_{k\in \mathbb Z/N\mathbb Z} F(k)\overline{G(k)}.$$ The system of functions $$ e_n(k):=\exp\, \left(i\frac{2\pi}{N}nk\right),$$ where $n\in\mathbb Z/N\mathbb Z$, is orthonormal on $L^2(\mathbb Z/N\mathbb Z)$, so every function $F\in L^2(\mathbb Z/N\mathbb Z)$ decomposes as follows: $$ F(n)=\sum_{k\in \mathbb Z/N\mathbb Z} \hat{F}(k)e_k(n), $$ where $\hat{F}(k)=(F, e_n)$. This is the Fourier inversion formula.

The relevance of all of this to our problem is that every $2\pi$-periodic function $P\colon \mathbb R\to \mathbb C$ induces a function $Q\in L^2(\mathbb Z/N\mathbb Z)$ by setting $$ Q(n):=P\left( \frac{2\pi}{N}n\right),\quad n\in \mathbb Z /N\mathbb Z.$$ We apply this to $P_M(t)=\sum_{k=-M}^M c_k e^{ikt}$, a trigonometric polynomial of degree $M$. Setting $N:=2M+1$ we have that, on the one hand, $$Q(n)=\sum_{k=-M}^M \hat{Q}_M(k)e_k(n),$$ by the Fourier inversion formula. On the other hand, by definition, $$Q(n)=P_M\left( \frac{2\pi}{N}n\right)=\sum_{k=-M}^M c_k e_k(n).$$ Therefore, equating the last two formulas, we have that $$c_k=(Q, e_k)=\frac{1}{N}\sum_{n\in \mathbb Z/N\mathbb Z} P_M\left(\frac{2\pi}{N}n\right)\exp\left(-i\frac{2\pi}{N}nk\right),$$ which is the solution James gave.

The number $N=2M+1$ is the minimal one such that the last formula holds true for all trigonometric polynomials of degree $M$; indeed, the space of such trigonometric polynomials has dimension $2M+1$, which equals the dimension of $L^2(\mathbb Z/(2M+1)\mathbb Z)$. It is probably the case that the last formula holds true if $N$ is replaced by any larger integer, but I don't want to go into this.