Random Projections of Smooth Manifolds

Authors: Richard G Baraniuk Michael B Wakin

Publish Date: 2007/12/18

Volume: 9, Issue: 1, Pages: 51-77

PDF Link

Abstract

We propose a new approach for nonadaptive dimensionality reduction of manifoldmodeled data demonstrating that a small number of random linear projections can preserve key information about a manifoldmodeled signal We center our analysis on the effect of a random linear projection operator Φℝ N →ℝ M MN on a smooth wellconditioned Kdimensional 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 manifoldmodeled 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 dataThis research was supported by ONR grants N000140610769 and N000140610829 AFOSR grant FA9550040148 DARPA grants N660010612011 and N000140610610 NSF grants CCF0431150 CNS0435425 CNS0520280 and DMS0603606 and the Texas Instruments Leadership University Program Web dspriceedu/cs

Keywords: