Best s-term ℓ1 approximation error

Let $n,s\in \mathbb{N}$ with $n\ge 1$ and $1\le s\le n$, and let $x\in {\mathbb{R}}^n$. Use one-based labels $[n]=\{1,\dots ,n\}$, identifying label $j$ with library coordinate $j-1$. For $T\subseteq [n]$, let $x_{T^c}$ retain the coordinates outside $T$ and vanish on $T$, where $T^c=[n]\setminus T$. Define the best $s$-term ${\mathrm{\ell }}^1$ approximation error by ${\sigma }_s(x{)}_1:=\min \{\mathrm{\parallel }{x}_{T^c}{\mathrm{\parallel }}_1:T\subseteq [n],\mathrm{\mid }T\mathrm{\mid }\le s\}\mathrm{.}$ The indexing family is finite and nonempty, so the displayed minimum exists and is attained.

One-based coordinate labels and coordinate restrictions

The finite-dimensional one-norm

Minimum of a real set

Attainment of minima on finite nonempty real sets

Finiteness of the power set of a finite set

Finiteness of a subfamily of a finite set

Finite-set convention

Cardinalities of finite sets, including the empty set

Bijection convention for equinumerous sets

Every nonzero natural number is a successor

Foucart and Rauhut, A Mathematical Introduction to Compressive Sensing, §2.1 Definition 2.2, printed p. 42, and §4.3

Mendelson, Rauhut, and Ward, Improved Bounds for Sparse Recovery from Subsampled Random Convolutions, §2.1

The attainment clause follows from an explicit finite enumeration. The canonical relabeling $j\mapsto j-1$ identifies $[n]$ bijectively with the library index set $n=\{0,\dots ,n-1\}$, so $[n]$ is finite and its power set is finite; the family ${\mathcal{T}}_s:=\{T\subseteq [n]:\mathrm{\mid }T\mathrm{\mid }\le s\}$ is a subset of that power set and is therefore finite. It is nonempty because $\mathrm{\varnothing }\in {\mathcal{T}}_s$. Since ${\mathcal{T}}_s$ is finite, there are a natural number $k$ and a bijection $e:k\to {\mathcal{T}}_s$. Nonemptiness implies $k\mathrm{\ne }0$, so write $k=\mathrm{\ell }+1$. For each $0\le j\le \mathrm{\ell }$, put $a_j:=\mathrm{\parallel }{x}_{e(j{)}^c}{\mathrm{\parallel }}_1$. Surjectivity of $e$ gives $\{\mathrm{\parallel }{x}_{T^c}{\mathrm{\parallel }}_1:T\in {\mathcal{T}}_s\}=\{a_0,\dots ,a_{\mathrm{\ell }}\}\mathrm{.}$ This is a finite nonempty set of real numbers. Applying the finite-list minimum result to $a_0,\dots ,a_{\mathrm{\ell }}$ gives a minimum that is one of these values, hence belongs to the displayed value set. Therefore the displayed minimum in the Definition is attained.