Name
Title | ||
|---|---|---|
Robust Decoding from 1-Bit Compressive Sampling with Ordinary and Regularized Least Squares |
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1137/17M1154102 | SIAM JOURNAL ON SCIENTIFIC COMPUTING |
Keywords | Field | DocType |
1-bit compressive sensing,l(1)-regularized least squares,primal dual active set algorithm,one-step convergence,continuation | Least squares,Combinatorics,Overdetermined system,Underdetermined system,Mathematical analysis,Multivariate random variable,Quantization (physics),Quantization (signal processing),Compressed sensing,Mathematics,Binary number | Journal |
Volume | Issue | ISSN |
40 | 4 | 1064-8275 |
Citations | PageRank | References |
1 | 0.36 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jian Huang | 1 | 32 | 13.19 |
| Yuling Jiao | 2 | 39 | 9.90 |
| Xiliang Lu | 3 | 14 | 4.77 |
| Li-Ping Zhu | 4 | 22 | 7.66 |