New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property

DOI10.1137/100810447zbMATH Open1247.15019arXiv1009.0744OpenAlexW2963262327MaRDI QIDQ3097486FDOQ3097486

Rachel Ward, Felix Krahmer

Publication date: 10 November 2011

Published in: SIAM Journal on Mathematical Analysis (Search for Journal in Brave)

Abstract: Consider an m by N matrix Phi with the Restricted Isometry Property of order k and level delta, that is, the norm of any k-sparse vector in R^N is preserved to within a multiplicative factor of 1 +- delta under application of Phi. We show that by randomizing the column signs of such a matrix Phi, the resulting map with high probability embeds any fixed set of p = O(e^k) points in R^N into R^m without distorting the norm of any point in the set by more than a factor of 1 +- delta. Consequently, matrices with the Restricted Isometry Property and with randomized column signs provide optimal Johnson-Lindenstrauss embeddings up to logarithmic factors in N. In particular, our results improve the best known bounds on the necessary embedding dimension m for a wide class of structured random matrices; for partial Fourier and partial Hadamard matrices, we improve the recent bound m = O(delta^(-4) log(p) log^4(N)) appearing in Ailon and Liberty to m = O(delta^(-2) log(p) log^4(N)), which is optimal up to the logarithmic factors in N. Our results also have a direct application in the area of compressed sensing for redundant dictionaries.

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

Recommendations

• New constructions of RIP matrices with fast multiplication and fewer rows
• Fast and RIP-optimal transforms
• Sparsity lower bounds for dimensionality reducing maps
• Sparser Johnson-Lindenstrauss transforms
• Rigorous restricted isometry property of low-dimensional subspaces
• Johnson–Lindenstrauss Embeddings with Kronecker Structure
• Isometric sketching of any set via the restricted isometry property
• Lower bounds on the low-distortion embedding dimension of submanifolds of \(\mathbb{R}^n\)
• Restricted isometry property for random matrices with heavy-tailed columns
• Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument

zbMATH Keywords

Rademacher chaosrestricted isometry propertyJohnson-Lindenstrauss lemmapartial Hadamard matricesoptimal asymptoticspartial Fourier matrices

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (algebraic aspects) (15B52) Boolean and Hadamard matrices (15B34) Miscellaneous inequalities involving matrices (15A45)

Cited In (82)

• Rendition: Reclaiming What a Black Box Takes Away
• \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\)
• On fast Johnson-Lindenstrauss embeddings of compact submanifolds of \(\mathbb{R}^N\) with boundary
• Fast deflation sparse principal component analysis via subspace projections
• Fast Metric Embedding into the Hamming Cube
• Classification Scheme for Binary Data with Extensions
• Compressed data separation via \(\ell_q\)-split analysis with \(\ell_\infty\)-constraint
• Simple Analyses of the Sparse Johnson-Lindenstrauss Transform.
• Compressed data separation via unconstrained l1-split analysis
• Simple Classification using Binary Data
• Johnson–Lindenstrauss Embeddings with Kronecker Structure
• Side effects of learning from low-dimensional data embedded in a Euclidean space
• Convergence on thresholding-based algorithms for dictionary-sparse recovery
• Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024
• Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
• Compressive Sensing
• On orthogonal projections for dimension reduction and applications in augmented target loss functions for learning problems
• Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery
• GenMod: a generative modeling approach for spectral representation of PDEs with random inputs
• A Survey of Compressed Sensing
• Fast binary embeddings with Gaussian circulant matrices: improved bounds
• Convergence analysis of projected gradient descent for Schatten-\(p\) nonconvex matrix recovery
• Signal separation under coherent dictionaries and \(\ell_p\)-bounded noise
• Compressed dictionary learning
• On principal components regression, random projections, and column subsampling
• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• Randomized numerical linear algebra: Foundations and algorithms
• On the Atomic Decomposition of Coorbit Spaces with Non-integrable Kernel
• The Hanson-Wright inequality for random tensors
• Fast Phase Retrieval from Local Correlation Measurements
• A Novel Compressed Sensing Scheme for Photoacoustic Tomography
• Compressive Sensing with Redundant Dictionaries and Structured Measurements
• Persistent homology for low-complexity models
• Generalized notions of sparsity and restricted isometry property. II: Applications
• On deterministic sketching and streaming for sparse recovery and norm estimation
• Derandomizing restricted isometries via the Legendre symbol
• Theory and applications of compressed sensing
• Fast and RIP-optimal transforms
• Spectral estimation from simulations via sketching
• Sparser Johnson-Lindenstrauss Transforms
• Sparse Model Uncertainties in Compressed Sensing with Application to Convolutions and Sporadic Communication
• Tighter Fourier Transform Lower Bounds
• Greedy-like algorithms for the cosparse analysis model
• Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO
• On randomized trace estimates for indefinite matrices with an application to determinants
• Minimization of the difference of Nuclear and Frobenius norms for noisy low rank matrix recovery
• Convergence of projected Landweber iteration for matrix rank minimization
• Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames
• A unified framework for linear dimensionality reduction in L1
• Dimensionality-reduced subspace clustering
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
• Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs
• Compressed sensing with coherent and redundant dictionaries
• Low rank tensor recovery via iterative hard thresholding
• A strong restricted isometry property, with an application to phaseless compressed sensing
• On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms
• Title not available (Why is that?)
• Restricted isometries for partial random circulant matrices
• Sparse reconstruction with multiple Walsh matrices
• The restricted isometry property for random block diagonal matrices
• The Quest for Optimal Sampling: Computationally Efficient, Structure-Exploiting Measurements for Compressed Sensing
• Title not available (Why is that?)
• Quantization and Compressive Sensing
• Robustness properties of dimensionality reduction with Gaussian random matrices
• Near-optimal encoding for sigma-delta quantization of finite frame expansions
• Optimal fast Johnson-Lindenstrauss embeddings for large data sets
• Dimensionality reduction for \(k\)-distance applied to persistent homology
• Dictionary-sparse recovery via thresholding-based algorithms
• Enhanced total variation minimization for stable image reconstruction
• Toward a unified theory of sparse dimensionality reduction in Euclidean space
• Compressed sensing of low-rank plus sparse matrices
• An investigation of Newton-Sketch and subsampled Newton methods
• Iterative hard thresholding for compressed data separation
• Lower bounds on the low-distortion embedding dimension of submanifolds of \(\mathbb{R}^n\)
• Improved bounds for sparse recovery from subsampled random convolutions
• Real-valued embeddings and sketches for fast distance and similarity estimation
• Title not available (Why is that?)
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• Suprema of chaos processes and the restricted isometry property
• The Restricted Isometry Property of Subsampled Fourier Matrices
• Kernel conjugate gradient methods with random projections
• Fast and memory-optimal dimension reduction using Kac's walk

This page was built for publication: New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property

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