  The fields of compressed sensing (CS) and matrix completion have shown that
high-dimensional signals with sparse or low-rank structure can be effectively
projected into a low-dimensional space (for efficient acquisition or
processing) when the projection operator achieves a stable embedding of the
data by satisfying the Restricted Isometry Property (RIP). It has also been
shown that such stable embeddings can be achieved for general Riemannian
submanifolds when random orthoprojectors are used for dimensionality reduction.
Due to computational costs and system constraints, the CS community has
recently explored the RIP for structured random matrices (e.g., random
convolutions, localized measurements, deterministic constructions). The main
contribution of this paper is to show that any matrix satisfying the RIP (i.e.,
providing a stable embedding for sparse signals) can be used to construct a
stable embedding for manifold-modeled signals by randomizing the column signs
and paying reasonable additional factors in the number of measurements. We
demonstrate this result with several new constructions for stable manifold
embeddings using structured matrices. This result allows advances in efficient
projection schemes for sparse signals to be immediately applied to manifold
signal models.
