0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Have you ever heard of the discrete Fourier transform? And for the bonus task, the discrete cosine transform? $\endgroup$ – LutzL Dec 11 '17 at 13:25
  • $\begingroup$ @LutzL: Yes, I know something about that. Thank you for the pointer $\endgroup$ – Giuseppe Negro Dec 11 '17 at 14:33
  • $\begingroup$ @LutzL: I have added some remarks to your good comment. Thank you again. $\endgroup$ – Giuseppe Negro Dec 15 '17 at 21:09
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Good solution, thank you. I have added some remarks in an answer. $\endgroup$ – Giuseppe Negro Dec 15 '17 at 21:09
  • $\begingroup$ Great! I was looking for exactly this kind of explanation. $\endgroup$ – Giuseppe Negro Dec 16 '17 at 10:04
  • $\begingroup$ If I understand correctly, here you proved a baby version of the sampling theorem at en.m.wikipedia.org/wiki/…, am I right? $\endgroup$ – Giuseppe Negro Dec 19 '17 at 18:43
  • 1
    $\begingroup$ Yes, it is sort of the same argument; Poisson summation, Shannon sampling, etc. There is a collection of tools in spectral differentiation. The above uniform sampling works well for periodic functions. For non-periodic functions, there is the Chebyshev method. $\endgroup$ – James Dec 20 '17 at 0:40
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks much, Giuseppe. I added a bit more on your last point. $\endgroup$ – James Dec 16 '17 at 4:09

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.