Say I have a monotonically increasing function$f : [0,1] \to {\Bbb R}$. I only know the values of$f$ for a finite set of points$x_1, \dots, x_n$. Can I use a Fourier series to approximate the function?
My rough idea was to compute a finite number$m$ of coefficients of a Fourier series (with$m$ "small" compared to$n$) so that the function defined by this finite Fourier series approximates$f$.
- 1$\begingroup$Read about Shannon sampling theorem. If the function is band limited, you can reconstruct it perfectly after sampling at our greater than the Nyquist rate. You can make the Fourier connection after that$\endgroup$Srini– Srini2025-09-23 18:21:49 +00:00CommentedSep 23 at 18:21
- $\begingroup$The Fourier series was first developed by sampling the function to interpolate (vibrating string problem). You could interpolate your points by a polynomial and then obtain its Fourier series, or simply link this points with straight lines.$\endgroup$mlg– mlg2025-09-23 18:30:31 +00:00CommentedSep 23 at 18:30
- $\begingroup$What do you know about $f$? Is its co-domain $\Bbb R$? Is it polynomial? Rational? Smooth? Continuous? Please keep in mind that a realization of Gaussian white noise can also be thought of as a function, though it is "maximally pathological" in some sense. Is it the case that $x_1 < x_2 < \dots< x_n$?$\endgroup$Rodrigo de Azevedo– Rodrigo de Azevedo2025-09-24 11:10:41 +00:00CommentedSep 24 at 11:10
- $\begingroup$@RodrigodeAzevedo $f(x)$ is a function from $[0,1] \rightarrow \mathbb{R}$ which is monotonically increasing. Otherwise I do not know much about it.$\endgroup$JF Meier– JF Meier2025-09-24 13:58:34 +00:00CommentedSep 24 at 13:58
- $\begingroup$@RodrigodeAzevedo Probably continuous. What do you mean by co-domain? It is a function from $[0,1]$ to $\mathbb{R}$. Let me also note that it is common notation to write a function as $f(x)$. The motivation is the analysis of runtimes of algorithms.$\endgroup$JF Meier– JF Meier2025-09-25 08:03:59 +00:00CommentedSep 25 at 8:03
1 Answer1
Yes, you can. But do you want to?
You can interpolate any finite data set with a Fourier series. A Fourier transform for$n$ points can always be constructed with$O(n^2)$ work. (In important special cases, in$O(n \log(n))$.) The number of terms that you get out will equal the number of points in the data set. But the primary characteristic of a Fourier series is that it is periodic. That means that the interpolation will have a discontinuity at the ends. This shows up in the series as a "ringing", a rapid oscillation near the ends so that the ends can meet up. Seehttps://en.wikipedia.org/wiki/Gibbs_phenomenon for more.
What this means in practical terms is that you've lost the only thing you know - monotone increasing - for a characteristic you didn't want - periodic.
As a principle, we want our approximations to be simple and our errors small. A Fourier transform will have particularly small errors near the end. I'd give a shot at a polynomial interpolation first.
You mustlog in to answer this question.
Explore related questions
See similar questions with these tags.