Nearly optimal linear embeddings into very low dimensions

We propose algorithms for constructing linear embeddings of a finite dataset V ⊂ ℝ[superscript d] 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 ε[subscript opt](k)+δ, for any δ > 0 where ε[subscript 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 + δ)ε[subscript 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.National Science Foundation (U.S.)Natural Sciences and Engineering Research Council of CanadaCenter for Massive Data Algorithmics (MADALGO)David & Lucile Packard FoundationMITEI-Shell Progra