May 2010; Revised October, 2010 | Emmanuel J. Candès, Yonina C. Eldar, Deanna Needell, Paige Randall
This paper presents novel results on the recovery of signals from undersampled data when the signals are not sparse in an orthonormal basis or incoherent dictionary, but in a redundant dictionary. It shows that compressed sensing is viable in this context and that accurate recovery is possible via an $\ell_1$-analysis optimization problem. The paper introduces a condition on the measurement matrix, a natural generalization of the restricted isometry property (RIP), which guarantees accurate recovery of signals nearly sparse in highly overcomplete and coherent dictionaries. This condition does not impose incoherence restrictions on the dictionary, and the results may be the first of this kind. The paper discusses practical examples and the implications of the results on applications, and complements the study by demonstrating the potential of $\ell_1$-analysis for such problems.
The paper introduces a new condition, the D-RIP (dictionary-RIP), which generalizes the standard RIP to accommodate redundant and coherent dictionaries. It shows that the solution to the $\ell_1$-analysis problem is very accurate provided that $D^*f$ has rapidly decreasing coefficients. The paper also discusses implications of the results for various applications, including multitone signals, radar, images, and concatenations of dictionaries. It shows that the recovery error is proportional to the measurement error and the tail of the signal, and that for compressible signals, the approximation error is very small, while for exactly sparse signals, it completely vanishes.
The paper also discusses the implications of the results for the use of redundant and coherent dictionaries in compressed sensing. It shows that the D-RIP is satisfied by many types of random measurement matrices, including Gaussian, subgaussian, and Bernoulli matrices. The paper also shows that the D-RIP is satisfied by the randomly subsampled Fourier matrix when multiplied by a random sign matrix. The paper concludes that compressed sensing with redundant and coherent dictionaries is viable with the same advantages as in the standard setting.This paper presents novel results on the recovery of signals from undersampled data when the signals are not sparse in an orthonormal basis or incoherent dictionary, but in a redundant dictionary. It shows that compressed sensing is viable in this context and that accurate recovery is possible via an $\ell_1$-analysis optimization problem. The paper introduces a condition on the measurement matrix, a natural generalization of the restricted isometry property (RIP), which guarantees accurate recovery of signals nearly sparse in highly overcomplete and coherent dictionaries. This condition does not impose incoherence restrictions on the dictionary, and the results may be the first of this kind. The paper discusses practical examples and the implications of the results on applications, and complements the study by demonstrating the potential of $\ell_1$-analysis for such problems.
The paper introduces a new condition, the D-RIP (dictionary-RIP), which generalizes the standard RIP to accommodate redundant and coherent dictionaries. It shows that the solution to the $\ell_1$-analysis problem is very accurate provided that $D^*f$ has rapidly decreasing coefficients. The paper also discusses implications of the results for various applications, including multitone signals, radar, images, and concatenations of dictionaries. It shows that the recovery error is proportional to the measurement error and the tail of the signal, and that for compressible signals, the approximation error is very small, while for exactly sparse signals, it completely vanishes.
The paper also discusses the implications of the results for the use of redundant and coherent dictionaries in compressed sensing. It shows that the D-RIP is satisfied by many types of random measurement matrices, including Gaussian, subgaussian, and Bernoulli matrices. The paper also shows that the D-RIP is satisfied by the randomly subsampled Fourier matrix when multiplied by a random sign matrix. The paper concludes that compressed sensing with redundant and coherent dictionaries is viable with the same advantages as in the standard setting.