Background:

What are sparse representations/approximations?

Sparse representations are representations that account for most or all information of a signal with a linear combination of a small number of elementary signals called atoms. Often, the atoms are chosen from a so called over-complete dictionary. Formally, an over-complete dictionary is a collection of atoms such that the number of atoms exceeds the dimension of the signal space, so that any signal can be represented by more than one combination of different atoms.

What are sparse representations/approximations good for?

Sparseness is one of the reasons for the extensive use of popular transforms such as the Discrete Fourier Transform, the wavelet transform and the Singular Value Decomposition. The aim of these transforms is often to reveal certain structures of a signal and to represent these structures in a compact and sparse representation. Sparse representations have therefore increasingly become recognized as providing extremely high performance for applications as diverse as: noise reduction, compression, feature extraction, pattern classification and blind source separation. Sparse representation ideas also build the foundations of wavelet denoising and methods in pattern classification, such as in the Support Vector Machine and the Relevance Vector Machine, where sparsity can be directly related to learnability of an estimator.

How to find sparse representations/approximations?

The technique of finding a representation with a small number of significant coefficients is often referred to as Sparse Coding. Decoding merely requires the summation of the relevant atoms, appropriately weighted, however, unlike a transform coder with its invertible transform, the generation of the sparse representation with an over-complete dictionary is non-trivial. Indeed, the general problem of finding a representation with the smallest number of atoms from an arbitrary dictionary has been shown to be NP-hard. This has led to considerable effort being put into the development of many sub-optimal schemes. These include algorithms that iteratively build up the signal approximation one coefficient at a time, e.g. Matching Pursuit, Orthogonal Matching Pursuit, and those that process all the coefficients simultaneously, e.g. Basis Pursuit, Basis Pursuit De-Noising and the Focal Underdetermined System Solver family of algorithms. 

What are the open problems?

Even though there exist a range of empirical evidence for the performance of methods built on
sparse representation, many fundamental theoretical questions remain to be addressed. The main aims of this project are:
• Build a sound theoretical foundation for sparse representations
• Investigate the design and learning of good signal dictionaries and their resulting characteristics
• Develop, implement and analyze novel fast sparse approximation algorithms
• Explore the theoretical and practical performance of such approximations when applied to coding and
source separation.
• Develop a practical low rate sparse audio coding scheme based upon these ideas.

Sponsor:

This project is financed by EPSRC grant D000246