Robust 1-bit compressed sensing via hinge loss minimization

DOI10.1093/IMAIAI/IAZ010MaRDI QIDQ5006524zbMATH OpenOpenAlexFDO

Authors Martin Genzel, Alexander Stollenwerk

Publication date 16 August 2021

Published in Information and Inference: A Journal of the IMA (Search for Journal in Brave)

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

zbMATH Keywords

1-bit compressed sensingGaussian widthhinge lossMendelson's small ball methodstructured empirical risk minimization

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: This work theoretically studies the problem of estimating a structured high-dimensional signal $x_{0}inmathbb{R}^n$ from noisy $1$-bit Gaussian measurements. Our recovery approach is based on a simple convex program which uses the hinge loss function as data fidelity term. While such a risk minimization strategy is very natural to learn binary output models, such as in classification, its capacity to estimate a specific signal vector is largely unexplored. A major difficulty is that the hinge loss is just piecewise linear, so that its "curvature energy" is concentrated in a single point. This is substantially different from other popular loss functions considered in signal estimation, e.g., the square or logistic loss, which are at least locally strongly convex. It is therefore somewhat unexpected that we can still prove very similar types of recovery guarantees for the hinge loss estimator, even in the presence of strong noise. More specifically, our non-asymptotic error bounds show that stable and robust reconstruction of $x_0$ can be achieved with the optimal oversampling rate $O(m^{-1/2})$ in terms of the number of measurements $m$. Moreover, we permit a wide class of structural assumptions on the ground truth signal, in the sense that $x_0$ can belong to an arbitrary bounded convex set $Ksubsetmathbb{R}^n$. The proofs of our main results rely on some recent advances in statistical learning theory due to Mendelson. In particular, we invoke an adapted version of Mendelson's small ball method that allows us to establish a quadratic lower bound on the error of the first order Taylor approximation of the empirical hinge loss function.

Recommendations

• One-bit compressed sensing with non-Gaussian measurements
• One-bit compressed sensing by linear programming
• Noisy 1-bit compressive sensing: models and algorithms
• On recovery guarantees for one-bit compressed sensing on manifolds
• Statistical mechanics approach to 1-bit compressed sensing

Cited in

(7)

• AdaBoost and robust one-bit compressed sensing
• Adaptive iterative hard thresholding for least absolute deviation problems with sparsity constraints
• Covariance estimation under one-bit quantization
• Robust Decoding from 1-Bit Compressive Sampling with Ordinary and Regularized Least Squares
• NBIHT: An Efficient Algorithm for 1-Bit Compressed Sensing With Optimal Error Decay Rate
• A unified approach to uniform signal recovery from nonlinear observations
• Just least squares: binary compressive sampling with low generative intrinsic dimension

This page was built for publication: Robust 1-bit compressed sensing via hinge loss minimization

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