  This paper considers the approximate reconstruction of points, x \in R^D,
which are close to a given compact d-dimensional submanifold, M, of R^D using a
small number of linear measurements of x. In particular, it is shown that a
number of measurements of x which is independent of the extrinsic dimension D
suffices for highly accurate reconstruction of a given x with high probability.
Furthermore, it is also proven that all vectors, x, which are sufficiently
close to M can be reconstructed with uniform approximation guarantees when the
number of linear measurements of x depends logarithmically on D. Finally, the
proofs of these facts are constructive: A practical algorithm for
manifold-based signal recovery is presented in the process of proving the two
main results mentioned above.
