4.6 Review

From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images

Journal

SIAM REVIEW
Volume 51, Issue 1, Pages 34-81

Publisher

SIAM PUBLICATIONS
DOI: 10.1137/060657704

Keywords

underdetermined; linear system of equations; redundant; overcomplete; sparse representation; sparse coding; basis pursuit; matching pursuit; mutual coherence; Sparse-Land; dictionary learning; inverse problems; denoising; compression

Funding

  1. Israel Science Foundation (ISF) [796/05]
  2. Binational Science Foundation (BSF) [2004199]
  3. Applied Materials research fund

Ask authors/readers for more resources

A full-rank matrix A is an element of R-nxm with n < m generates an underdetermined system of linear equations Ax = b having infinitely many solutions. Suppose we seek the sparsest solution, i.e., the one with the fewest nonzero entries. Can it ever be unique? If so, when? As optimization of sparsity is combinatorial in nature, are there efficient methods for finding the sparsest solution? These questions have been answered positively and constructively in recent years, exposing a wide variety of surprising phenomena, in particular the existence of easily verifiable conditions under which optimally sparse solutions can be found by concrete, effective computational methods. Such theoretical results inspire a bold perspective on some important practical problems in signal and image processing. Several well-known signal and image processing problems can be cast as demanding solutions of undetermined systems of equations. Such problems have previously seemed, to many, intractable, but there is considerable evidence that these problems often have sparse solutions. Hence, advances in finding sparse solutions to underdetermined systems have energized research on such signal and image processing problems-to striking effect. In this paper we review the theoretical results on sparse solutions of linear systems, empirical results on sparse modeling of signals and images, and recent applications in inverse problems and compression in image processing. This work lies at the intersection of signal processing and applied mathematics, and arose initially from the wavelets and harmonic analysis research communities. The aim of this paper is to introduce a few key notions and applications connected to sparsity, targeting newcomers interested in either the mathematical aspects of this area or its applications.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.6
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available