Sparse approximation (also known as sparse representation) theory deals with sparse solutions for systems of linear equations. Techniques for finding these solutions and exploiting them in applications have found wide use in image processing, signal processing, machine learning, medical imaging, and more.
Sparse decomposition
Noiseless observations Consider a linear system of equations x = D α {\displaystyle x=D\alpha } , where D {\displaystyle D} is an underdetermined m × p {\displaystyle m\times p} matrix ( m < p ) {\displaystyle (m<p)} and x ∈ R m , α ∈ R p {\displaystyle x\in \mathbb {R} ^{m},\alpha \in \mathbb {R} ^{p}} . The matrix D {\displaystyle D} (typically assumed to be full-rank) is referred to as the dictionary, and x {\displaystyle x} is a signal of interest. The core sparse representation problem is defined as the quest for the sparsest possible representation α {\displaystyle \alpha } satisfying x = D α {\displaystyle x=D\alpha } . Due to the underdetermined nature of D {\displaystyle D} , this linear system admits in general infinitely many possible solutions, and among these we seek the one with the fewest non-zeros. Put formally, we solve
min α ∈ R p ‖ α ‖ 0 subject to x = D α , {\displaystyle \min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}x=D\alpha ,}
where ‖ α ‖ 0 = # { i : α i ≠ 0 , i = 1 , … , p } {\displaystyle \|\alpha \|_{0}=\#\{i:\alpha _{i}\neq 0,\,i=1,\ldots ,p\}} is the ℓ 0 {\displaystyle \ell _{0}} pseudo-norm, which counts the number of non-zero components of α {\displaystyle \alpha } . This problem is known to be NP-hard with a reduction to NP-complete subset selection problems in combinatorial optimization. Sparsity of α {\displaystyle \alpha } implies that only a few ( k ≪ m < p {\displaystyle k\ll m<p} ) components in it are non-zero. The underlying motivation for such a sparse decomposition is the desire to provide the simplest possible explanation of x {\displaystyle x} as a linear combination of as few as possible columns from D {\displaystyle D} , also referred to as atoms. As such, the signal x {\displaystyle x} can be viewed as a molecule composed of a few fundamental elements taken from D {\displaystyle D} . While the above posed problem is indeed NP-Hard, its solution can often be found using approximation algorithms. One such option is a convex relaxation of the problem, obtained by using the ℓ 1 {\displaystyle \ell _{1}} -norm instead of ℓ 0 {\displaystyle \ell _{0}} , where ‖ α ‖ 1 {\displaystyle \|\alpha \|_{1}} simply sums the absolute values of the entries in α {\displaystyle \alpha } . This is known as the basis pursuit (BP) algorithm, which can be handled using any linear programming solver. An alternative approximation method is a greedy technique, such as the matching pursuit (MP), which finds the location of the non-zeros one at a time. Surprisingly, under mild conditions on D {\displaystyle D} (using the spark (mathematics), the mutual coherence or the restricted isometry property) and the level of sparsity in the solution, k {\displaystyle k} , the sparse representation problem can be shown to have a unique solution, and BP and MP are guaranteed to find it perfectly.
Noisy observations Often the observed signal x {\displaystyle x} is noisy. By relaxing the equality constraint and imposing an ℓ 2 {\displaystyle \ell _{2}} -norm on the data-fitting term, the sparse decomposition problem becomes
… excerpt ends here. Continue reading the full article.
