Determine negligible coefficients in spectrum

Question

Suppose I have some function $f$ that I have sampled at $N$ points and I preform a transform on it (this could be a Fourier transform, or perhaps a Hadamard, or really anything eles - I'm hoping for a general answer) to get the function $\hat{f}$. Really, $\hat{f}$ represents the coefficients of the basis elements of the transform that I need to reconstruct $f$. The question is this: is there a way to determine which coefficients are the least important for the reconstruction? Ie, once I have obtained $\hat{f}$, is there a way to determine the smallest set of coefficients needed to reconstruct $f$ within some error tolerance $\epsilon$?

Answer 1

Let us restrict the problem to a linear transform, $\mathbf{A}$. Your reconstruction requirement is $\Vert \mathbf{A}\hat{\mathbf{x}} - \mathbf{x} \Vert_2 < \epsilon$. The "smallest" set of coefficients will the be that $\hat{\mathbf{x}}$ which has the minimum $\ell_0$ norm:

$$ \min_{\hat{\mathbf{x}}} \Vert \hat{\mathbf{x}}\Vert_0 \,\, \mathrm{s.t.} \,\, \Vert \mathbf{A}\hat{\mathbf{x}} - \mathbf{x} \Vert_2 < \epsilon $$

The above problem is NP-hard, so it's not feasible. However, there are many situations in which the following convex problem will give the correct answer:

$$ \min_{\hat{\mathbf{x}}} \Vert \hat{\mathbf{x}}\Vert_1 \,\, \mathrm{s.t.} \,\, \Vert \mathbf{A}\hat{\mathbf{x}} - \mathbf{x} \Vert_2 < \epsilon $$

The above is generally referred to a Basis Pursuit De-Noising, though it has has no fixed name. If you look for things like "sparse optimzation" or "$\ell_1$ minimization", you will find several references and freely available software packages that will implement the above.