Sparse approximation - Wikipedia

Abstraction: Finding fewest-nonzero-coefficient signal representation in a dictionary

Key points:

• Sparse approximation seeks the sparsest solution x to y = Dx where D is an underdetermined dictionary matrix; the ℓ₀ pseudo-norm minimization problem is NP-hard.
• Basis pursuit relaxes ℓ₀ to ℓ₁ (convex), solvable by linear programming; matching pursuit (MP) and orthogonal matching pursuit (OMP) are greedy alternatives.
• Under conditions on the dictionary (restricted isometry property, mutual coherence, or spark), the sparse solution is unique and BP/OMP recover it exactly.
• Structured sparsity extensions: block/group sparsity (atoms picked in groups), collaborative sparse coding (joint support across multiple signals).
• Applications span image processing, medical imaging, machine learning, array processing, and convolutional neural network analysis via sparse coding.
• Stage-wise greedy methods (CoSaMP, Subspace Pursuit) improve upon basic OMP by adding groups of atoms and including pruning steps per iteration.

Connections: Sparse Approximation · Basis Pursuit · Matching Pursuit · Compressed Sensing

Source: http://en.wikipedia.org/wiki/Sparse_approximation