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…