Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 340 / 2 / a / Solution

Fix the ordering of the orthonormal basis and write $c_m=⟨f,g_m⟩$, taking indices from $1$. The linear N-term approximation retains the first $N$ coefficients:Its index set is independent of $f$, so the map is an orthogonal projection and is linear.

For the nonlinear N-term approximation, let ${\Lambda }_N(f)$ be any set of $N$ indices with greatest $|c_m|$, resolving ties arbitrarily and padding with zero coefficients if necessary. Since $(c_m)\in {\ell }^2$, such a selection exists. ThenThe Parseval identity shows that for any fixed index set the displayed coefficients minimize the Hilbert space error. Choosing the largest squared magnitudes minimizes the omitted sum over every set of at most $N$ indices. This is the best N-term approximation; dependence of the selected indices on $f$ makes the operation nonlinear.