Toward a unified theory of sparse dimensionality reduction in Euclidean space
From MaRDI portal
Publication:496171
DOI10.1007/s00039-015-0332-9zbMath1341.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)
Full work available at URL: https://arxiv.org/abs/1311.2542
random matricesnumerical linear algebradimensionality reductionsparsitymanifold learningcompressed sensingconstrained least squares programssparse Johnson-Lindenstrauss transformrandomized linear algebra
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)
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
Cites Work
- 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
- 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
This page was built for publication: Toward a unified theory of sparse dimensionality reduction in Euclidean space
