Random Projections of Smooth Manifolds
Random Projections of Smooth Manifolds
复制标题
DOI：
10.1007/s10208-007-9011-z
复制
发表时间：
2009-02-01
影响因子：
3
通讯作者：
Wakin, Michael B.
中科院分区：
文献类型：
--
作者：
Baraniuk, Richard G.;Wakin, Michael B.
提出了一种对流形建模数据进行非自适应降维的新方法，证明了少量的随机线性投影可以保留流形建模信号的关键信息。我们主要分析了随机线性投影算子Phi：R-N->；R-M，M<；N对R-N的光滑良好K维子流形M子集的影响。作为我们的主要理论贡献，我们建立了足够多的随机投影M，以保证在高概率下，M上的点之间的所有成对欧几里得和测地距离在映射Ph下保持良好。我们的结果与新兴的压缩感知(CS)理论有很大的相似之处，在CS理论中，稀疏信号可以从少量随机线性测量中恢复出来。与在CS中一样，我们提出的随机测量可以用于恢复R-N中的原始数据。此外，与CS中的基本界一样，我们的必要条件M在“信息水平”K中线性，在现有维度N中对数；我们还证明了对数依赖于流形的体积和条件。然而，除了恢复对流形建模信号的忠实近似之外，我们提出的随机投影还可以用于识别关于流形的关键属性。我们讨论了与流形学习中现有技术的联系和对比，流形学习是一种典型的非线性降维映射，并且从一组采样的训练数据自适应地构建。
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 Phi : R-N -> R-M, M < N, on a smooth well-conditioned K-dimensional submanifold M subset of R-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 M are well preserved under the mapping Phi.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 R-N. Moreover, like the fundamental bound in CS, our requisite M is linear in the "information level" K and logarithmic in the am-bient 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.