A variant of the Johnson-Lindenstrauss lemma for circulant matrices

By Jan Vyb'iral. 2010

64 citations recorded by the source corpus.

We continue our study of the Johnson-Lindenstrauss lemma and its connection to circulant matrices started in \cite{HV}. We reduce the bound on $k$ from $k=O(\epsilon^{-2}\log^3n)$ proven there to $k=O(\epsilon^{-2}\log^2n)$. Our technique differs essentially from the one used in \cite{HV}. We employ the discrete Fourier transform and singular value decomposition to deal with the dependency caused by the circulant structure.

Subfields: Computer Vision and Pattern Recognition, Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/9da848e8e3893afc33417803cf2629cc8617df39

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Discrete Mathematics and Combinatorics

In Electrical and Electronic Engineering

Citations in the corpus

The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings (2017, background): “All these works, and other earlier approaches (Hinrichs and Vybíral, 2011; Vybíral, 2011; Zhang and Cheng, 2013; Le et al., 2013; Choromanska et al., 2016), provided computational beneﬁts by using structured matrices with less randomness than unstructured iid Gaussian matrices, but none…”
Initialization matters: Orthogonal Predictive State Recurrent Neural Networks (2018, background): “Several other structured constructions were known before (Ailon & Chazelle, 2006; Hinrichs & Vybı́ral, 2011; Vybı́ral, 2011; Zhang & Cheng, 2013; Choromanski & Sindhwani, 2016; Choromanska et al., 2016; Bojarski et al., 2017), however these were motivated by computational and space complexity gains…”
Fast locality-sensitive hashing (2011, methodology): “Concurrently and independently of our work, Vybiral [31] obtained a version of the Johnson–Lindenstrauss theorem using circulant matrices and Gaussian random variables.”
New and Improved Johnson-Lindenstrauss Embeddings via the Restricted Isometry Property (2010, unknown): “For large p, this is an improvement compared to [39].”
An Exploration of Parameter Redundancy in Deep Networks with Circulant Projections (2015, methodology): “resulted projections are less correlated [16, 41].”
OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings (2012, background): “There have been two popular lines of work in this area: one focusing on fast embeddings for all vectors [2]–[4], [19], [24], [25], [37], and one focusing on fast embeddings specifically for sparse vectors [1], [6], [13], [21], [22].”