Towards a Lower Sample Complexity for Robust One-bit Compressed Sensing

author: Rongda Zhu, Department of Computer Science, University of Illinois at Urbana-Champaign
published: Sept. 27, 2015,   recorded: July 2015,   views: 1975

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


In this paper, we propose a novel algorithm based on nonconvex sparsity-inducing penalty for one-bit compressed sensing. We prove that our algorithm has a sample complexity of O(s/ϵ2) for strong signals, and O(slogd/ϵ2) for weak signals, where s is the number of nonzero entries in the signal vector, d is the signal dimension and ϵ is the recovery error. For general signals, the sample complexity of our algorithm lies between O(s/ϵ2) and O(slogd/ϵ2). This is a remarkable improvement over the existing best sample complexity O(slogd/ϵ2). Furthermore, we show that our algorithm achieves exact support recovery with high probability for strong signals. Our theory is verified by extensive numerical experiments, which clearly illustrate the superiority of our algorithm for both approximate signal and support recovery in the noisy setting.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: