A variant of the Johnson-Lindenstrauss lemma for circulant matrices |
| |
| Authors: | Jan Vybí ral |
| |
| Affiliation: | Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenbergerstraße 69, A-4040 Linz, Austria |
| |
| Abstract: | 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=Ω(ε−2log3n) proven there to k=Ω(ε−2log2n). 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. |
| |
| Keywords: | Johnson-Lindenstrauss lemma Circulant matrix Discrete Fourier transform Singular value decomposition |
| 本文献已被 ScienceDirect 等数据库收录！ |
