Engineering Commons^™

Near-Isometric Linear Embeddings Of Manifolds, Chinmay Hegde, Aswin C. Sankaranarayanan, Richard G. Baraniuk

Chinmay Hegde

We propose a new method for linear dimensionality reduction of manifold-modeled data. Given a training set X of Q points belonging to a manifold M ⊂ ℝ^N, we construct a linear operator P : ℝ^N → ℝ^M that approximately preserves the norms of all (2^Q) pairwise difference vectors (or secants) of X. We design the matrix P via a trace-norm minimization that can be efficiently solved as a semi-definite program (SDP). When X comprises a sufficiently dense sampling of M, we prove that the optimal matrix P preserves all pairs of secants over M. …