This is an announcement for the paper "Johnson-Lindenstrauss lemma for circulant matrices" by Aicke Hinrichs and Jan Vybiral.

Abstract: We prove a variant of a Johnson-Lindenstrauss lemma for matrices with circulant structure. This approach allows to minimise 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(\varepsilon^{-2}\log^3n)$ instead of the classical bound $k=O(\varepsilon^{-2}\log n)$.

Archive classification: math.FA cs.IT math.IT

Mathematics Subject Classification: 52C99; 68Q01

The source file(s), Hinrichs_Vybiral.tex: 18930 bytes, is(are) stored in gzipped form as 1001.4919.gz with size 7kb. The corresponding postcript file has gzipped size 84kb.

Submitted from: jan.vybiral@oeaw.ac.at

The paper may be downloaded from the archive by web browser from URL

http://front.math.ucdavis.edu/1001.4919

or

http://arXiv.org/abs/1001.4919

or by email in unzipped form by transmitting an empty message with subject line

uget 1001.4919

or in gzipped form by using subject line

get 1001.4919

to: math@arXiv.org.