TY - GEN

T1 - Nearly optimal linear embeddings into very low dimensions

AU - Grant, Elyot

AU - Hegde, Chinmay

AU - Indyk, Piotr

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

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

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

U2 - 10.1109/GlobalSIP.2013.6737055

DO - 10.1109/GlobalSIP.2013.6737055

M3 - Conference contribution

AN - SCOPUS:84897729824

SN - 9781479902484

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

SP - 973

EP - 976

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

T2 - 2013 1st IEEE Global Conference on Signal and Information Processing, GlobalSIP 2013

Y2 - 3 December 2013 through 5 December 2013

ER -