---
tag: D94626DTTW
kind: definition
name: Nonlinear approximation
msc: [41A46, 41A25]
defines: YS1GRQRVY7
uses: [03J5RAKB30, YDN0T4MEX0, 0S9GGTR0EX]
sources:
  - url: https://en.wikipedia.org/wiki/Approximation_theory
---

## Definition

Let $X$ be a [[normed space|03J5RAKB30]] and let $\Sigma_0 \subseteq \Sigma_1 \subseteq \Sigma_2 \subseteq \cdots$ be subsets of $X$, which in general are not linear subspaces.
Usually there is a constant $c$ with $\Sigma_n + \Sigma_n \subseteq \Sigma_{cn}$.
*Nonlinear approximation* is the approximation of elements $f \in X$ by elements of $\Sigma_n$, measured by the [[error of best approximation|YDN0T4MEX0]]
$$\sigma_n(f) = \inf_{s \in \Sigma_n} \norm{f - s}_X.$$
The main example is $n$-term approximation from a dictionary $\mathcal{D} \subseteq X$, with $\Sigma_n = \set{\sum_{k=1}^{n} c_k g_k : c_k \in \R,\ g_k \in \mathcal{D}}$.

## Remarks

Example: let $X$ be a separable Hilbert space with [[orthonormal basis|0S9GGTR0EX]] $(e_j)$, and let $\Sigma_n$ be the vectors with at most $n$ nonzero coordinates.
The set $\Sigma_1$ is not a subspace: $e_1, e_2 \in \Sigma_1$ but $e_1 + e_2 \notin \Sigma_1$.
For $f = \sum_j c_j e_j$, the best element of $\Sigma_n$ keeps the $n$ coefficients of largest absolute value, so $\sigma_n(f)^2$ is the sum of $\abs{c_j}^2$ over all other $j$.

Non-example: $\Sigma_n$ the polynomials of degree at most $n$ in $C[0, 1]$ is a linear subspace, so approximation from it is linear approximation.