A variant of the Johnson-Lindenstrauss lemma for circulant matrices
type: Item
instance of: scholarly article
title: A variant of the Johnson-Lindenstrauss lemma for circulant matrices
zbMATH Open document ID: 1220.46015
author: Jan Vybíral
published in: Journal of Functional Analysis
publication date: 2011-03-09T00:00:00Z
full work available at URL: https://arxiv.org/abs/1002.2847
review text: The well-known Johnson-Lindenstrauss lemma [\textit{W. B. Johnson} and \textit{J. Lindenstrauss}, Contemp. Math. 26, 189--206 (1984; Zbl 0539.46017)] is used in numerous computer science applications. In this connection, it becomes important to find proofs of the lemma for which the corresponding computations have relatively small running time. Also, all existing proofs of the Johnson-Lindenstrauss lemma use random matrices. For applications, it is useful to find constructions of such matrices which use a (relatively) small amount of random bits. An important achievement of this type is due to \textit{N. Ailon} and \textit{B. Chazelle} [SIAM J. Comput. 39, No. 1, 302--322 (2009; Zbl 1185.68327)]; see \textit{J. Matoušek} [Random Struct. Algorithms 33, No. 2, 142--156 (2008; Zbl 1154.51002)] for improvements and a description of the history of this topic. The present paper is devoted to the proof of a variant of the Johnson-Lindenstrauss lemma with random matrix given as a composition of a random circulant matrix with a random diagonal matrix. This type of random matrices was first used for the Johnson-Lindenstrauss lemma in the paper by \textit{A. Hinrichs} and \textit{J.~Vybíral} [``Johnson-Lindenstrauss lemma for circulant matrices'', Preprint (2010; arXiv:1001.4919)]. So far, on these lines the optimal (logarithmic) bound on the target space has not been reached. The present paper contains an improvement (\(k=\Omega(\varepsilon^{-2}\log^2 n)\)) of the bound reached by \textit{A. Hinrichs} and \textit{J.~Vybíral} [op.\,cit] and a different proof. The proof in the paper under review is based on the discrete Fourier transform and the singular value decomposition of circulant matrices.
Mathematics Subject Classification ID: 46B85
Mathematics Subject Classification ID: 15A18
Mathematics Subject Classification ID: 60B20
zbMATH DE Number: 5863604
zbMATH Keywords: Johnson-Lindenstrauss lemma
zbMATH Keywords: circulant matrix
zbMATH Keywords: discrete Fourier transform
zbMATH Keywords: singular value decomposition
reviewed by: Mikhail Ostrovskii
MaRDI profile type: Publication
OpenAlex ID: W2962683872
Wikidata QID: Q124802332
arXiv ID: 1002.2847
cites work: Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
cites work: Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
cites work: The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
cites work: Fast dimension reduction using Rademacher series on dual BCH codes
cites work: Q5365036
cites work: An elementary proof of a theorem of Johnson and Lindenstrauss
cites work: Johnson-Lindenstrauss lemma for circulant matrices**
cites work: Q4542583
cites work: Extensions of Lipschitz mappings into a Hilbert space
cites work: New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
cites work: Adaptive estimation of a quadratic functional by model selection.
cites work: On variants of the Johnson–Lindenstrauss lemma
cites work: Restricted isometries for partial random circulant matrices
DOI: 10.1016/J.JFA.2010.11.014
Recommended article: Johnson-Lindenstrauss lemma for circulant matrices**
Recommended article: Almost Optimal Explicit Johnson-Lindenstrauss Families
Recommended article: Q5743469
Recommended article: New bounds for circulant Johnson-Lindenstrauss embeddings
Recommended article: Q4607975
Recommended article: On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
Recommended article: On variants of the Johnson–Lindenstrauss lemma
Recommended article: Fast dimension reduction using Rademacher series on dual BCH codes
Recommended article: On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms
Recommended article: Q4829005
description: scientific article