Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization

Given a dictionary D = d (k) of vectors d (k), we seek to represent a signal S as a linear combination S = summation operator (k) gamma (k) 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 S has a sufficiently sparse representation, this representation is unique and can be found by solving a convex optimization problem: specifically, minimizing the l (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.