Fast binary embeddings and quantized compressed sensing with structured matrices

DOI10.1002/CPA.21850MaRDI QIDQ5212891zbMATH OpenOpenAlexWikidataFDO

Authors Thang Huynh, Rayan Saab

Publication date 30 January 2020

Published in Communications on Pure and Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

binary embeddingscompressed sensingquantization

Mathematics Subject Classification ID

Equations and inequalities involving linear operators, with vector unknowns (47A50) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: This paper deals with two related problems, namely distance-preserving binary embeddings and quantization for compressed sensing . First, we propose fast methods to replace points from a subset $mathcalXsubsetmathbb{R}^n$, associated with the Euclidean metric, with points in the cube ${pm1}^m$ and we associate the cube with a pseudo-metric that approximates Euclidean distance among points in $mathcalX$. Our methods rely on quantizing fast Johnson-Lindenstrauss embeddings based on bounded orthonormal systems and partial circulant ensembles, both of which admit fast transforms. Our quantization methods utilize noise-shaping, and include Sigma-Delta schemes and distributed noise-shaping schemes. The resulting approximation errors decay polynomially and exponentially fast in $m$, depending on the embedding method. This dramatically outperforms the current decay rates associated with binary embeddings and Hamming distances. Additionally, it is the first such binary embedding result that applies to fast Johnson-Lindenstrauss maps while preserving $el{l}_2$ norms. Second, we again consider noise-shaping schemes, albeit this time to quantize compressed sensing measurements arising from bounded orthonormal ensembles and partial circulant matrices. We show that these methods yield a reconstruction error that again decays with the number of measurements (and bits), when using convex optimization for reconstruction. Specifically, for Sigma-Delta schemes, the error decays polynomially in the number of measurements, and it decays exponentially for distributed noise-shaping schemes based on beta encoding. These results are near optimal and the first of their kind dealing with bounded orthonormal systems.

Recommendations

• Fast binary embeddings with Gaussian circulant matrices: improved bounds
• Quantized compressed sensing for random circulant matrices
• Time for dithering: fast and quantized random embeddings via the restricted isometry property
• On binary embedding using circulant matrices
• Distributed noise-shaping quantization. I: Beta duals of finite frames and near-optimal quantization of random measurements

Cited in

(15)

• Fast binary embeddings with Gaussian circulant matrices: improved bounds
• On recovery guarantees for one-bit compressed sensing on manifolds
• Quantization for spectral super-resolution
• Adapted decimation on finite frames for arbitrary orders of sigma-delta quantization
• Quantized compressed sensing for random circulant matrices
• Quantized compressed sensing: a survey
• On binary embedding using circulant matrices
• Representation and coding of signal geometry
• Time for dithering: fast and quantized random embeddings via the restricted isometry property
• Binary Matrices for Compressed Sensing
• Optimal (Euclidean) Metric Compression
• Endpoint results for Fourier integral operators on noncompact symmetric spaces
• Sigma Delta Quantization for Images
• Robust one-bit compressed sensing with partial circulant matrices
• Fast Metric Embedding into the Hamming Cube

This page was built for publication: Fast binary embeddings and quantized compressed sensing with structured matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212891)