Johnson‐Lindenstrauss lemma for circulant matrices** |
| |
| Authors: | Aicke Hinrichs Jan Vybíral |
| |
| Affiliation: | 1. Department of Mathematics, Universit?t Jena, 07740 Jena, Germany;2. Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, A‐4040 Linz, Austria |
| |
| Abstract: | We prove a variant of a Johnson‐Lindenstrauss lemma for matrices with circulant structure. This approach allows to minimize the randomness used, is easy to implement and provides good running times. The price to be paid is the higher dimension of the target space k = O(ε?2 log3 n) instead of the classical bound k = O(ε?2 log n). © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011 |
| |
| Keywords: | Johnson‐Lindenstrauss lemma circulant matrices decoupling lemma |
|
|
