A variant of the Johnson-Lindenstrauss lemma for circulant matrices

DOI10.1016/J.JFA.2010.11.014zbMATH Open1220.46015arXiv1002.2847OpenAlexW2962683872WikidataQ124802332 ScholiaQ124802332MaRDI QIDQ629700FDOQ629700

Authors: Jan Vybíral 

Publication date: 9 March 2011

Published in: Journal of Functional Analysis (Search for Journal in Brave)

Abstract: 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(epsilo{n}^{-2}lo{g}^{3}n)$ proven there to $k=O(epsilo{n}^{-2}lo{g}^{2}n)$. 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.

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

Recommendations

• Johnson-Lindenstrauss lemma for circulant matrices
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• Sparser Johnson-Lindenstrauss transforms
• New bounds for circulant Johnson-Lindenstrauss embeddings
• Fast, deterministic and sparse dimensionality reduction
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• On variants of the Johnson–Lindenstrauss lemma
• Fast dimension reduction using Rademacher series on dual BCH codes
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• scientific article; zbMATH DE number 2119731

zbMATH Keywords

singular value decompositioncirculant matrixdiscrete Fourier transformJohnson-Lindenstrauss lemma

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (probabilistic aspects) (60B20) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85)

Cites Work

• Extensions of Lipschitz mappings into a Hilbert space
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Fast dimension reduction using Rademacher series on dual BCH codes
• Adaptive estimation of a quadratic functional by model selection.
• Title not available (Why is that?)
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• On variants of the Johnson–Lindenstrauss lemma
• Restricted isometries for partial random circulant matrices
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Johnson-Lindenstrauss lemma for circulant matrices
• An almost optimal unrestricted fast Johnson-Lindenstrauss transform

Cited In (14)

• On variants of the Johnson–Lindenstrauss lemma
• Sparser Johnson-Lindenstrauss transforms
• On binary embedding using circulant matrices
• Fast Metric Embedding into the Hamming Cube
• Restricted isometries for partial random circulant matrices
• New bounds for circulant Johnson-Lindenstrauss embeddings
• Robustness properties of dimensionality reduction with Gaussian random matrices
• On circulant thin Lehman matrices
• Johnson–Lindenstrauss Embeddings with Kronecker Structure
• Real-valued embeddings and sketches for fast distance and similarity estimation
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• Suprema of chaos processes and the restricted isometry property
• Johnson-Lindenstrauss lemma for circulant matrices

This page was built for publication: A variant of the Johnson-Lindenstrauss lemma for circulant matrices

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