We study the robust one-bit compressed sensing problem whose goal is to design an algorithm that faithfully recovers any sparse target vector
 $\theta_0\in\mathbb{R}^d$ \emph{uniformly} from $m$ quantized noisy measurements. Under the assumption that the measurements are sub-Gaussian,  to recover any $k$-sparse $\theta_0$ ($k\ll d$) \emph{uniformly} up to an error $\varepsilon$ with high probability, the best known computationally tractable algorithm requires\footnote{Here, an algorithm is ``computationally tractable'' if it has provable convergence guarantees. The notation $\tilde{\mathcal{O}}(\cdot)$ omits a logarithm factor of $\varepsilon^{-1}$. } $m\geq\tilde{\mathcal{O}}(k\log d/\varepsilon^4)$. In this paper, we consider a new framework for the one-bit sensing problem where the sparsity is implicitly enforced via mapping a low dimensional representation $x_0$ through a known $n$-layer ReLU generative network $G:\mathbb{R}^k\rightarrow\mathbb{R}^d$. Such a framework poses low-dimensional priors on $\theta_0$ without a known basis. We propose to recover the target $G(x_0)$ via an unconstrained empirical risk minimization (ERM) problem under a much weaker \emph{sub-exponential  measurement assumption}.  For such a problem, we establish a joint statistical and computational analysis . In particular, we prove that the ERM estimator in this new framework achieves an improved statistical rate of $m=\tilde{\mathcal{O}} (kn\log d /\epsilon^2)$ recovering any $G(x_0)$ uniformly up to an error $\varepsilon$. Moreover, from the lens of computation, we prove that under proper conditions on the ReLU weights, our proposed empirical risk, despite non-convexity, has no stationary point outside of small neighborhoods around the true representation $x_0$ and its negative multiple. Furthermore, we show that the global minimizer of the empirical risk stays within the neighborhood around $x_0$ rather than its negative multiple. Our analysis sheds some light on the possibility of inverting a deep generative model under partial and quantized measurements, complementing the recent success of using deep generative models for inverse problems. Quantized compressed sensing investigates how to design the sensing procedure, quantizer and reconstruction algorithm so as to recover a high dimensional vector from a limited number of quantized measurements. The problem of one-bit compressed sensing, which aims at recovering a target vector θ 0 ∈ R d from single-bit observations y i = sign( a i , θ 0 ), i ∈ {1, 2, · · · , m}, m d and random sensing vectors a i ∈ R d , is particularly challenging. Previous theoretical successes on this problem (e.g. Jacques et al. (2013) ; Plan and Vershynin (2013) ) mainly rely on two key assumptions: (1) The Gaussianity of the sensing vector a i , (2) The sparsity of the vector θ 0 on a given basis. However, the practical significance of these assumptions are rather limited in the sense that it is difficult to generate Gaussian vectors and high dimensional targets in practice are often distributed * Equal Contribution 1 Here, an algorithm is "computationally tractable" if it has provable convergence guarantees. The notatioñ O(·) omits a logarithm factor of ε −1 . near a low-dimensional manifold rather than sparse on some given basis. The goal of this work is to make steps towards addressing these two limitations. Specifically, we introduce a new framework for robust dithered one-bit compressed sensing where the structure of target vector θ 0 is represented via a ReLU network G : Building upon this framework, we propose a new recovery algorithm by solving an unconstrained ERM. We show this algorithm enjoys the following favorable properties: • Statistically, when taking measurements a i to be sub-exponential random vectors, with high probability and uniformly for any is the ball of radius R > 0 centered at the origin, the solution G( x m ) to the ERM recovers the true vector G(x 0 ) up to error ε when the number of samples m ≥ O(kn log 4 (ε −1 )(log d + log(ε −1 ))/ε 2 ). In particular, our result does not require REC type assumptions adopted in previous analysis of generative signal recovery works and at the same time weakens the known sub-Gaussian assumption adopted in previous one-bit compressed sensing works. When the number of layers n is small, this result meets the minimax optimal rate (up to a logarithm factor) for sparse recovery and simultaneously improves upon the best knownÕ(k log d/ε 4 ) statistical rate for computationally tractable algorithms. • Computationally, we show that solving the ERM and approximate the true representation x 0 ∈ R k is tractable. More specifically, we prove with high probability, there always exists a descent direction outside two small neighborhoods around x 0 and its negative multiple with radius O(ε 1/4 ), uniformly for any x 0 ∈ B k 2 (R ) with R = (0.5+ε) −n/2 R, when the ReLU network satisfies a weight distribution condition with parameter ε > 0 and m ≥ O(kn log 4 (ε −1 )(log d + log(ε −1 ))/ε 2 ). Furthermore, when ε is small enough, one guarantees that the solution x m stays within the neighborhood around x 0 (rather than its negative multiple). Our result is achieved without assuming the REC type conditions and under quantization errors, thereby improving upon previously known computational guarantees for ReLU generative signal recovery in linear models with small noise. From a technical perspective, our proof makes use of the special piecewise linearity property of ReLU network. The merits of such a property in the current scenario are two folds: (1) It allows us to replaces the generic chaining type bounds commonly adopted in previous works (e.g. Dirksen and Mendelson (2018a) ) by novel arguments that are "sub-Gaussian free". (2) From a hyperplane tessellation point of view, we show that for a given accuracy level, a binary embedding of 2 (R) into Euclidean space is "easier" in that it requires less random hyperplanes than that of a bounded k sparse set. Notations. Throughout the paper, let S d−1 and B(x, r) denotes the unit sphere and the ball of radius r centered at We say a random variable is sub-exponential if its ψ 1 -norm is bounded. A random vector x ∈ R d is sub-exponential if there exists a a constant C > 0 such that sup t∈S d−1 x, t ψ1 ≤ C. We use x ψ1 to denote the minimal C such that this bound holds. Furthermore, C, C , c, c 1 , c 2 , c 3 , c 4 , c 5 denote absolute constants, their actual values can be different per appearance.
We provide statistical and computational analysis of one-bit compressed sensing problem with a generative prior. 
{"src": "scitldr-AIC_train", "paper_id": "rkxbn735IH"}