This is an announcement for the paper "New bounds for circulant Johnson-Lindenstrauss embeddings" by Hui Zhang and Lizhi Cheng.

Abstract: This paper analyzes circulant Johnson-Lindenstrauss (JL) embeddings which, as an important class of structured random JL embeddings, are formed by randomizing the column signs of a circulant matrix generated by a random vector. With the help of recent decoupling techniques and matrix-valued Bernstein inequalities, we obtain a new bound $k=O(\epsilon^{-2}\log^{(1+\delta)} (n))$ for Gaussian circulant JL embeddings. Moreover, by using the Laplace transform technique (also called Bernstein's trick), we extend the result to subgaussian case. The bounds in this paper offer a small improvement over the current best bounds for Gaussian circulant JL embeddings for certain parameter regimes and are derived using more direct methods.

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

Remarks: 11 pages; accepted by Communications in Mathematical Sciences

Submitted from: h.zhang1984@163.com

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

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

or

http://arXiv.org/abs/1308.6339