Near-isometric linear embeddings of manifolds

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 languageEnglish (US)
    Title of host publication2012 IEEE Statistical Signal Processing Workshop, SSP 2012
    Pages728-731
    Number of pages4
    DOIs
    StatePublished - 2012
    Event2012 IEEE Statistical Signal Processing Workshop, SSP 2012 - Ann Arbor, MI, United States
    Duration: Aug 5 2012Aug 8 2012

    Publication series

    Name2012 IEEE Statistical Signal Processing Workshop, SSP 2012

    Other

    Other2012 IEEE Statistical Signal Processing Workshop, SSP 2012
    CountryUnited States
    CityAnn Arbor, MI
    Period8/5/128/8/12

    Keywords

    • Adaptive sampling
    • Linear Dimensionality Reduction
    • Whitney's Theorem

    ASJC Scopus subject areas

    • Signal Processing

    Fingerprint Dive into the research topics of 'Near-isometric linear embeddings of manifolds'. Together they form a unique fingerprint.

  • Cite this

    Hegde, C., Sankaranarayanan, A. C., & Baraniuk, R. G. (2012). Near-isometric linear embeddings of manifolds. In 2012 IEEE Statistical Signal Processing Workshop, SSP 2012 (pp. 728-731). [6319806] (2012 IEEE Statistical Signal Processing Workshop, SSP 2012). https://doi.org/10.1109/SSP.2012.6319806