  Consider the problem of recovering an unknown signal from undersampled
measurements, given the knowledge that the signal has a sparse representation
in a specified dictionary $D$. This problem is now understood to be well-posed
and efficiently solvable under suitable assumptions on the measurements and
dictionary, if the number of measurements scales roughly with the sparsity
level. One sufficient condition for such is the $D$-restricted isometry
property ($D$-RIP), which asks that the sampling matrix approximately preserve
the norm of all signals which are sufficiently sparse in $D$. While many
classes of random matrices are known to satisfy such conditions, such matrices
are not representative of the structural constraints imposed by practical
sensing systems. We close this gap in the theory by demonstrating that one can
subsample a fixed orthogonal matrix in such a way that the $D$-RIP will hold,
provided this basis is sufficiently incoherent with the sparsifying dictionary
$D$. We also extend this analysis to allow for weighted sparse expansions.
Consequently, we arrive at compressive sensing recovery guarantees for
structured measurements and redundant dictionaries, opening the door to a wide
array of practical applications.
