Highly Nonlinear Approximations for Sparse Signal Representation


Building B-spline dictionaries

Let us start by recalling that an extended partition with single inner knots associated with $ S_m(\Delta )$ is a set $ \tilde{\Delta }=\{y_i\}_{i=1}^{2m+N}$ such that

$\displaystyle y_{m+i}=x_i,  i=1,\ldots,N,   x_1<\cdots<x_N$

and the first and last $ m$ points $ y_1\leq \cdots \leq y_{m} \leq
c,\quad d \leq y_{m+N+1}\leq \cdots \leq y_{2m+N}$ can be arbitrarily chosen. With each fixed extended partition $ \tilde{\Delta }$ there is associated a unique B-spline basis for $ S_m(\Delta )$, that we denote as $ \{B_{m,j}\}_{j=1}^{m+N}$. The B-spline $ B_{m,j}$ can be defined by the recursive formulae [23]:
$\displaystyle B_{1,j}(x)$ $\displaystyle =$ \begin{displaymath}\begin{cases}
1, & t_j\leq x<t_{j+1},\\
0, & {\rm otherwise,}
$\displaystyle B_{m,j}(x)$ $\displaystyle =$ $\displaystyle \frac{x-y_j}{y_{j+m-1}-y_j}B_{m-1,j}(x)+\frac{y_{j+m}-x}{y_{j+m}-y_{j+1}}B_{m-1,j+1}(x).$  

The following theorem paves the way for the construction of dictionaries for $ S_m(\Delta )$. We use the symbol $ \char93 $ to indicate the cardinality of a set.

Theorem 2   Let $ \Delta_j, j=1,\ldots,n$ be partitions of $ [c,d]$ and $ \Delta=\cup_{j=1}^n \Delta_j$. We denote the B-spline basis for $ S_m(\Delta_j)$ as $ \{B_{m,k}^{(j)}:k=1,\ldots,m+\char93 \Delta_j\}$. Accordingly, a dictionary, $ {\mathcal
D}_m(\Delta: \cup_{j=1}^n\Delta _j)$, for $ S_m(\Delta )$ can be constructed as

$\displaystyle {\mathcal D}_m(\Delta: \cup_{j=1}^n\Delta _j)   :=  
\cup_{j=1}^n \{B_{m,k}^{(j)}:k=1,\ldots, m+\char93 \Delta_j \},

so as to satisfy

$\displaystyle {\rm span}\{{\mathcal D}_m(\Delta: \cup_{j=1}^n\Delta _j)
\}  =  S_m(\Delta).

When $ n=1$, $ {\mathcal D}_m(\Delta:\Delta _1)$ is reduced to the B-spline basis of $ S_m(\Delta )$.

Remark 4   Note that the number of functions in the above defined dictionary is equal to $ n\cdot m+\sum_{j=1}^n\char93 \Delta_j$, which is larger than $ \dim S_m(\Delta)=m+\char93 \Delta$. Hence, excluding the trivial case $ n=1$, the dictionary constitutes a redundant dictionary for $ S_m(\Delta )$.

According to Theorem 2, to build a dictionary for $ S_m(\Delta )$ we need to choose $ n$-subpartitions $ \Delta_j\in
\Delta$ such that $ \cup_{j=1}^n\Delta_j=\Delta$. This gives a great deal of freedom for the actual construction of a non-uniform B-spline dictionary. Fig.7 shows some examples which are produced by generating a random partition of $ [0,4]$ with 6 interior knots. From an arbitrary partition

$\displaystyle \Delta   :=   \{0=x_0<x_1<\cdots <x_{6}<x_{7}=4\},

we generate two subpartitions as

$\displaystyle \Delta _1  :=   \{0=x_0<x_1<x_3<x_{5}<x_{7}=4\}, \quad
\Delta _2  :=   \{0=x_0<x_2<x_4<x_{6}<x_{7}=4\}$

and join together the B-spline basis for $ \Delta _1$ (light lines in the right graphs of Fig.7) and $ \Delta _2$ (dark lines in the same graphs)

Figure 7: Examples of bases (graphs on the left) and the corresponding dictionaries (right graphs) for a random partition The top graphs correspond to linear B-splines ($ m=2$). The bottom graphs involve cubic B-splines ($ m=4$).
\includegraphics[width=8cm]{2-1.eps} \includegraphics[width=8cm]{re1-3.eps}
\includegraphics[width=8cm]{1.eps} \includegraphics[width=8cm]{re2-3.eps}