New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
From MaRDI portal
Publication:3097486
DOI10.1137/100810447zbMath1247.15019arXiv1009.0744OpenAlexW2963262327MaRDI QIDQ3097486
Publication date: 10 November 2011
Published in: SIAM Journal on Mathematical Analysis (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1009.0744
restricted isometry propertyRademacher chaosJohnson-Lindenstrauss lemmapartial Hadamard matricesoptimal asymptoticspartial Fourier matrices
Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Miscellaneous inequalities involving matrices (15A45) Random matrices (algebraic aspects) (15B52) Boolean and Hadamard matrices (15B34)
Related Items
Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery ⋮ On principal components regression, random projections, and column subsampling ⋮ Johnson–Lindenstrauss Embeddings with Kronecker Structure ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Compressed data separation via unconstrained l1-split analysis ⋮ Spectral estimation from simulations via sketching ⋮ Derandomizing restricted isometries via the Legendre symbol ⋮ Tighter Fourier Transform Lower Bounds ⋮ Structure dependent sampling in compressed sensing: theoretical guarantees for tight frames ⋮ Improved bounds for sparse recovery from subsampled random convolutions ⋮ A Novel Compressed Sensing Scheme for Photoacoustic Tomography ⋮ A unified framework for linear dimensionality reduction in L1 ⋮ Compressive Sensing with Redundant Dictionaries and Structured Measurements ⋮ Fast Phase Retrieval from Local Correlation Measurements ⋮ A Survey of Compressed Sensing ⋮ The Quest for Optimal Sampling: Computationally Efficient, Structure-Exploiting Measurements for Compressed Sensing ⋮ Quantization and Compressive Sensing ⋮ Sparse Model Uncertainties in Compressed Sensing with Application to Convolutions and Sporadic Communication ⋮ Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering ⋮ Sparser Johnson-Lindenstrauss Transforms ⋮ The Hanson-Wright inequality for random tensors ⋮ Unnamed Item ⋮ Suprema of Chaos Processes and the Restricted Isometry Property ⋮ Low rank tensor recovery via iterative hard thresholding ⋮ Generalized notions of sparsity and restricted isometry property. II: Applications ⋮ On randomized trace estimates for indefinite matrices with an application to determinants ⋮ Iterative hard thresholding for compressed data separation ⋮ Fast deflation sparse principal component analysis via subspace projections ⋮ Restricted isometries for partial random circulant matrices ⋮ \( \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 Metric Embedding into the Hamming Cube ⋮ Enhanced total variation minimization for stable image reconstruction ⋮ Side effects of learning from low-dimensional data embedded in a Euclidean space ⋮ A variant of the Johnson-Lindenstrauss lemma for circulant matrices ⋮ Compressed sensing of low-rank plus sparse matrices ⋮ Dimensionality-reduced subspace clustering ⋮ A strong restricted isometry property, with an application to phaseless compressed sensing ⋮ Robustness properties of dimensionality reduction with Gaussian random matrices ⋮ Compressive Sensing ⋮ Greedy-like algorithms for the cosparse analysis model ⋮ On deterministic sketching and streaming for sparse recovery and norm estimation ⋮ Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. ⋮ An investigation of Newton-Sketch and subsampled Newton methods ⋮ The restricted isometry property for random block diagonal matrices ⋮ Signal separation under coherent dictionaries and \(\ell_p\)-bounded noise ⋮ Classification Scheme for Binary Data with Extensions ⋮ Near-optimal encoding for sigma-delta quantization of finite frame expansions ⋮ Kernel conjugate gradient methods with random projections ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ On orthogonal projections for dimension reduction and applications in augmented target loss functions for learning problems ⋮ Fast binary embeddings with Gaussian circulant matrices: improved bounds ⋮ Persistent homology for low-complexity models ⋮ Convergence of projected Landweber iteration for matrix rank minimization ⋮ Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO ⋮ Compressed sensing with coherent and redundant dictionaries ⋮ Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs ⋮ Dictionary-sparse recovery via thresholding-based algorithms ⋮ Fast and RIP-optimal transforms ⋮ Convergence analysis of projected gradient descent for Schatten-\(p\) nonconvex matrix recovery ⋮ On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms ⋮ Simple Classification using Binary Data ⋮ Minimization of the difference of Nuclear and Frobenius norms for noisy low rank matrix recovery ⋮ Optimal fast Johnson-Lindenstrauss embeddings for large data sets ⋮ Compressed dictionary learning ⋮ Dimensionality reduction for \(k\)-distance applied to persistent homology ⋮ On the Atomic Decomposition of Coorbit Spaces with Non-integrable Kernel ⋮ Sparse reconstruction with multiple Walsh matrices ⋮ Rendition: Reclaiming What a Black Box Takes Away ⋮ Fast and memory-optimal dimension reduction using Kac's walk ⋮ Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares ⋮ The Restricted Isometry Property of Subsampled Fourier Matrices ⋮ Unnamed Item ⋮ GenMod: a generative modeling approach for spectral representation of PDEs with random inputs ⋮ Unnamed Item ⋮ Theory and applications of compressed sensing
This page was built for publication: New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
