Time for dithering: fast and quantized random embeddings via the restricted isometry property

DOI10.1093/IMAIAI/IAX004zbMATH Open1386.94031arXiv1607.00816OpenAlexW2964285922MaRDI QIDQ4603715FDOQ4603715

Laurent Jacques, Valerio Cambareri

Publication date: 19 February 2018

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

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 $(mathcalKsubsetmathbb{R}^n,el{l}_q)$ in $(mathbb{R}^m,el{l}_p)$ with $p,qgeq1$, we derive upper bounds on the additive distortion induced by quantization, showing that it decays either when the embedding dimension $m$ increases or when the distance of a pair of embedded vectors in $mathcalK$ 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.

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

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

zbMATH Keywords

dimensionality reductionrandom projectionsquantizationcompressive sensingrestricted isometry propertyditherfast and structured sensing matriceslow-complexity signal modelsnonlnear embeddingsquantized rank-one projections

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cites Work

• An elementary proof of a theorem of Johnson and Lindenstrauss
• Decoding by Linear Programming
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• A simple proof of the restricted isometry property for random matrices
• An Introduction to Matrix Concentration Inequalities
• A mathematical introduction to compressive sensing
• On sparse reconstruction from Fourier and Gaussian measurements
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• The convex geometry of linear inverse problems
• ROP: matrix recovery via rank-one projections
• Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
• Compressed Sensing and Redundant Dictionaries
• Quantization
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Dequantizing Compressed Sensing: When Oversampling and Non-Gaussian Constraints Combine
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Locality-sensitive hashing scheme based on p-stable distributions
• Title not available (Why is that?)
• A unified framework for linear dimensionality reduction in L1
• Compressed sensing with coherent and redundant dictionaries
• Compressive sensing by random convolution
• Restricted isometries for partial random circulant matrices
• Compressed sensing and its applications. MATHEON workshop, Berlin, Germany, December 2013
• Low rank matrix recovery from rank one measurements
• Empirical processes and random projections
• Sampling and Reconstructing Signals From a Union of Linear Subspaces
• Two observations regarding embedding subsets of Euclidean spaces in normed spaces
• New analysis of manifold embeddings and signal recovery from compressive measurements
• Uniform recovery of fusion frame structured sparse signals
• Dimension reduction by random hyperplane tessellations
• Isometric sketching of any set via the Restricted Isometry Property
• Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach
• Self-calibration and biconvex compressive sensing
• Universal Rate-Efficient Scalar Quantization
• Stabilizing Nonuniformly Quantized Compressed Sensing With Scalar Companders
• Recipes for Stable Linear Embeddings From Hilbert Spaces to $ {\mathbb {R}}^{m}$
• A Quantized Johnson–Lindenstrauss Lemma: The Finding of Buffon’s Needle
• Conference on Modern Analysis and Probability
• Error Decay of (almost) Consistent Signal Estimations from Quantized Gaussian Random Projections

Cited In (5)

• Fast Metric Embedding into the Hamming Cube
• Binary vectors for fast distance and similarity estimation
• A unified approach to uniform signal recovery from nonlinear observations
• Endpoint Results for Fourier Integral Operators on Noncompact Symmetric Spaces
• Quantized Compressed Sensing: A Survey

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)