A variant of the Johnson-Lindenstrauss lemma for circulant matrices. (English) Zbl 1220.46015
The well-known Johnson-Lindenstrauss lemma [W. B. Johnson and J. Lindenstrauss, Contemp. Math. 26, 189–206 (1984; Zbl 0539.46017)] is used in numerous computer science applications. In this connection, it becomes important to find proofs of the lemma for which the corresponding computations have relatively small running time. Also, all existing proofs of the Johnson-Lindenstrauss lemma use random matrices. For applications, it is useful to find constructions of such matrices which use a (relatively) small amount of random bits. An important achievement of this type is due to N. 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 circulant matrix with a random diagonal matrix. This type of random matrices was first used for the Johnson-Lindenstrauss lemma in the paper by A. Hinrichs and J. Vybíral [“Johnson-Lindenstrauss lemma for circulant matrices”, Preprint (2010; arXiv:1001.4919)].
So far, on these lines the optimal (logarithmic) bound on the target space has not been reached. The present paper contains an improvement (\(k=\Omega(\varepsilon^{-2}\log^2 n)\)) of the bound reached by A. Hinrichs and J. Vybíral [op.cit] and a different proof. The proof in the paper under review is based on the discrete Fourier transform and the singular value decomposition of circulant matrices.
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 circulant matrix with a random diagonal matrix. This type of random matrices was first used for the Johnson-Lindenstrauss lemma in the paper by A. Hinrichs and J. Vybíral [“Johnson-Lindenstrauss lemma for circulant matrices”, Preprint (2010; arXiv:1001.4919)].
So far, on these lines the optimal (logarithmic) bound on the target space has not been reached. The present paper contains an improvement (\(k=\Omega(\varepsilon^{-2}\log^2 n)\)) of the bound reached by A. Hinrichs and J. Vybíral [op.cit] and a different proof. The proof in the paper under review is based on the discrete Fourier transform and the singular value decomposition of circulant matrices.
Reviewer: Mikhail Ostrovskii (Queens)
MSC:
| 46B85 | Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 60B20 | Random matrices (probabilistic aspects) |
Keywords:
Johnson-Lindenstrauss lemma; circulant matrix; discrete Fourier transform; singular value decompositionReferences:
| [1] | Achlioptas, D., Database-friendly random projections: Johnson-Lindenstrauss with binary coins, J. Comput. System Sci., 66, 4, 671-687 (2003) · Zbl 1054.68040 |
| [2] | N. Ailon, B. Chazelle, Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform, in: Proc. 38th Annual ACM Symposium on Theory of Computing, 2006.; N. Ailon, B. Chazelle, Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform, in: Proc. 38th Annual ACM Symposium on Theory of Computing, 2006. · Zbl 1301.68232 |
| [3] | Ailon, N.; Chazelle, B., The fast Johnson-Lindenstrauss transform and approximate nearest neighbors, SIAM J. Comput., 39, 1, 302-322 (2009) · Zbl 1185.68327 |
| [4] | Ailon, N.; Liberty, E., Fast dimension reduction using Rademacher series on dual BCH codes, Discrete Comput. Geom., 42, 4, 615-630 (2009) · Zbl 1180.94083 |
| [5] | Ailon, N.; Liberty, E., Almost optimal unrestricted fast Johnson-Lindenstrauss transform · Zbl 1377.68259 |
| [6] | Dasgupta, S.; Gupta, A., An elementary proof of a theorem of Johnson and Lindenstrauss, Random Structures Algorithms, 22, 60-65 (2003) · Zbl 1018.51010 |
| [7] | A. Hinrichs, J. Vybíral, Johnson-Lindenstrauss lemma for circulant matrices, Random Structures Algorithms, in press.; A. Hinrichs, J. Vybíral, Johnson-Lindenstrauss lemma for circulant matrices, Random Structures Algorithms, in press. · Zbl 1230.46019 |
| [8] | P. Indyk, R. Motwani, Approximate nearest neighbors: Towards removing the curse of dimensionality, in: Proc. 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 604-613.; P. Indyk, R. Motwani, Approximate nearest neighbors: Towards removing the curse of dimensionality, in: Proc. 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 604-613. · Zbl 1029.68541 |
| [9] | Johnson, W. B.; Lindenstrauss, J., Extensions of Lipschitz Mappings into a Hilbert Space, Contemp. Math., vol. 26 (1984), pp. 189-206 · Zbl 0539.46017 |
| [10] | Krahmer, F.; Ward, R., New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property · Zbl 1247.15019 |
| [11] | Laurent, B.; Massart, P., Adaptive estimation of a quadratic functional by model selection, Ann. Statist., 28, 5, 1302-1338 (2000) · Zbl 1105.62328 |
| [12] | Matoušek, J., On variants of the Johnson-Lindenstrauss lemma, Random Structures Algorithms, 33, 2, 142-156 (2008) · Zbl 1154.51002 |
| [13] | Rauhut, H.; Romberg, J.; Tropp, J., Restricted isometries for partial random circulant matrices · Zbl 1245.15040 |
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.
