Johnson-Lindenstrauss lemma for circulant matrices

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({\epsilon }^{-2}{\log }^{3}n)$ instead of the classical bound $k=O({\epsilon }^{-2}\log n)$.

References in corpus (1)

• Circulant and Toeplitz matrices in compressed sensing

Cited by in corpus (1)

• A Derandomized Sparse Johnson-Lindenstrauss Transform