A unified framework for linear dimensionality reduction in L1

DOI10.1007/s00025-015-0475-xzbMath1346.15036arXiv1405.1332OpenAlexW2964301151MaRDI QIDQ310869

Felix Krahmer, Rachel Ward

Publication date: 8 September 2016

Published in: Results in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

interpolation norm, random variablelinear dimensionality reduction

Mathematics Subject Classification ID

Probabilistic methods in Banach space theory (46B09) Random matrices (algebraic aspects) (15B52) Interpolation between normed linear spaces (46B70)

Related Items

Time for dithering: fast and quantized random embeddings via the restricted isometry property, Real-valued embeddings and sketches for fast distance and similarity estimation, Persistent homology for low-complexity models, Optimal fast Johnson-Lindenstrauss embeddings for large data sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• A mathematical introduction to compressive sensing
• Compressed sensing with coherent and redundant dictionaries
• A simple proof of the restricted isometry property for random matrices
• Tutorial on large deviations for the binomial distribution
• Smallest singular value of random matrices and geometry of random polytopes
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• One-Bit Compressed Sensing by Linear Programming
• Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation
• Randomized algorithms for the low-rank approximation of matrices
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Tight embedding of subspaces of 𝐿_{𝑝} in ℓ_{𝑝}ⁿ for even 𝑝
• Extensions of Lipschitz mappings into a Hilbert space
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• The Distribution of Rademacher Sums
• The best constants in the Khintchine inequality
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Compressed Sensing With Cross Validation
• New Bounds for Restricted Isometry Constants
• Probability and Computing
• Interpolation of Quasi-Normed Spaces.