Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach

DOI10.1109/TIT.2012.2207945zbMATH Open1364.94153arXiv1202.1212OpenAlexW2964322027MaRDI QIDQ2989476FDOQ2989476

Authors: Y. Plan, Roman Vershynin 

Publication date: 8 June 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: This paper develops theoretical results regarding noisy 1-bit compressed sensing and sparse binomial regression. We show that a single convex program gives an accurate estimate of the signal, or coefficient vector, for both of these models. We demonstrate that an s-sparse signal in R^n can be accurately estimated from m = O(slog(n/s)) single-bit measurements using a simple convex program. This remains true even if each measurement bit is flipped with probability nearly 1/2. Worst-case (adversarial) noise can also be accounted for, and uniform results that hold for all sparse inputs are derived as well. In the terminology of sparse logistic regression, we show that O(slog(n/s)) Bernoulli trials are sufficient to estimate a coefficient vector in R^n which is approximately s-sparse. Moreover, the same convex program works for virtually all generalized linear models, in which the link function may be unknown. To our knowledge, these are the first results that tie together the theory of sparse logistic regression to 1-bit compressed sensing. Our results apply to general signal structures aside from sparsity; one only needs to know the size of the set K where signals reside. The size is given by the mean width of K, a computable quantity whose square serves as a robust extension of the dimension.

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

Mathematics Subject Classification ID

Convex programming (90C25) Applications of mathematical programming (90C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Information theory (general) (94A15)

Cited In (61)

• Just least squares: binary compressive sampling with low generative intrinsic dimension
• On the convergence rate of projected gradient descent for a back-projection based objective
• Uniform recovery guarantees for quantized corrupted sensing using structured or generative priors
• Structure from randomness in halfspace learning with the zero-one loss
• Gradient projection Newton algorithm for sparse collaborative learning using synthetic and real datasets of applications
• Covariance estimation under one-bit quantization
• Fast binary embeddings with Gaussian circulant matrices: improved bounds
• The recovery of ridge functions on the hypercube suffers from the curse of dimensionality
• One-bit compressed sensing with non-Gaussian measurements
• One-bit sensing, discrepancy and Stolarsky's principle
• Non-Gaussian hyperplane tessellations and robust one-bit compressed sensing
• One-bit compressed sensing via \(\ell_p\) \((0<p<1)\)-minimization method
• Least squares estimation in the monotone single index model
• Robust one-bit compressed sensing with partial circulant matrices
• Double fused Lasso regularized regression with both matrix and vector valued predictors
• Sparse classification: a scalable discrete optimization perspective
• Title not available (Why is that?)
• Quantization and compressive sensing
• Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness
• Sigma delta quantization with harmonic frames and partial Fourier ensembles
• Hypothesis testing for high-dimensional sparse binary regression
• On recovery guarantees for one-bit compressed sensing on manifolds
• Title not available (Why is that?)
• A unified approach to uniform signal recovery from nonlinear observations
• An extended Newton-type algorithm for \(\ell_2\)-regularized sparse logistic regression and its efficiency for classifying large-scale datasets
• Fast and reliable parameter estimation from nonlinear observations
• A one-bit, comparison-based gradient estimator
• Statistical Inference for High-Dimensional Generalized Linear Models With Binary Outcomes
• An introduction to compressed sensing
• Variable smoothing incremental aggregated gradient method for nonsmooth nonconvex regularized optimization
• Estimation from nonlinear observations via convex programming with application to bilinear regression
• On the atomic decomposition of coorbit spaces with non-integrable kernel
• Generalized high-dimensional trace regression via nuclear norm regularization
• Phase retrieval by binary questions: which complementary subspace is closer?
• Convergence guarantee for the sparse monotone single index model
• Noisy 1-bit compressive sensing: models and algorithms
• Quantized compressed sensing: a survey
• \(\ell^1\)-analysis minimization and generalized (co-)sparsity: when does recovery succeed?
• Generalizing CoSaMP to signals from a union of low dimensional linear subspaces
• An approach to one-bit compressed sensing based on probably approximately correct learning theory
• Representation and coding of signal geometry
• Robust Decoding from 1-Bit Compressive Sampling with Ordinary and Regularized Least Squares
• A theory of capacity and sparse neural encoding
• Time for dithering: fast and quantized random embeddings via the restricted isometry property
• The landscape of empirical risk for nonconvex losses
• Sigma Delta Quantization for Images
• Sparse recovery from saturated measurements
• Global and Simultaneous Hypothesis Testing for High-Dimensional Logistic Regression Models
• Estimation in high dimensions: a geometric perspective
• High-dimensional estimation with geometric constraints
• Flavors of compressive sensing
• Linear regression with sparsely permuted data
• Simple classification using binary data
• A simple tool for bounding the deviation of random matrices on geometric sets
• Classification scheme for binary data with extensions
• Applied harmonic analysis and data processing. Abstracts from the workshop held March 25--31, 2018
• Sparse learning for large-scale and high-dimensional data: a randomized convex-concave optimization approach
• Classification of COVID19 Patients using robust logistic regression
• AdaBoost and robust one-bit compressed sensing
• Characterization of \(\ell_1\) minimizer in one-bit compressed sensing
• Endpoint results for Fourier integral operators on noncompact symmetric spaces

This page was built for publication: Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach

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