Compressive sensing with redundant dictionaries and structured measurements

Sparse approximation methods for the recovery of signals from undersampled data when the signal is sparse in an overcomplete dictionary have received much attention recently due to their practical importance. A common assumption is the D-restricted isometry property (D-RIP), which asks that the sampling matrix approximately preserve the norm of all signals sparse in D. While many classes of random matrices satisfy this condition, those with a fast-multiply stemming from subsampled bases require an additional randomization of the column signs, which is not feasible in many practical applications. In this work, we demonstrate that one can subsample certain bases in such a way that the D-RIP will hold without the need for random column signs.