A variant of the Johnson-Lindenstrauss lemma for circulant matrices (Q629700): Difference between revisions

The well-known Johnson-Lindenstrauss lemma [\textit{W. B. Johnson} and \textit{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 \textit{N. Ailon} and \textit{B. Chazelle} [SIAM J. Comput. 39, No. 1, 302--322 (2009; Zbl 1185.68327)]; see \textit{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 \textit{A. Hinrichs} and \textit{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 \textit{A. Hinrichs} and \textit{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.