Journal article
ROBUST DECODING FROM 1-BIT COMPRESSIVE SAMPLING WITH ORDINARY AND REGULARIZED LEAST SQUARES
SIAM journal on scientific computing, Vol.40(4), pp.A2062-A2086
01/01/2018
DOI: 10.1137/17M1154102
Abstract
In 1-bit compressive sensing (1-bit CS) where a target signal is coded into a binary measurement, one goal is to recover the signal from noisy and quantized samples. Mathematically, the 1-bit CS model reads y = eta circle dot sign(Psi x* + epsilon), where x* is an element of R-n; y is an element of R-m, Psi is an element of R(mx)n, and epsilon is the random error before quantization and eta is an element of R-n is a random vector modeling the sign flips. Due to the presence of nonlinearity, noise, and sign flips, it is quite challenging to decode from the 1-bit CS. In this paper, we consider a least squares approach under the overdetermined and underdetermined settings. For m > n, we show that, up to a constant c, with high probability, the least squares solution xls approximates x* with precision ffi as long as m >= (O) over tilde (n/delta(2)). For m < n, we prove that, up to a constant c, with high probability, the l(1)-regularized least-squares solution xl(1) lies in the ball with center x* and radius delta provided that m >= O (s log n/delta(2)) and parallel to x parallel to(0) := s < m. We introduce a Newton type method, the so-called primal and dual active set (PDAS) algorithm, to solve the nonsmooth optimization problem. The PDAS possesses the property of one-step convergence. It only requires solving a small least squares problem on the active set. Therefore, the PDAS is extremely e ffi cient for recovering sparse signals through continuation. We propose a novel regularization parameter selection rule which does not introduce any extra computational overhead. Extensive numerical experiments are presented to illustrate the robustness of our proposed model and the e ffi ciency of our algorithm.
Details
- Title: Subtitle
- ROBUST DECODING FROM 1-BIT COMPRESSIVE SAMPLING WITH ORDINARY AND REGULARIZED LEAST SQUARES
- Creators
- Jian Huang - Hong Kong Polytechnic UniversityYuling Jiao - Zhongnan University of Economics and LawXiliang Lu - Wuhan UniversityLiping Zhu - Renmin University of China
- Resource Type
- Journal article
- Publication Details
- SIAM journal on scientific computing, Vol.40(4), pp.A2062-A2086
- DOI
- 10.1137/17M1154102
- ISSN
- 1064-8275
- eISSN
- 1095-7197
- Publisher
- SIAM PUBLICATIONS
- Number of pages
- 25
- Grant note
- 16JJD910002 / Chinese Ministry of Education Project of Key Research Institute of Humanities and Social Sciences at Universities 11501579 / National Science Foundation of China (NSFC) National Youth Top-notch Talent Support Program of China 11471253; 91630313; 11731011 / NSFC 2016CFB486 / National Science Foundation of Hubei Province
- Language
- English
- Date published
- 01/01/2018
- Academic Unit
- Statistics and Actuarial Science
- Record Identifier
- 9984257629102771
Metrics
23 Record Views