Highly Nonlinear Approximations for Sparse Signal Representation


Background and notations

We refer to the fundamental books [23,25] for a complete treatment of splines. Here we simply introduce the notation and basic definitions which are needed in the present context.

Definition 1   Given a finite closed interval $ [c,d]$ we define a partition of $ [c,d]$ as the finite set of points

$\displaystyle \Delta :=\{x_i\}_{i=0}^{N+1}, N\in\mathbb{N},  $such that$\displaystyle   
 c=x_0<x_1<\cdots<x_{N}<x_{N+1}=d.$ (34)

We further define $ N$ subintervals $ I_i, i=0,\dots,N$ as: $ I_i=[x_i,x_{i+1}), i=0,\dots,N-1$ and $ I_N=[x_N,x_{N+1}]$.

Definition 2   Let $ \Pi_{m}$ be the space of polynomials of degree smaller than or equal to $ m\in\mathbb{N}_0=\mathbb{N}\cup\{0\}$, i.e.,

$\displaystyle \{\Pi_m(x): \Pi_m(x)=\sum_{i=0}^m a_ix^i,\; x\in \mathbb{R}\Big\},$

and define

$\displaystyle S_m(\Delta )=\{f\in C^{m-2}[c,d] :  f\vert _{I_i}\in\Pi_{m-1},
 i=0,\dots,N\},$ (35)

where $ f\vert _{I_i}$ indicates the restriction of the function $ f$ on the interval $ {I_i}$.

The construction of nonuniform dictionaries arises from the next proposition [21]

Theorem 1   Suppose that $ \Delta_j,j=1,\ldots,n$ are partitions of $ [c,d]$. Then

$\displaystyle S_m(\Delta_1) +\cdots + S_m(\Delta_n)  =  S_m(\cup_{j=1}^n\Delta_j).