Nearly optimal linear embeddings into very low dimensions

Elyot Grant, Chinmay Hegde, Piotr Indyk

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

    Abstract

    We propose algorithms for constructing linear embeddings of a finite dataset V ⊂ rd into a k-dimensional subspace with provable, nearly optimal distortions. First, we propose an exhaustive-search-based algorithm that yields a k-dimensional linear embedding with distortion at most εopt(k)+δ, for any δ > 0 where εopt(k) is the smallest achievable distortion over all possible orthonormal embeddings. This algorithm is space-efficient and can be achieved by a single pass over the data V. However, the runtime of this algorithm is exponential in k. Second, we propose a convex-programming-based algorithm that yields an O(k/δ)-dimensional orthonormal embedding with distortion at most (1 + δ)εopt(k). The runtime of this algorithm is polynomial in d and independent of k. Several experiments demonstrate the benefits of our approach over conventional linear embedding techniques, such as principal components analysis (PCA) or random projections.

    Original languageEnglish (US)
    Title of host publication2013 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2013 - Proceedings
    Pages973-976
    Number of pages4
    DOIs
    StatePublished - 2013
    Event2013 1st IEEE Global Conference on Signal and Information Processing, GlobalSIP 2013 - Austin, TX, United States
    Duration: Dec 3 2013Dec 5 2013

    Publication series

    Name2013 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2013 - Proceedings

    Other

    Other2013 1st IEEE Global Conference on Signal and Information Processing, GlobalSIP 2013
    CountryUnited States
    CityAustin, TX
    Period12/3/1312/5/13

    ASJC Scopus subject areas

    • Information Systems
    • Signal Processing

    Fingerprint Dive into the research topics of 'Nearly optimal linear embeddings into very low dimensions'. Together they form a unique fingerprint.

    Cite this