Publication:496171

DOI10.1145/2746539.2746541zbMath1341.46007arXiv1311.2542OpenAlexW1500518989MaRDI QIDQ496171

Jean Bourgain, Sjoerd Dirksen, Jelani Nelson

Publication date: 21 September 2015

Published in: Geometric and Functional Analysis. GAFA, Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Abstract: Let $Phiinmathbb{R}^{m imes n}$ be a sparse Johnson-Lindenstrauss transform [KN14] with $s$ non-zeroes per column. For a subset $T$ of the unit sphere, $varepsilonin(0,1/2)$ given, we study settings for $m,s$ required to ensure $$ mathop{mathbb{E}}_Phi sup_{xin T} left||Phi x|_2^2 - 1 ight| < varepsilon , $$ i.e. so that $Phi$ preserves the norm of every $xin T$ simultaneously and multiplicatively up to $1+varepsilon$. We introduce a new complexity parameter, which depends on the geometry of $T$, and show that it suffices to choose $s$ and $m$ such that this parameter is small. Our result is a sparse analog of Gordon's theorem, which was concerned with a dense $Phi$ having i.i.d. Gaussian entries. We qualitatively unify several results related to the Johnson-Lindenstrauss lemma, subspace embeddings, and Fourier-based restricted isometries. Our work also implies new results in using the sparse Johnson-Lindenstrauss transform in numerical linear algebra, classical and model-based compressed sensing, manifold learning, and constrained least squares problems such as the Lasso.

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

zbMATH Keywords

random matricesnumerical linear algebradimensionality reductionsparsitymanifold learningcompressed sensingconstrained least squares programssparse Johnson-Lindenstrauss transformrandomized linear algebra

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Convex programming (90C25) Learning and adaptive systems in artificial intelligence (68T05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Local theory of Banach spaces (46B07) Random matrices (algebraic aspects) (15B52) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast, linear time hierarchical clustering using the Baire metric
• A mathematical introduction to compressive sensing
• Dimensionality reduction with subgaussian matrices: a unified theory
• Statistics for high-dimensional data. Methods, theory and applications.
• Explicit constructions of RIP matrices and related problems
• Iterative thresholding for sparse approximations
• Uniform recovery of fusion frame structured sparse signals
• Kernels as features: on kernels, margins, and low-dimensional mappings
• Subspaces and orthogonal decompositions generated by bounded orthogonal systems
• The restricted isometry property and its implications for compressed sensing
• Ramsey partitions and proximity data structures
• Majorizing measures and proportional subsets of bounded orthonormal systems
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Random projections of smooth manifolds
• Fast dimension reduction using Rademacher series on dual BCH codes
• Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
• Non commutative Khintchine and Paley inequalities
• On sparse spanners of weighted graphs
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Problems and results in extremal combinatorics. I.
• Approximation of zonoids by zonotopes
• Finding frequent items in data streams
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• New analysis of manifold embeddings and signal recovery from compressive measurements
• Reconstruction and subgaussian operators in asymptotic geometric analysis
• Tail bounds via generic chaining
• The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
• Empirical processes and random projections
• The Fast Cauchy Transform and Faster Robust Linear Regression
• A sparse Johnson
• Suprema of Chaos Processes and the Restricted Isometry Property
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• Efficient Dimensionality Reduction for Canonical Correlation Analysis
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Randomized Sketches of Convex Programs With Sharp Guarantees
• Randomized Dimensionality Reduction for <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Means Clustering
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Low-Rank Approximation and Regression in Input Sparsity Time
• Sparser Johnson-Lindenstrauss Transforms
• Extensions of Lipschitz mappings into a Hilbert space
• On sparse reconstruction from Fourier and Gaussian measurements
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• On variants of the Johnson–Lindenstrauss lemma
• Approximate distance oracles
• Sampling from large matrices
• Decoding by Linear Programming
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Low-distortion embeddings of general metrics into the line
• A Fast Random Sampling Algorithm for Sparsifying Matrices
• Tighter bounds for random projections of manifolds
• Subspaces of Small Codimension of Finite-Dimensional Banach Spaces
• On the moduli of convexity and smoothness
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• The Fourth Moment Method
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
• The Generic Chaining
• Numerical linear algebra in the streaming model
• Shortest-path queries in static networks
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Approximate distance oracles with constant query time
• Model-Based Compressive Sensing
• On Model-Based RIP-1 Matrices
• An Algorithm for the Machine Calculation of Complex Fourier Series
• New constructions of RIP matrices with fast multiplication and fewer rows
• Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
• The random paving property for uniformly bounded matrices
• Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data
• Learning Theory
• Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
• Sparsity lower bounds for dimensionality reducing maps
• Convex Analysis
• Automata, Languages and Programming
• Eigenvalues of a matrix in the streaming model
• Compressed sensing
• Graph Sparsification by Effective Resistances

Related Items (16)

Randomized numerical linear algebra: Foundations and algorithms ⋮ Fast Phase Retrieval from Local Correlation Measurements ⋮ Inverse problems on low-dimensional manifolds ⋮ Sharper Bounds for Regularized Data Fitting ⋮ Binary random projections with controllable sparsity patterns ⋮ Norms of structured random matrices ⋮ Practical Sketching Algorithms for Low-Rank Matrix Approximation ⋮ \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\) ⋮ Fast Metric Embedding into the Hamming Cube ⋮ Representation and coding of signal geometry ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Persistent homology for low-complexity models ⋮ Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation ⋮ Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization ⋮ Estimating Leverage Scores via Rank Revealing Methods and Randomization ⋮ Tensor-Structured Sketching for Constrained Least Squares

Uses Software

• CoSaMP
• Blendenpik
• Graphs

This page was built for publication: Toward a unified theory of sparse dimensionality reduction in Euclidean space