Highly Nonlinear Approximations for Sparse Signal Representation

Numerical examples

We produce here an example illustrating the potentiality of the proposed nonuniform dictionaries for achieving sparse representations by nonlinear techniques. The signals we consider are the chirp signal 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 .

Denoting by the atoms of the th-dictionary, we look now for the subsets of indices of cardinality 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.
i)
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.
ii)
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 .
iii)
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.

The described technique is applied to all the non-orthogonal dictionaries we have considered for comparison with the proposed approach. The results are shown in Table 1. In the first column we place the dictionaries to be compared. These are: 1) the spline basis for the space adapted to the corresponding signal. 2) The dictionary for the identical spaces consisting of functions of larger support. 3) The orthogonal cosine bases used by the discrete cosine transform (dct). 4) The semi-orthogonal cardinal Chui-Wang spline wavelet basis  and 5) the Chui-Wang cardinal spline dictionary for the same space .

 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.