Premium
Johnson‐Lindenstrauss lemma for circulant matrices* *
Author(s) -
Hinrichs Aicke,
Vybíral Jan
Publication year - 2011
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20360
Subject(s) - circulant matrix , lemma (botany) , randomness , dimension (graph theory) , mathematics , combinatorics , space (punctuation) , discrete mathematics , computer science , statistics , ecology , poaceae , biology , operating system
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 log 3 n ) instead of the classical bound k = O (ε −2 log n ). © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011