1
$\begingroup$

I need to approximate a function f, but I cannot do so with frequencies that exceed 1kHz

What is the best approximation I can get? Is taking the Fourier transform then zeroing any term above 1kHz the best approximation? Or can I fiddle with the lower order terms and get a better fit?

This is a made up scenario, but I have to prove the same concept with Walsh transforms. I am fairly certain that the lower order terms form the best approximation from random twiddling and hill climbing searches, but I need proof.

I believe the proof is something very similar to a least squares regression proof, but I can't get it. Has this problem been solved before? At least in the Fourier domain?

$\endgroup$
2
$\begingroup$

Depends on what you mean by 'best'. In terms of least squares, then yes, just knocking off the terms above 1kHz will give the closest approximation. I guess one way to prove it would be: $$ x(t) = \int_{-\infty}^{\infty} X(f)\exp\left( j2\pi ft \right) dt\\ \hat x(t) = \int_{-1k}^{1k} X(f) \exp\left( j2\pi ft \right) dt $$ leaving a residual error of $$ e(t) = \int_{|f| > 1k} X(f)\exp\left( j2\pi ft \right) dt . $$

Compare this to a 'fiddled' version, using $\tilde X(f)$ for the coefficients: $$ \hat x(t) = \int_{-1k}^{1k} \tilde X(f) \exp\left( j2\pi ft \right) dt, $$ which has a residual error of $$ e(t) = \int_{|f| \le 1k} \left(X(f) - \tilde X(f)\right) \exp\left( j2\pi ft \right) dt + \int_{|f| > 1k} X(f)\exp\left( j2\pi ft \right) dt , $$ which is greater than the error in the first instance unless $\tilde X(f) = X(f) \; \forall f$.

Something like that ought to do it, anyway.

EDIT: It is possible to prove that a projection onto any orthogonal set of functions (doesn't need to be the Fourier set) gives the least squares fit:

$$ \int f_k(t) f_m(t) dt = \cases{ 0, & $k \ne m$ \\ 1/\lambda_k, & $k = m$} $$ for any orthogonal basis set $\{f_k\}$ (I'm not bothering with weighting functions), where $$ \lambda_k = \frac{1}{\int f^2(t) dt} $$ The projection of $g(t)$ onto the set is given by $$ c_k = \lambda_k \int g(t)f_k(t) dt. $$ The least squares fit of a set of orthogonal basis function is the minimisation of $$ \int \left[g(t) - \sum_k d_k f_k(t)\right]^2 dt. $$ Minimise by setting the derivative (wrt $d_m$) to zero: $$ 2\int\left(g(t) - \sum_kd_kf_k(t)\right)\left(-f_m(t)\right) dt = 0 \\ -\int f_m(t)g(t)dt + \int f_m(t)\sum_kd_kf_k(t)dt = 0 \\ -\int f_m(t)g(t)dt + \sum_kd_k \int f_m(t)f_k(t)dt = 0 \\ -\int f_m(t)g(t)dt + \sum_kd_k \frac{1}{\lambda_m} = 0 $$ which rearranges to give the same value as for $c_k$, thus the least squares fit is exactly the straightforward projection onto the orthogonal set.

$\endgroup$
  • $\begingroup$ Thank you. I had something like this floating in pieces. I had an idea that the orthogonality was going to be an important part of it. This answer is awesome. Thank you so much for the extra detail $\endgroup$ – MaxRunFast Mar 21 '13 at 16:32

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.