Robust 1-Bit Compressed Sensing via Hinge Loss Minimization

We study the problem of estimating a structured high-dimensional signal x₀ ϵ ℝⁿ 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 typically applied in classification tasks, its capacity to estimate a specific signal vector is largely unexplored. In contrast to other popular loss functions considered in signal estimation, which are at least locally strongly convex, the hinge loss is just piecewise linear, so that its "curvature energy" is concentrated in a single point. 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 error bounds show that stable and robust reconstruction of x₀ can be achieved with the optimal approximation 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₀ can belong to an arbitrary bounded convex set K ⊂ ℝⁿ. For the proofs of our main results 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.