Robust 1-bit compressed sensing via hinge loss minimization

This work theoretically studies the problem of estimating a structured high-dimensional signal x0 ∈ Rn
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 nonasymptotic error bounds show that stable and robust reconstruction of x0 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 x0 can belong to an arbitrary
bounded convex set K ⊂ Rn. 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.