Highly Nonlinear Approximations for Sparse Signal Representation

• Project Overview
• Tutorial [.ps | .pdf]
• Source code
• Examples
• Publications
• EIFS
• SCEIFS
• Acknowledgements

• Home
• maths@Aston
• EPSRC Home

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

$$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]:

$$B_{1,j}(x) = \begin{cases} 1, & t_j\leq x<t_{j+1},\\ 0, & {\rm otherwise,} \end{cases}$$

$$B_{m,j}(x) = \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

$${\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

$${\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

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

we generate two subpartitions as

$$\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$).

This project is supported by EPSRC (EP/D062632/1)