Approximation of Points on Low-Dimensional Manifolds Via Random Linear Projections

Here is something that appeared on the Arxiv radar screen: Approximation of Points on Low-Dimensional Manifolds Via Random Linear Projections by Mark A. Iwen, Mauro Maggioni. The abstract reads:

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.

The  Geometric Multi-Resolution Analysis Code is here.  Mauro  tells me that "...We will be uploading the code in the next few days, as part of an update to the Geometric Multi-Resolution code...". Stay tuned!

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.