New bounds for circulant Johnson-Lindenstrauss embeddings

DOI10.4310/CMS.2014.V12.N4.A5zbMATH Open1366.15031arXiv1308.6339MaRDI QIDQ471965FDOQ471965

Authors: Hui Zhang, Li-zhi Cheng 

Publication date: 18 November 2014

Published in: Communications in Mathematical Sciences (Search for Journal in Brave)

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(epsilo{n}^{-2}lo{g}^{(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.

Full work available at URL: https://arxiv.org/abs/1308.6339

Recommendations

• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• Johnson-Lindenstrauss lemma for circulant matrices
• Sparser Johnson-Lindenstrauss transforms
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Improved bounds for the RIP of subsampled circulant matrices

zbMATH Keywords

Laplace transformcirculant matrixdecoupling techniqueJohnson-Lindenstrauss embeddingmatrix-valued Bernstein inequality

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Cited In (7)

• On binary embedding using circulant matrices
• Fast binary embeddings with Gaussian circulant matrices: improved bounds
• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• Neural network approximation of continuous functions in high dimensions with applications to inverse problems
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• Johnson–Lindenstrauss Embeddings with Kronecker Structure
• Real-valued embeddings and sketches for fast distance and similarity estimation

This page was built for publication: New bounds for circulant Johnson-Lindenstrauss embeddings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q471965)