×

Johnson-Lindenstrauss lemma for circulant matrices. (English) Zbl 1230.46019

All known proofs of the Johnson-Lindenstrauss lemma [W. B. Johnson and J. Lindenstrauss, Contemp. Math. 26, 189–206 (1984; Zbl 0539.46017)] use random matrices. Since the lemma is used in numerous algorithms, it is important to find proofs of the lemma for which the corresponding computations have relatively small running time and use relatively small amount of random bits. An important achievement of this type is due to Nir Ailon and B. Chazelle [SIAM J. Comput. 39, No. 1, 302–322 (2009; Zbl 1185.68327)]. See J. Matoušek [Random Struct. Algorithms 33, No. 2, 142–156 (2008; Zbl 1154.51002)] for improvements and a description of the history of this topic.
The present paper is devoted to the proof of a variant of the Johnson-Lindenstrauss lemma with random matrix given as a composition of a random partial circulant matrix with a random diagonal matrix. This approach allows the authors to minimize the randomness used and provides good running times, the disadvantage of this approach is that it has worse than the optimal (logarithmic) bound on the target space, namely, the bound is \(O(\varepsilon^{-2}\log^3 n)\).
Reviewer’s remark: This bound was improved and this approach was further developed in J. Vybíral [J. Funct. Anal. 260, No. 4, 1096–1105 (2011; Zbl 1220.46015)].

MSC:

46B85 Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science
15B52 Random matrices (algebraic aspects)
60B20 Random matrices (probabilistic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Achlioptas, Database-friendly random projections: Johnson-Lindenstrauss with binary coins, J Comput Syst Sci 66 pp 671– (2003) · Zbl 1054.68040 · doi:10.1016/S0022-0000(03)00025-4
[2] N. Ailon B. Chazelle Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform 2006 · Zbl 1301.68232
[3] Ailon, The fast Johnson-Lindenstrauss transform and approximate nearest neighbors, SIAM J Comput 39 pp 302– (2009) · Zbl 1185.68327 · doi:10.1137/060673096
[4] N. Ailon E. Liberty http://arxiv.org/abs/1005.5513 2010
[5] W. Bajwa J. Haupt G. Raz S. Wright R. Nowak Toeplitz-structured compressed sensing matrices IEEE Workshop SSP Madison Wisconsin 2007
[6] W. U. Bajwa J. Haupt G. Raz R. Nowak Compressed channel sensing 2008
[7] Bourgain, Invertibility of large submatrices with applications to the geometry of Banach spaces and harmonic analysis, Israel J Math 57 pp 137– (1987) · Zbl 0631.46017 · doi:10.1007/BF02772174
[8] Dasgupta, An elementary proof of a theorem of Johnson and Lindenstrauss, Random Struct Algorithms 22 pp 60– (2003) · Zbl 1018.51010 · doi:10.1002/rsa.10073
[9] Golub, Matrix computations (1996)
[10] Haagerup, The best constants in the Khintchine inequality, Studia Math 70 pp 231– (1982) · Zbl 0501.46015
[11] Hanson, A bound on tail probabilities for quadratic forms in independent random variables, Ann Math Statist 42 pp 1079– (1971) · Zbl 0216.22203 · doi:10.1214/aoms/1177693335
[12] P. Indyk R. Motwani Approximate nearest neighbors: Towards removing the curse of dimensionality 1998 604 613 · Zbl 1029.68541
[13] Indyk, Nearest neighbor preserving embeddings, ACM Trans Algorithms 3 (2007) · Zbl 1192.68748 · doi:10.1145/1273340.1273347
[14] Johnson, Extensions of Lipschitz mappings into a Hilbert space, Contem Math 26 pp 189– (1984) · Zbl 0539.46017 · doi:10.1090/conm/026/737400
[15] Latała, Estimates of moments and tails of Gaussian chaoses, Ann Prob 34 pp 2315– (2006) · Zbl 1119.60015 · doi:10.1214/009117906000000421
[16] Laurent, Adaptive estimation of a quadratic functional by model selection, Ann Statist 28 pp 1302– (2000) · Zbl 1105.62328
[17] Matoušek, On variants of the Johnson-Lindenstrauss lemma, Random Struct Algorithms 33 pp 142– (2008) · Zbl 1154.51002 · doi:10.1002/rsa.20218
[18] H. Rauhut Circulant and Toeplitz matrices in compressed sensing 2009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.