Department of Mathematics,
University of California San Diego
****************************
Center for Computational Mathematics Seminar & MINDS Seminar
Junren Chen
University of Hong Kong
Efficient and optimal quantized compressed sensing
Abstract:
The goal of quantized compressed sensing (QCS) is to recover structured signals from quantized measurements. The performance bounds of hamming distance minimization (HDM) were well established and known to be optimal in recovering sparse signals, but HDM is in general computationally infeasible. In this talk, we propose an efficient projected gradient descent (PGD) algorithm for QCS which generalizes normalized binary iterative hard thresholding (NBIHT) in one-bit compressed sensing for sparse vectors. Under sub-Gaussian design, we identify the conditions under which PGD achieves essentially the same error rates as HDM, up to logarithmic factors. These conditions are easy to validate and include estimates of the separation probability, a small-ball probability and some moments. We specialize the general framework to several popular memoryless QCS models and show that PGD achieves the optimal rate O(k/m) in recovering sparse vectors, and the best-known rate O((k/m)^{1/3}) in recovering effectively sparse signals. This is joint work with Ming Yuan. An initial version is available in https://arxiv.org/abs/2407.04951.
April 8, 2025
11:00 AM
APM 2402 and Zoom ID 946 4079 7326
Research Areas
Mathematics of Information, Data, and Signals****************************