n-term approximation

Remarks

This is the error of best approximation from the set $\Sigma_n(\mathcal{D})$, which is a union of subspaces and not a subspace. Indeed $\Sigma_n + \Sigma_n \subseteq \Sigma_{2n}$, but in general $\Sigma_n + \Sigma_n \ne \Sigma_n$. Example: let $X$ be a Hilbert space with orthonormal basis $\mathcal{D} = (e_j)$ and $f = \sum_j a_j e_j$. Keeping the $n$ coefficients $a_j$ of largest absolute value gives a best approximant, and $\sigma_n(f, \mathcal{D})^2$ is the sum of $\abs{a_j}^2$ over the remaining indices. Check: for $g = \sum_{j \in S} c_j e_j$ with $\abs{S} \le n$, $\norm{f - g}^2 = \sum_{j \in S} \abs{a_j - c_j}^2 + \sum_{j \notin S} \abs{a_j}^2$, which is smallest when $c_j = a_j$ and $S$ carries the largest $\abs{a_j}$. Non-example: in $\R^3$ with the standard basis, $3e_1 + e_2 + 2e_3$ is not in $\Sigma_2$, since it has three nonzero coordinates. When $\mathcal{D}$ is redundant, the best approximant may be hard to compute, and greedy algorithms are used instead.