Highly Nonlinear Approximations for Sparse Signal Representation
and the seismic signal plotted in the Fig. 8.
We deal with the chirp signal on the interval , by discretizing it into samples and applying Algorithm 1 to produce the partition. The resulting number of knots is , which is enough to approximate the signal, by a cubic B-spline basis for the space, within the precision . A dictionary for the identical space is constructed by considering 10 subpartitions, which yield functions.
The signal is a piece of data. A partition of cardinality is obtained as and the dictionary of cubic splines we have used arises by considering subpartitions, which yields a dictionary of cardinality .
the atoms of the
th-dictionary, we look now for the subsets of indices
providing us with
a sparse representation of the signals. In other words,
we are interested in the approximations
such that and the values are satisfactory small for the approximation to be considered sparse. Since the problem of finding the sparsest solution is intractable, for all the signals we look for a satisfactory sparse representation using the same greedy strategy, which evolves by selecting atoms through stepwise minimization of the residual error as follows.
- The atoms are selected one by one according to the Optimized Orthogonal Matching Pursuit (OOMP) method  until the above defined tolerance for the norm of the residual error is reached.
- The previous approximation is improved, without greatly increasing the computational cost, by a `swapping refinement' which at each step interchanges one atom of the atomic decomposition with a dictionary atom, provided that the operation decreases the norm of the residual error .
- A Backward-Optimized Orthogonal Matching Pursuit (BOOMP)
method  is applied to disregard some coefficients of
the atomic decomposition, in order to produce an approximation up
to the error of stage i). The last two steps are repeated until no
further swapping is possible. The routine implementing
the steps is OOMPFinalRefi.m.
|Dictionaries||(signal )||(signal )|
|Non-uniform spline basis||1097||322|
|Non-uniform spline dictionary||173||129|
|Discreet cosine transform||263||208|
|Cardinal Chui-Wang wavelet basis||246||201|
|Cardinal Chui-Wang wavelet dictionary||174||112|
Notice that whilst the non-uniform spline space is adapted to the corresponding signal, only the dictionary for the space achieves the sparse representation. Moreover the performance is superior to that of the Chui-Wang spline wavelet basis  and similar to the cardinal Chui-Wang dictionary, which is known to render a very good representation for these signals . However, whilst the Chui-Wang cardinal spline wavelet dictionaries introduced in  are significantly redundant with respect to the corresponding basis (about twice as larger) the non-uniform B-spline dictionaries introduced here contain a few more functions than the basis. Nevertheless, as the examples indicate, the improvement in the sparseness of the approximation a dictionary may yield with respect to the B-spline basis is enormous.