Highly Nonlinear Approximations for Sparse Signal Representation
Project Overview
Sparse representation of information by decreasing the dimensionality of a data set without losing its information is a central aim of signal processing. Emerging non-linear techniques for signal representation achieve this goal by decomposing the signal as a superposition of elements, normally referred to as ‘atoms’, selected from a large redundant set called a ‘dictionary’. The problem of finding the sparsest representation of a signal is, in general, intractable with classical computers. However, highly non-linear approximations have been proved to be very powerful, even when implemented by algorithms which do not seek the optimal solution with regard sparseness, but attempt to make tractable the problem of finding a sparse enough solution.
This project focuses on the development of highly non-linear methods for sparse signal representation and disseminates the computational tools for their implementation. The proposed methods evolve by stepwise selection of atoms extending those developed within the previous EPSRC project, "Biorthoganol Techniques for Optimal Signal Representation". Present methods improve upon the previous ones by correcting the stepwise selections so as to guarantee a gain in sparsity. Moreover, the techniques generalise the previously proposed by allowing for the discrimination of structured information. Cardinal spline and cardinal spline wavelet dictionaries have also been generalised to the non-uniform case thus allowing spline space adaption in the representation of a given signal.
The conclusions of the project relating to the potential of highly non-linear approximations are strong. One of the findings establishes that particular combinations of dictionaries are especially suitable for achieving high sparsity levels in representing images at the visually acceptable PSNR of 40dB. The increment in complexity introduced by redundant dictionaries is compensated for by the fact that the algorithms involve simple operations that are fully implementable with parallel processing. Hence their real time implementation is foreseen in the near future.
A bonus arising from the project findings asserts that sparse representations may also be used for information storage. We have shown that the space generated by the sparse representation of an image can be used, for instance, to store part of the image itself. We have termed this application ‘Image Folding’.
