Talk:Trigonometric interpolation

Errors in article

Due to the Stone-Weierstrass theorem this function exists and is unique. It is called complex trigonometric polynomial of degree N-1 and has the form ...

I don't think this article is correctly worded. First of all, a continuous function is certainly not uniquely determined by the requirement that it pass through n specified points, nor is this false statement implied by the Stone-Weierstrass theorem. The correct statement is more along the lines of, if you are looking for a periodic interpolating function of the given trigonometric form, then the coefficients are uniquely determined. However, even this is a bit too simplistic because there are multiple possible choices of trigonometric interpolation polynomial due to aliasing. See e.g. the discussion under discrete Fourier transform.

I don't have time to make this article not suck right now, but I thought I should tag it to warn readers, at least. —Steven G. Johnson 23:44, 12 December 2005 (UTC)

Ouch. I remember that I noticed this some time ago, but I postponed action first and forgot about it later. By the way, Stone-Weierstrass has nothing to do with it. I think {{disputed}} is still too weak, so I commented out most of the article (false info is worse than no info). Hopefully, I'll find time soon to fix it, if Steven hasn't done so before. -- Jitse Niesen (talk) 00:10, 13 December 2005 (UTC)

Gauss and the FFT

So, Gauss derived a FFT? i.e. a n*log(n) FFT? I never knew this. Why all the fuss about Cooley and Tukey then? Was Gauss' result not noticed until after Cooley-Tukey? Lavaka 20:32, 4 March 2007 (UTC)

Yes, Gauss discovered the same recursive decomposition as Cooley-Tukey (and noted that it could be performed recursively/repeatedly), although he didn't analyze the asymptotic complexity. However, Gauss' work was published only posthumously and in Latin, using a fairly cumbersome notation, and its relationship to FFTs was not noticed until well after Cooley and Tukey. Indeed, special cases of this algorithm were re-discovered several times throughout the 19th and early 20th centuries. Cooley and Tukey, however, came along at the right time: because programmable computers were widespread in 1965, and they published a very clear description and analyzed the asymptotic complexity (unlike previous discoverers), the algorithm spread like crazy following their paper. See also Cooley-Tukey FFT algorithm for more information and references. —Steven G. Johnson 16:55, 7 March 2007 (UTC)
Thanks Steven. As if I weren't impressed by Gauss already... Lavaka 23:32, 13 March 2007 (UTC)

Even number of nodes formula

I believe the formula is not correct. Suppose K = 1, so the polynomial should be in form (remember we are vanishing $\sin Kx$ term) $p(x) = a_0 + a_1 \cos x$ which satisfies $p(x) = p(2\pi - x)$ and cannot interpolate the following dataset: $(1,1), (2\pi - 1,2)$.

But if we conversely make $\cos K x$ gone, the problem becomes well-posessed. I believe, the correct version is

$t_k(x) = \frac{\cos\frac12(x+\alpha_k)}{\cos\frac12(x_k+\alpha_k)}\prod_{m=0,m\ne k}^{2K} \frac{\sin\frac12(x-x_m)}{\sin\frac12(x_k-x_m)}.$

Uranix (talk) 16:28, 14 September 2014 (UTC)