Dimension reduction by random hyperplane tessellations

DOI10.1007/s00454-013-9561-6zbMath1296.52014arXiv1111.4452OpenAlexW1977601760MaRDI QIDQ2250053

Yaniv Plan, R. V. Vershinin

Publication date: 4 July 2014

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

embeddingdimension reductionmean widthhyperplane tessellationsnear isometry

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Related Items

Binary vectors for fast distance and similarity estimation, Sharp Estimates on Random Hyperplane Tessellations, Sparse recovery from inaccurate saturated measurements, Quantization and Compressive Sensing, Phase retrieval by binary questions: which complementary subspace is closer?, Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements, The Stolarsky principle and energy optimization on the sphere, Robust sensing of low-rank matrices with non-orthogonal sparse decomposition, Sigma Delta Quantization for Images, A theory of capacity and sparse neural encoding, A unified approach to uniform signal recovery from nonlinear observations, \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\), Fast Metric Embedding into the Hamming Cube, Sparse recovery from saturated measurements, Representation and coding of signal geometry, Time for dithering: fast and quantized random embeddings via the restricted isometry property, One-bit sensing, discrepancy and Stolarsky's principle, Quantized Compressed Sensing: A Survey, Classification Scheme for Binary Data with Extensions, Real-valued embeddings and sketches for fast distance and similarity estimation, Fast binary embeddings with Gaussian circulant matrices: improved bounds, On recovery guarantees for one-bit compressed sensing on manifolds, The stochastic geometry of unconstrained one-bit data compression, Estimation in High Dimensions: A Geometric Perspective, Non-Gaussian hyperplane tessellations and robust one-bit compressed sensing, Simple Classification using Binary Data, Thin-shell concentration for zero cells of stationary Poisson mosaics, Endpoint Results for Fourier Integral Operators on Noncompact Symmetric Spaces, On the Atomic Decomposition of Coorbit Spaces with Non-integrable Kernel, One-bit compressed sensing via ℓ _p (0 < p < 1)-minimization method, Adaptive iterative hard thresholding for least absolute deviation problems with sparsity constraints, Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors, A Theoretical Perspective on Hyperdimensional Computing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Two observations regarding embedding subsets of Euclidean spaces in normed spaces
• Empirical processes and random projections
• One-Bit Compressed Sensing by Linear Programming
• Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
• Extensions of Lipschitz mappings into a Hilbert space
• Sampling from large matrices
• Similarity estimation techniques from rounding algorithms
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• The Generic Chaining
• The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
• Universal Rate-Efficient Scalar Quantization
• On the Euclidean Metric Entropy of Convex Bodies