Near-isometric linear embeddings of manifolds

Chinmay Hegde; Aswin C. Sankaranarayanan; Richard G. Baraniuk

doi:10.1109/SSP.2012.6319806

Near-isometric linear embeddings of manifolds

Chinmay Hegde, Aswin C. Sankaranarayanan, Richard G. Baraniuk

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	2012 IEEE Statistical Signal Processing Workshop, SSP 2012
Pages	728-731
Number of pages	4
DOIs	https://doi.org/10.1109/SSP.2012.6319806
State	Published - 2012
Event	2012 IEEE Statistical Signal Processing Workshop, SSP 2012 - Ann Arbor, MI, United States Duration: Aug 5 2012 → Aug 8 2012

Publication series

Name	2012 IEEE Statistical Signal Processing Workshop, SSP 2012

Other

Other	2012 IEEE Statistical Signal Processing Workshop, SSP 2012
Country/Territory	United States
City	Ann Arbor, MI
Period	8/5/12 → 8/8/12

Keywords

Adaptive sampling
Linear Dimensionality Reduction
Whitney's Theorem

ASJC Scopus subject areas

Signal Processing

Access to Document

10.1109/SSP.2012.6319806

Cite this

Hegde, C, Sankaranarayanan, AC & Baraniuk, RG 2012, Near-isometric linear embeddings of manifolds. in 2012 IEEE Statistical Signal Processing Workshop, SSP 2012., 6319806, 2012 IEEE Statistical Signal Processing Workshop, SSP 2012, pp. 728-731, 2012 IEEE Statistical Signal Processing Workshop, SSP 2012, Ann Arbor, MI, United States, 8/5/12. https://doi.org/10.1109/SSP.2012.6319806

@inproceedings{8e7a315eb6a14edbbdf1c3eee27faaae,

title = "Near-isometric linear embeddings of manifolds",

abstract = "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.",

keywords = "Adaptive sampling, Linear Dimensionality Reduction, Whitney's Theorem",

author = "Chinmay Hegde and Sankaranarayanan, {Aswin C.} and Baraniuk, {Richard G.}",

year = "2012",

doi = "10.1109/SSP.2012.6319806",

language = "English (US)",

isbn = "9781467301831",

series = "2012 IEEE Statistical Signal Processing Workshop, SSP 2012",

pages = "728--731",

booktitle = "2012 IEEE Statistical Signal Processing Workshop, SSP 2012",

}

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 -

Near-isometric linear embeddings of manifolds

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this