Best s-Term Approximation

Suppose \(\mathbb{K}\) is either \(\mathbb{C}\) or \(\mathbb{R}\), \(x\in \mathbb{K}^N\) and \(s\le N\). We want to find the best approximation by \(s\)-sparse vectors .

For this, consider the permutation \(\pi\) of the non-increasing rearrangement \(x^*\) and set \(S=\{\pi^{-1}(1),\ldots ,\pi^{-1}(s)\}\). Then

\[ z=\begin{cases} x_j, & \text{if } j\in S,\\ 0, & \text{else,} \end{cases}\]

is the so-called best \(s\)-term approximation of \(x\).