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