Authors: Abdeldjalil AISSA-EL-BEY
Comments: 149 Pages. French
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.
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 using 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.
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.
Category: Digital Signal Processing