Communications in Mathematical Sciences

Volume 12 (2014)

Number 4

New bounds for circulant Johnson-Lindenstrauss embeddings

Pages: 695 – 705

DOI: https://dx.doi.org/10.4310/CMS.2014.v12.n4.a5

Authors

Lizhi Cheng (Department of Mathematics and Systems Science, College of Science, National University of Defense Technology, Changsha, Hunan, China)

Hui Zhang (Department of Mathematics and Systems Science, College of Science, National University of Defense Technology, Changsha, Hunan, China)

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 the 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.

Keywords

Johnson-Lindenstrauss embedding, circulant matrix, Laplace transform, decoupling technique, matrix-valued Bernstein inequality

2010 Mathematics Subject Classification

52Cxx, 68Q01

Published 7 February 2014