Improved Support Recovery in Universal One-bit Compressed Sensing

• URL: http://arxiv.org/abs/2210.16657v1
• Date: Sat, 29 Oct 2022 17:43:14 GMT
• Title: Improved Support Recovery in Universal One-bit Compressed Sensing
• Authors: Namiko Matsumoto, Arya Mazumdar, Soumyabrata Pal
• Abstract summary: One-bit compressed (1bCS) is an extremely quantized signal acquisition method. The focus of this paper is support recovery, which often also computationally facilitate approximate signal recovery. We show that the first type of recovery is possible with $tildeO(k/epsilon)$ measurements, while the later type of recovery, more challenging, is possible with $tildeO(maxk/epsilon,k3/2)$ measurements.
• Score: 37.5349071806395
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One-bit compressed sensing (1bCS) is an extremely quantized signal acquisition method that has been proposed and studied rigorously in the past decade. In 1bCS, linear samples of a high dimensional signal are quantized to only one bit per sample (sign of the measurement). Assuming the original signal vector to be sparse, existing results in 1bCS either aim to find the support of the vector, or approximate the signal allowing a small error. The focus of this paper is support recovery, which often also computationally facilitate approximate signal recovery. A {\em universal} measurement matrix for 1bCS refers to one set of measurements that work for all sparse signals. With universality, it is known that $\tilde{\Theta}(k^2)$ 1bCS measurements are necessary and sufficient for support recovery (where $k$ denotes the sparsity). To improve the dependence on sparsity from quadratic to linear, in this work we propose approximate support recovery (allowing $\epsilon>0$ proportion of errors), and superset recovery (allowing $\epsilon$ proportion of false positives). We show that the first type of recovery is possible with $\tilde{O}(k/\epsilon)$ measurements, while the later type of recovery, more challenging, is possible with $\tilde{O}(\max\{k/\epsilon,k^{3/2}\})$ measurements. We also show that in both cases $\Omega(k/\epsilon)$ measurements would be necessary for universal recovery. Improved results are possible if we consider universal recovery within a restricted class of signals, such as rational signals, or signals with bounded dynamic range. In both cases superset recovery is possible with only $\tilde{O}(k/\epsilon)$ measurements. Other results on universal but approximate support recovery are also provided in this paper. All of our main recovery algorithms are simple and polynomial-time.

Related papers

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Robust 1-bit Compressed Sensing with Iterative Hard Thresholding [18.05573480691047]
  In 1-bit compressed sensing, the aim is to estimate a $k$-sparse unit vector $xin Sn-1$ within an $epsilon$ error. In this paper, we study a noisy version where a fraction of the measurements can be flipped, potentially by an adversary. We show that when up to $tau$-fraction of the sign measurements are incorrect, BIHTally provides an estimate of $x$ within an $tildeO(epsilon+tau)$ error.
  arXiv  Detail & Related papers  (2023-10-12T03:41:32Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing [29.570141048369297]
  We show that the BIHT algorithm converges with only $tildeO(frackepsilon) measurements. This is also an example of a linear descent algorithm converging to the correct solution for a non problem.
  arXiv  Detail & Related papers  (2022-07-07T16:52:50Z)
• Polynomial-time sparse measure recovery [2.0951285993543642]
  We propose the first poly-time recovery method from carefully designed moments. This method relies on the recovery of a planted two-layer neural network with two-dimensional inputs, a finite width, and zero-one activation.
  arXiv  Detail & Related papers  (2022-04-16T22:12:55Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  We study the problem of estimating the value of a known smooth function $f$ at an unknown point $boldsymbolmu in mathbbRn$, where each component $mu_i$ can be sampled via a noisy oracle. We design an instance-adaptive algorithm that learns to sample according to the importance of each coordinate, and with probability at least $1-delta$ returns an $epsilon$ accurate estimate of $f(boldsymbolmu)$.
  arXiv  Detail & Related papers  (2022-03-18T18:50:52Z)
• Support Recovery in Universal One-bit Compressed Sensing [54.26691979520478]
  One-bit compressed sensing (1bCS) is an extreme-quantized signal acquisition method. We show that it is possible to universally recover the support with a small number of false positives.
  arXiv  Detail & Related papers  (2021-07-19T18:10:51Z)
• 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)
• Hadamard Wirtinger Flow for Sparse Phase Retrieval [24.17778927729799]
  We consider the problem of reconstructing an $n$-dimensional $k$-sparse signal from a set of noiseless magnitude-only measurements. Formulating the problem as an unregularized empirical risk minimization task, we study the sample complexity performance of gradient descent with Hadamard parametrization. We numerically investigate the performance of HWF at convergence and show that, while not requiring any explicit form of regularization nor knowledge of $k$, HWF adapts to the signal sparsity and reconstructs sparse signals with fewer measurements than existing gradient based methods.
  arXiv  Detail & Related papers  (2020-06-01T16:41:27Z)

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.