Robust one-bit compressed sensing with partial circulant matrices

DOI10.1214/22-AAP1855zbMATH Open1515.94023arXiv1812.06719OpenAlexW2904320893MaRDI QIDQ6104014FDOQ6104014

Authors: Sjoerd Dirksen, Shahar Mendelson 

Publication date: 5 June 2023

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: We present optimal sample complexity estimates for one-bit compressed sensing problems in a realistic scenario: the procedure uses a structured matrix (a randomly sub-sampled circulant matrix) and is robust to analog pre-quantization noise as well as to adversarial bit corruptions in the quantization process. Our results imply that quantization is not a statistically expensive procedure in the presence of nontrivial analog noise: recovery requires the same sample size one would have needed had the measurement matrix been Gaussian and the noisy analog measurements been given as data.

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

Recommendations

• One-bit compressed sensing with partial Gaussian circulant matrices
• Quantized compressed sensing for random circulant matrices
• Quantization of compressive samples with stable and robust recovery
• One-bit compressed sensing with non-Gaussian measurements
• One-bit compressed sensing by linear programming

zbMATH Keywords

empirical processescompressed sensingquantizationgeneric chainingrandom circulant matrices

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Geometric probability and stochastic geometry (60D05) Sampling theory in information and communication theory (94A20)

Cites Work

• Title not available (Why is that?)
• A mathematical introduction to compressive sensing
• Some limit theorems for empirical processes (with discussion)
• One-bit compressed sensing by linear programming
• Compressive sensing by random convolution
• One-bit compressed sensing with non-Gaussian measurements
• Recovering low-rank matrices from binary measurements
• Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces
• Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach
• \(5n\) Minkowski symmetrizations suffice to arrive at an approximate Euclidean ball
• Improved bounds for sparse recovery from subsampled random convolutions
• Flavors of compressive sensing
• ``Local vs. ``global parameters -- breaking the Gaussian complexity barrier
• Non-Gaussian hyperplane tessellations and robust one-bit compressed sensing
• One-bit compressed sensing with partial Gaussian circulant matrices
• Quantized compressed sensing for random circulant matrices
• Fast binary embeddings and quantized compressed sensing with structured matrices
• Capacity Analysis of One-Bit Quantized MIMO Systems With Transmitter Channel State Information
• Quantized compressed sensing: a survey
• Quantized compressive sensing with RIP matrices: the benefit of dithering

Cited In (5)

• Fast Metric Embedding into the Hamming Cube
• A unified approach to uniform signal recovery from nonlinear observations
• Quantized compressed sensing for random circulant matrices
• Robust Decoding from 1-Bit Compressive Sampling with Ordinary and Regularized Least Squares
• One-bit compressed sensing with partial Gaussian circulant matrices

This page was built for publication: Robust one-bit compressed sensing with partial circulant matrices

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