×

Optimally sparse representation in general (nonorthogonal) dictionaries via \(\ell^1\) minimization. (English) Zbl 1064.94011

Summary: Given a dictionary D\(= \{\underline{d}_k\}\) of vectors \(\underline{d}_k\), we seek to represent a signal \(\underline{S}\) as a linear combination \(\underline{S}= \sum_k \gamma(k) \underline{d}_k\), with scalar coefficients \(\gamma(k)\). In particular, we aim for the sparsest representation possible. In general, this requires a combinatorial optimization process. Previous work considered the special case where D is an overcomplete system consisting of exactly two orthobases and has shown that, under a condition of mutual incoherence of the two bases, and assuming that \(\underline{S}\) has a sufficiently sparse representation, this representation is unique and can be found by solving a convex optimization problem: specifically, minimizing the 1 norm of the coefficients \(\gamma\). In this article, we obtain parallel results in a more general setting, where the dictionary D can arise from two or several bases, frames, or even less structured systems. We sketch three applications: separating linear features from planar ones in 3D data, noncooperative multiuser encoding, and identification of over-complete independent component models.

MSC:

94A29 Source coding
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] SIAM REV 43 pp 129– (2001) · Zbl 0979.94010 · doi:10.1137/S003614450037906X
[2] PROCEEDINGS OF THE IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS 4 pp 106– (1999)
[3] Debrunner, IEEE transactions on image processing : a publication of the IEEE Signal Processing Society 6 (9) pp 1316– (1997) · doi:10.1109/83.623194
[4] MATH COMP 65 pp 1513– (1996) · Zbl 0853.42018 · doi:10.1090/S0025-5718-96-00780-6
[5] IEEE TRANS SIGNAL PROCESSING 11 pp 670– (2002)
[6] IEEE TRANS SIGNAL PROCESSING 41 pp 3397– (1993) · Zbl 0842.94004 · doi:10.1109/78.258082
[7] IEEE TRANS INF THEORY 47 pp 2845– (2001) · Zbl 1019.94503 · doi:10.1109/18.959265
[8] IEEE TRANS INF THEORY 48 pp 2558– (2002) · Zbl 1062.15001 · doi:10.1109/TIT.2002.801410
[9] CRYPTOGRAPHY LECTURE NOTES IN COMPUTER SCIENCE 149 pp 71– (1983) · doi:10.1007/3-540-39466-4_6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.