[Home]
[
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Efficient and optimal quantized compressed sensing
Junren Chen
University of Hong Kong
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
Tuesday, April 8, 2025
11:00AM AP&M 2402 and Zoom ID 946 4079 7326 (Joint with MINDS)
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Directors:
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Junren Chen
University of Hong Kong
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
Tuesday, April 8, 2025
11:00AM AP&M 2402 and Zoom ID 946 4079 7326 (Joint with MINDS)