TY - JOUR

T1 - Random projections of smooth manifolds

AU - Baraniuk, Richard G.

AU - Wakin, Michael B.

N1 - Funding Information:
This research was supported by ONR grants N00014-06-1-0769 and N00014-06-1-0829; AFOSR grant FA9550-04-0148; DARPA grants N66001-06-1-2011 and N00014-06-1-0610; NSF grants CCF-0431150, CNS-0435425, CNS-0520280, and DMS-0603606; and the Texas Instruments Leadership University Program. Web: dsp.rice.edu/cs.

PY - 2009/2

Y1 - 2009/2

N2 - We propose a new approach for nonadaptive dimensionality reduction of manifold-modeled data, demonstrating that a small number of random linear projections can preserve key information about a manifold-modeled signal. We center our analysis on the effect of a random linear projection operator Φ: N → M , M<N, on a smooth well-conditioned K-dimensional submanifold N . As our main theoretical contribution, we establish a sufficient number M of random projections to guarantee that, with high probability, all pairwise Euclidean and geodesic distances between points on are well preserved under the mapping Φ. Our results bear strong resemblance to the emerging theory of Compressed Sensing (CS), in which sparse signals can be recovered from small numbers of random linear measurements. As in CS, the random measurements we propose can be used to recover the original data in N . Moreover, like the fundamental bound in CS, our requisite M is linear in the "information level" K and logarithmic in the ambient dimension N; we also identify a logarithmic dependence on the volume and conditioning of the manifold. In addition to recovering faithful approximations to manifold-modeled signals, however, the random projections we propose can also be used to discern key properties about the manifold. We discuss connections and contrasts with existing techniques in manifold learning, a setting where dimensionality reducing mappings are typically nonlinear and constructed adaptively from a set of sampled training data.

AB - We propose a new approach for nonadaptive dimensionality reduction of manifold-modeled data, demonstrating that a small number of random linear projections can preserve key information about a manifold-modeled signal. We center our analysis on the effect of a random linear projection operator Φ: N → M , M<N, on a smooth well-conditioned K-dimensional submanifold N . As our main theoretical contribution, we establish a sufficient number M of random projections to guarantee that, with high probability, all pairwise Euclidean and geodesic distances between points on are well preserved under the mapping Φ. Our results bear strong resemblance to the emerging theory of Compressed Sensing (CS), in which sparse signals can be recovered from small numbers of random linear measurements. As in CS, the random measurements we propose can be used to recover the original data in N . Moreover, like the fundamental bound in CS, our requisite M is linear in the "information level" K and logarithmic in the ambient dimension N; we also identify a logarithmic dependence on the volume and conditioning of the manifold. In addition to recovering faithful approximations to manifold-modeled signals, however, the random projections we propose can also be used to discern key properties about the manifold. We discuss connections and contrasts with existing techniques in manifold learning, a setting where dimensionality reducing mappings are typically nonlinear and constructed adaptively from a set of sampled training data.

KW - Compressed sensing

KW - Dimensionality reduction

KW - Johnson-Lindenstrauss lemma

KW - Manifold learning

KW - Manifolds

KW - Random projections

KW - Sparsity

UR - http://www.scopus.com/inward/record.url?scp=58849146227&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58849146227&partnerID=8YFLogxK

U2 - 10.1007/s10208-007-9011-z

DO - 10.1007/s10208-007-9011-z

M3 - Article

AN - SCOPUS:58849146227

SN - 1615-3375

VL - 9

SP - 51

EP - 77

JO - Foundations of Computational Mathematics

JF - Foundations of Computational Mathematics

IS - 1

ER -