---
tag: 3TXY35FR30
kind: definition
name: n-term approximation
msc: [41A46, 41A65]
defines: GEK0NP5WQM
uses: [03J5RAKB30, YDN0T4MEX0]
sources:
  - url: https://en.wikipedia.org/wiki/Sparse_approximation
---

## Definition

Let $X$ be a real or complex [[normed vector space|03J5RAKB30]] with norm $\norm{\cdot}$, and let $\mathcal{D} \subseteq X$ be a set, called the *dictionary*.
Let $n \ge 1$ be an integer.
The set of *$n$-term approximants* is
$$\Sigma_n(\mathcal{D}) = \set{\textstyle\sum_{k=1}^{n} c_k g_k : c_k \text{ scalars}, \ g_k \in \mathcal{D}} .$$
The *error of best $n$-term approximation* of $f \in X$ is
$$\sigma_n(f, \mathcal{D}) = \inf\set{\norm{f - g} : g \in \Sigma_n(\mathcal{D})} .$$
*$n$-term approximation* is the approximation of elements $f \in X$ by elements of $\Sigma_n(\mathcal{D})$, measured by $\sigma_n(f, \mathcal{D})$.

## Remarks

This is the [[error of best approximation|YDN0T4MEX0]] 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.