Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension

• URL: http://arxiv.org/abs/2111.14486v1
• Date: Mon, 29 Nov 2021 12:06:47 GMT
• Title: Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension
• Authors: Yuling Jiao, Dingwei Li, Min Liu, Xiangliang Lu and Yuanyuan Yang
• Abstract summary: We consider recovering $n$ dimensional signals from $m$ binary measurements corrupted by noises and sign flips. Although the binary measurements model is highly nonlinear, we propose a least square decoder.
• Score: 12.67951378791069
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we consider recovering $n$ dimensional signals from $m$ binary measurements corrupted by noises and sign flips under the assumption that the target signals have low generative intrinsic dimension, i.e., the target signals can be approximately generated via an $L$-Lipschitz generator $G: \mathbb{R}^k\rightarrow\mathbb{R}^{n}, k\ll n$. Although the binary measurements model is highly nonlinear, we propose a least square decoder and prove that, up to a constant $c$, with high probability, the least square decoder achieves a sharp estimation error $\mathcal{O} (\sqrt{\frac{k\log (Ln)}{m}})$ as long as $m\geq \mathcal{O}( k\log (Ln))$. Extensive numerical simulations and comparisons with state-of-the-art methods demonstrated the least square decoder is robust to noise and sign flips, as indicated by our theory. By constructing a ReLU network with properly chosen depth and width, we verify the (approximately) deep generative prior, which is of independent interest.

Related papers

• The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements [1.2604738912025477]
  We consider the problem of recovering the support of a sparse signal using noisy projections.<n>We establish sufficient conditions on the sample size for successful sparse recovery using sparse measurement matrices.
  arXiv  Detail & Related papers  (2025-09-01T22:26:37Z)
• Learning quadratic neural networks in high dimensions: SGD dynamics and scaling laws [21.18373933718468]
  We study the optimization and sample complexity of gradient-based training of a two-layer neural network with quadratic activation function in the high-dimensional regime.<n>We present a sharp analysis of the dynamics in the feature learning regime, for both the population limit and the finite-sample discretization.
  arXiv  Detail & Related papers  (2025-08-05T17:57:56Z)
• Entangled Mean Estimation in High-Dimensions [36.97113089188035]
  We study the task of high-dimensional entangled mean estimation in the subset-of-signals model. We show that the optimal error (up to polylogarithmic factors) is $f(alpha,N) + sqrtD/(alpha N)$, where the term $f(alpha,N)$ is the error of the one-dimensional problem and the second term is the sub-Gaussian error rate.
  arXiv  Detail & Related papers  (2025-01-09T18:31:35Z)
• New advances in universal approximation with neural networks of minimal width [4.424170214926035]
  We show that autoencoders with leaky ReLU activations are universal approximators of $Lp$ functions. We broaden our results to show that smooth invertible neural networks can approximate $Lp(mathbbRd,mathbbRd)$ on compacta.
  arXiv  Detail & Related papers  (2024-11-13T16:17:16Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ with a complexity that is not governed by information exponents.
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• Model-adapted Fourier sampling for generative compressed sensing [7.130302992490975]
  We study generative compressed sensing when the measurement matrix is randomly subsampled from a unitary matrix. We construct a model-adapted sampling strategy with an improved sample complexity of $textitO(kd| boldsymbolalpha|_22)$ measurements.
  arXiv  Detail & Related papers  (2023-10-08T03:13:16Z)
• 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)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  We show the first algorithms for the problem of regression for generalized linear models (GLMs) in the presence of additive oblivious noise. We present an algorithm that tackles newthis problem in its most general distribution-independent setting. This is the first newalgorithmic result for GLM regression newwith oblivious noise which can handle more than half the samples being arbitrarily corrupted.
  arXiv  Detail & Related papers  (2023-09-20T21:41:59Z)
• Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors [33.0212223058894]
  The problem of recovering a signal from a quadratic system $y_i=boldsymbol xtopboldsymbol A_iboldsymbol x, i=1,ldots,m$ with full-rank matrices $boldsymbol A_i$ frequently arises in applications such as unassigned distance geometry and sub-wavelength imaging. This paper addresses the high-dimensional case where $mll n$ incorporating by prior knowledge of $boldsymbol x$.
  arXiv  Detail & Related papers  (2023-09-16T16:00:07Z)
• Effective Minkowski Dimension of Deep Nonparametric Regression: Function Approximation and Statistical Theories [70.90012822736988]
  Existing theories on deep nonparametric regression have shown that when the input data lie on a low-dimensional manifold, deep neural networks can adapt to intrinsic data structures. This paper introduces a relaxed assumption that input data are concentrated around a subset of $mathbbRd$ denoted by $mathcalS$, and the intrinsic dimension $mathcalS$ can be characterized by a new complexity notation -- effective Minkowski dimension.
  arXiv  Detail & Related papers  (2023-06-26T17:13:31Z)
• Neural Networks Efficiently Learn Low-Dimensional Representations with SGD [22.703825902761405]
  We show that SGD-trained ReLU NNs can learn a single-index target of the form $y=f(langleboldsymbolu,boldsymbolxrangle) + epsilon$ by recovering the principal direction. We also provide compress guarantees for NNs using the approximate low-rank structure produced by SGD.
  arXiv  Detail & Related papers  (2022-09-29T15:29:10Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• 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)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Nonparametric Learning of Two-Layer ReLU Residual Units [22.870658194212744]
  We describe an algorithm that learns two-layer residual units with rectified linear unit (ReLU) activation. We design layer-wise objectives as functionals whose analytic minimizers express the exact ground-truth network in terms of its parameters and nonlinearities. We prove the statistical strong consistency of our algorithm, and demonstrate the robustness and sample efficiency of our algorithm by experiments.
  arXiv  Detail & Related papers  (2020-08-17T22:11:26Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)

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.