# Approximation using a Fourier transform with low pass filter

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?

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$.
$$\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.