Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension
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.
Code (0)
등록된 구현이 없습니다.
Tasks
DecoderSimilar Papers 제목 키워드 기반
Blind Orthogonal Least Squares based Compressive Spectrum Sensing
As an enabling technique of cognitive radio (CR), compressive spectrum sensing (CSS) based on compressive sensing (CS) can detect the spectrum opportunities from wide frequency bands efficiently and accurately by using s…
Compressive SensingThird-Order Statistics Reconstruction from Compressive Measurements
Estimation of third-order statistics relies on the availability of a huge amount of data records, which can pose severe challenges on the data collecting hardware in terms of considerable storage costs, overwhelming ener…
Compressive SensingCompressive Spectrum Sensing Using Blind-Block Orthogonal Least Squares
Compressive sensing (CS) has recently emerged as an extremely efficient technology of the wideband spectrum sensing. In compressive spectrum sensing (CSS), it is necessary to know the sparsity or the noise information in…
Compressive SensingCompressive Statistical Learning with Random Feature Moments
We describe a general framework -- compressive statistical learning -- for resource-efficient large-scale learning: the training collection is compressed in one pass into a low-dimensional sketch (a vector of random empi…
ClusteringAdjusted least squares fitting of algebraic hypersurfaces
We consider the problem of fitting a set of points in Euclidean space by an algebraic hypersurface. We assume that points on a true hypersurface, described by a polynomial equation, are corrupted by zero mean independent…