A variant of the Johnson–Lindenstrauss lemma for circulant matrices

We continue our study of the Johnson–Lindenstrauss lemma and its connection to circulant matrices started in Hinrichs and Vybíral (in press) [7]. We reduce the bound on k from k = Ω(ε −2 log3 n) proven there to k = Ω(ε −2 log2 n). Our technique differs essentially from the one used in Hinrichs and Vybíral (in press) [7]. We employ the discrete Fourier transform and singular value decomposition to deal with the dependency caused by the circulant structure. © 2010 Elsevier Inc. All rights reserved