TY - GEN

T1 - Near-isometric linear embeddings of manifolds

AU - Hegde, Chinmay

AU - Sankaranarayanan, Aswin C.

AU - Baraniuk, Richard G.

PY - 2012

Y1 - 2012

N2 - 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 (Q2) - 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. We numerically demonstrate the considerable gains using our SDP-based approach over existing linear dimensionality reduction methods, such as principal components analysis (PCA) and random projections.

AB - 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 (Q2) - 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. We numerically demonstrate the considerable gains using our SDP-based approach over existing linear dimensionality reduction methods, such as principal components analysis (PCA) and random projections.

KW - Adaptive sampling

KW - Linear Dimensionality Reduction

KW - Whitney's Theorem

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

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

U2 - 10.1109/SSP.2012.6319806

DO - 10.1109/SSP.2012.6319806

M3 - Conference contribution

AN - SCOPUS:84868225713

SN - 9781467301831

T3 - 2012 IEEE Statistical Signal Processing Workshop, SSP 2012

SP - 728

EP - 731

BT - 2012 IEEE Statistical Signal Processing Workshop, SSP 2012

T2 - 2012 IEEE Statistical Signal Processing Workshop, SSP 2012

Y2 - 5 August 2012 through 8 August 2012

ER -