Sparser Johnson-Lindenstrauss Transforms

被引：157

作者：

Kane, Daniel M. ^{[1
]}

Nelson, Jelani ^{[2
]}

机构：

[1] Stanford Univ, Dept Math, Stanford, CA 94305 USA

[2] Harvard Univ, Sch Engn & Appl Sci, Cambridge, MA 02138 USA

来源：

JOURNAL OF THE ACM | 2014年 / 61卷 / 01期

基金：

新加坡国家研究基金会;

关键词：

Algorithms; Theory; Dimensionality reduction; Johnson-Lindenstrauss; numerical linear algebra; streaming algorithms; MATRICES; LEMMA;

D O I：

10.1145/2559902

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We give two different and simple constructions for dimensionality reduction in l(2) via linear mappings that are sparse: only an O(epsilon)- fraction of entries in each column of our embedding matrices are non-zero to achieve distortion 1+epsilon with high probability, while still achieving the asymptotically optimal number of rows. These are the first constructions to provide subconstant sparsity for all values of parameters, improving upon previous works of Achlioptas [2003] and Dasgupta et al. [2010]. Such distributions can be used to speed up applications where l(2) dimensionality reduction is used.

引用

页数：23

共 40 条

[21] Algorithmic applications of low-distortion geometric embeddings [J].

Indyk, P .

42ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2001, :10-33

[22] Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error [J].

Jayram, T. S. ;

Woodruff, David P. .

ACM TRANSACTIONS ON ALGORITHMS, 2013, 9 (03)

[23]

Johnson William B, 1984, C MODERN ANAL PROBAB

[24]

Kane Daniel, 2011, Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques. Proceedings 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, P628, DOI 10.1007/978-3-642-22935-0_53

[25]

KANE D, 2010, DERANDOMIZED SPARSE

[26]

Kane D. M., 2012, SODA, P1195, DOI DOI 10.1137/1.9781611973099.94

[27]

Kane DM, 2011, ACM S THEORY COMPUT, P745

[28] Derandomized Constructions of k-Wise (Almost) Independent Permutations [J].