One-Bit Compressed Sensing via One-Shot Hard Thresholding

• URL: http://arxiv.org/abs/2007.03641v2
• Date: Thu, 9 Jul 2020 11:58:57 GMT
• Title: One-Bit Compressed Sensing via One-Shot Hard Thresholding
• Authors: Jie Shen
• Abstract summary: A problem of 1-bit compressed sensing is to estimate a sparse signal from a few binary measurements. We present a novel and concise analysis that moves away from the widely used non-constrained notion of width.
• Score: 7.594050968868919
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper concerns the problem of 1-bit compressed sensing, where the goal is to estimate a sparse signal from a few of its binary measurements. We study a non-convex sparsity-constrained program and present a novel and concise analysis that moves away from the widely used notion of Gaussian width. We show that with high probability a simple algorithm is guaranteed to produce an accurate approximation to the normalized signal of interest under the $\ell_2$-metric. On top of that, we establish an ensemble of new results that address norm estimation, support recovery, and model misspecification. On the computational side, it is shown that the non-convex program can be solved via one-step hard thresholding which is dramatically efficient in terms of time complexity and memory footprint. On the statistical side, it is shown that our estimator enjoys a near-optimal error rate under standard conditions. The theoretical results are substantiated by numerical experiments.

Related papers

• Robust shallow shadows [0.251657752676152]
  We present a robust shadow estimation protocol for wide classes of shallow measurement circuits. We show how to estimate this directly from experimental data using tensor-network tools. Under the practical constraints of current and near-term noisy quantum devices, our method maximally realizes the potential of shadow estimation with global rotations.
  arXiv  Detail & Related papers  (2024-05-09T18:00:09Z)
• Quantum Sparse Coding [5.130440339897477]
  We develop a quantum-inspired algorithm for sparse coding. The emergence of quantum computers and Ising machines can potentially lead to more accurate estimations. We conduct numerical experiments with simulated data on Lightr's quantum-inspired digital platform.
  arXiv  Detail & Related papers  (2022-09-08T13:00:30Z)
• Computationally Efficient and Statistically Optimal Robust Low-rank Matrix and Tensor Estimation [15.389011827844572]
  Low-rank linear shrinkage estimation undertailed noise is challenging, both computationally statistically. We introduce a novel sub-ient (RsGrad) which is not only computationally efficient but also statistically optimal.
  arXiv  Detail & Related papers  (2022-03-02T09:05:15Z)
• Nystr\"om Kernel Mean Embeddings [92.10208929236826]
  We propose an efficient approximation procedure based on the Nystr"om method. It yields sufficient conditions on the subsample size to obtain the standard $n-1/2$ rate. We discuss applications of this result for the approximation of the maximum mean discrepancy and quadrature rules.
  arXiv  Detail & Related papers  (2022-01-31T08:26:06Z)
• Accelerated and instance-optimal policy evaluation with linear function approximation [17.995515643150657]
  Existing algorithms fail to match at least one of these lower bounds. We develop an accelerated, variance-reduced fast temporal difference algorithm that simultaneously matches both lower bounds and attains a strong notion of instance-optimality.
  arXiv  Detail & Related papers  (2021-12-24T17:21:04Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  Even simple methods like least squares can exhibit non-normal behavior when data is collected in an adaptive manner. We propose a family of online debiasing estimators to correct these distributional anomalies in at least squares estimation. We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
  arXiv  Detail & Related papers  (2021-07-05T21:05:11Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  We show that $O(k log L)$ samples suffice to guarantee that the signal is close to any vector that minimizes an amplitude-based empirical loss function. We adapt this result to sparse phase retrieval, and show that $O(s log n)$ samples are sufficient for a similar guarantee when the underlying signal is $s$-sparse and $n$-dimensional.
  arXiv  Detail & Related papers  (2021-06-29T12:49:54Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Learning Minimax Estimators via Online Learning [55.92459567732491]
  We consider the problem of designing minimax estimators for estimating parameters of a probability distribution. We construct an algorithm for finding a mixed-case Nash equilibrium.
  arXiv  Detail & Related papers  (2020-06-19T22:49:42Z)
• Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors [52.06292503723978]
  Motivated by advances in compressive sensing with generative models, we study the problem of 1-bit compressive sensing with generative models. We first consider noiseless 1-bit measurements, and provide sample complexity bounds for approximate recovery under i.i.d.Gaussian measurements. We demonstrate that the Binary $epsilon$-Stable Embedding property, which characterizes the robustness of the reconstruction to measurement errors and noise, also holds for 1-bit compressive sensing with Lipschitz continuous generative models.
  arXiv  Detail & Related papers  (2020-02-05T09:44:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.