Time for dithering: fast and quantized random embeddings via the restricted isometry property
From MaRDI portal
Publication:4603715
Abstract: Recently, many works have focused on the characterization of non-linear dimensionality reduction methods obtained by quantizing linear embeddings, e.g., to reach fast processing time, efficient data compression procedures, novel geometry-preserving embeddings or to estimate the information/bits stored in this reduced data representation. In this work, we prove that many linear maps known to respect the restricted isometry property (RIP) can induce a quantized random embedding with controllable multiplicative and additive distortions with respect to the pairwise distances of the data points beings considered. In other words, linear matrices having fast matrix-vector multiplication algorithms (e.g., based on partial Fourier ensembles or on the adjacency matrix of unbalanced expanders) can be readily used in the definition of fast quantized embeddings with small distortions. This implication is made possible by applying right after the linear map an additive and random "dither" that stabilizes the impact of the uniform scalar quantization operator applied afterwards. For different categories of RIP matrices, i.e., for different linear embeddings of a metric space in with , we derive upper bounds on the additive distortion induced by quantization, showing that it decays either when the embedding dimension increases or when the distance of a pair of embedded vectors in decreases. Finally, we develop a novel "bi-dithered" quantization scheme, which allows for a reduced distortion that decreases when the embedding dimension grows and independently of the considered pair of vectors.
Recommendations
- New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
- Fast binary embeddings and quantized compressed sensing with structured matrices
- Fast binary embeddings with Gaussian circulant matrices: improved bounds
- Sparser Johnson-Lindenstrauss transforms
- Quantized compressive sensing with RIP matrices: the benefit of dithering
Cites work
- scientific article; zbMATH DE number 1313392 (Why is no real title available?)
- A Quantized Johnson–Lindenstrauss Lemma: The Finding of Buffon’s Needle
- A mathematical introduction to compressive sensing
- A simple proof of the restricted isometry property for random matrices
- A unified framework for linear dimensionality reduction in L1
- An elementary proof of a theorem of Johnson and Lindenstrauss
- An introduction to matrix concentration inequalities
- Compressed Sensing and Redundant Dictionaries
- Compressed sensing and its applications. MATHEON workshop, Berlin, Germany, December 2013
- Compressed sensing with coherent and redundant dictionaries
- Compressive sensing by random convolution
- Conference on Modern Analysis and Probability
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Decoding by Linear Programming
- Dequantizing Compressed Sensing: When Oversampling and Non-Gaussian Constraints Combine
- Dimension reduction by random hyperplane tessellations
- Empirical processes and random projections
- Error Decay of (almost) Consistent Signal Estimations from Quantized Gaussian Random Projections
- Isometric sketching of any set via the restricted isometry property
- Locality-sensitive hashing scheme based on \(p\)-stable distributions
- Low rank matrix recovery from rank one measurements
- New analysis of manifold embeddings and signal recovery from compressive measurements
- On sparse reconstruction from Fourier and Gaussian measurements
- Quantization
- ROP: matrix recovery via rank-one projections
- Recipes for Stable Linear Embeddings From Hilbert Spaces to $ {\mathbb {R}}^{m}$
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- Restricted isometries for partial random circulant matrices
- Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
- Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach
- Sampling and Reconstructing Signals From a Union of Linear Subspaces
- Self-calibration and biconvex compressive sensing
- Stabilizing Nonuniformly Quantized Compressed Sensing With Scalar Companders
- The convex geometry of linear inverse problems
- Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
- Two observations regarding embedding subsets of Euclidean spaces in normed spaces
- Uniform recovery of fusion frame structured sparse signals
- Uniform uncertainty principle for Bernoulli and subgaussian ensembles
- Universal Rate-Efficient Scalar Quantization
Cited in
(8)- Endpoint results for Fourier integral operators on noncompact symmetric spaces
- Fast Metric Embedding into the Hamming Cube
- Quantized compressive sensing with RIP matrices: the benefit of dithering
- Binary vectors for fast distance and similarity estimation
- Fast binary embeddings and quantized compressed sensing with structured matrices
- A unified approach to uniform signal recovery from nonlinear observations
- Quantized compressed sensing: a survey
- Representation and coding of signal geometry
This page was built for publication: Time for dithering: fast and quantized random embeddings via the restricted isometry property
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603715)
