A variant of the Johnson–Lindenstrauss lemma for circulant matrices

详细信息    查看全文

• 作者：Jan Vybí ; ral
• 关键词：Johnson– ; Lindenstrauss lemma ; Circulant matrix ; Discrete Fourier transform ; Singular value decomposition
• 刊名：Journal of Functional Analysis
• 出版年：2011
• 出版时间：28 February 2011
• 年：2011
• 卷：260
• 期：4
• 页码：1096-1105
• 全文大小：126 K

文摘

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=Ω(ε⁻²log³n) proven there to k=Ω(ε⁻²log²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.