Robust Decoding from 1-Bit Compressive Sampling with Ordinary and Regularized Least Squares

DOI10.1137/17M1154102zbMATH Open1395.49033arXiv1711.01206OpenAlexW2810437963MaRDI QIDQ3174766FDOQ3174766

Xiliang Lu, Jian Huang, Li-Ping Zhu, Yu Ling Jiao

Publication date: 18 July 2018

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: In 1-bit compressive sensing (1-bit CS) where 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=etaodotextrmsign(Psi{x}^{*}+epsilon)$, where $x^{*}inmathcal{R}^n,yinmathcal{R}^m$, $Psiinmathcal{R}^{mimesn}$, and $epsilon$ is the random error before quantization and $etainmathcal{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 least squares approach under the over-determined and under-determined settings. For $m>n$, we show that, up to a constant $c$, with high probability, the least squares solution $x_{extrmls}$ approximates $x^{*}$ with precision $delta$ as long as $mgeqwidetildemathcalO(fracndelt{a}^2)$. For $m<n$, we prove that, up to a constant $c$, with high probability, the $el{l}_1$-regularized least-squares solution $x_{el{l}_1}$ lies in the ball with center $x^{*}$ and radius $delta$ provided that $mgeqmathcalO(fracslogndelt{a}^2)$ and $|x^{*}{|}_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 to solve a small least squares problem on the active set. Therefore, the PDAS is extremely efficient 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 efficiency of our algorithm.

Full work available at URL: https://arxiv.org/abs/1711.01206

Recommendations

• Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
• One-Bit Compressive Sensing With Norm Estimation
• Quantization of compressive samples with stable and robust recovery
• Robust one-bit compressed sensing with partial circulant matrices
• Robust 1-bit compressed sensing via hinge loss minimization
• 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
• On Compressive Sensing in Coding Problems: A Rigorous Approach
• Stability of 1-bit compressed sensing in sparse data reconstruction
• One-bit compressed sensing by greedy algorithms
• One-bit compressed sensing by linear programming

zbMATH Keywords

continuation1-bit compressive sensingprimal dual active set algorithm\(\ell_1\)-regularized least squaresone-step convergence

Mathematics Subject Classification ID

Numerical methods for inverse problems for boundary value problems involving PDEs (65N21) Newton-type methods (49M15) Inverse problems in optimal control (49N45)

Cites Work

• Title not available (Why is that?)
• A wavelet tour of signal processing. The sparse way.
• Atomic Decomposition by Basis Pursuit
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• Introductory lectures on convex optimization. A basic course.
• Trust, But Verify: Fast and Accurate Signal Recovery From 1-Bit Compressive Measurements
• A new approach to variable selection in least squares problems
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• Proximal Splitting Methods in Signal Processing
• Signal Recovery by Proximal Forward-Backward Splitting
• A nonsmooth version of Newton's method
• Optimization with sparsity-inducing penalties
• A mathematical introduction to compressive sensing
• Lagrange Multiplier Approach to Variational Problems and Applications
• A Primal Dual Active Set Algorithm With Continuation for Compressed Sensing
• Title not available (Why is that?)
• A primal dual active set with continuation algorithm for the \(\ell^0\)-regularized optimization problem
• Information criteria and statistical modeling.
• One-bit compressed sensing by linear programming
• Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
• Matrix-free interior point method for compressed sensing problems
• A Semismooth Newton Method for $\mathrm{L}^1$ Data Fitting with Automatic Choice of Regularization Parameters and Noise Calibration
• One-bit compressed sensing with non-Gaussian measurements
• Robust 1-bit Compressive Sensing Using Adaptive Outlier Pursuit
• A Regularization Parameter for Nonsmooth Tikhonov Regularization
• A Duality-Based Splitting Method for $\ell^1$-$TV$ Image Restoration with Automatic Regularization Parameter Choice
• Iterative parameter choice by discrepancy principle
• Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach
• Estimation in High Dimensions: A Geometric Perspective
• High-dimensional estimation with geometric constraints: Table 1.
• Noisy 1-bit compressive sensing: models and algorithms
• One-Bit Compressive Sensing With Norm Estimation
• Inverse problems. Tikhonov theory and algorithms
• A Preconditioner for A Primal-Dual Newton Conjugate Gradient Method for Compressed Sensing Problems
• Selected Works of David Brillinger
• One-Bit Compressed Sensing by Greedy Algorithms

Cited In (10)

• Distributed Decoding From Heterogeneous 1-Bit Compressive Measurements
• A primal dual active set with continuation algorithm for high-dimensional nonconvex SICA-penalized regression
• Just least squares: binary compressive sampling with low generative intrinsic dimension
• Byzantine-robust and efficient distributed sparsity learning: a surrogate composite quantile regression approach
• A unified primal dual active set algorithm for nonconvex sparse recovery
• REMI: REGRESSION WITH MARGINAL INFORMATION AND ITS APPLICATION IN GENOME-WIDE ASSOCIATION STUDIES
• An Algorithm Solving Compressive Sensing Problem Based on Maximal Monotone Operators
• Distributed Sparse Composite Quantile Regression in Ultrahigh Dimensions
• NBIHT: An Efficient Algorithm for 1-Bit Compressed Sensing With Optimal Error Decay Rate
• Quadratic Convergence of Smoothing Newton's Method for 0/1 Loss Optimization

Uses Software

• PDCO
• UNLocBoX

This page was built for publication: Robust Decoding from 1-Bit Compressive Sampling with Ordinary and Regularized Least Squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3174766)