In this paper we consider memoryless one-bit compressed sensing with randomly subsampled Gaussian circulant matrices. We show that in a small sparsity regime and for small enough accuracy @math , @math measurements suffice to reconstruct the direction of any @math -sparse vector up to accuracy @math via an efficient program. We derive this result by proving that partial Gaussian circulant matrices satisfy an @math RIP-property. Under a slightly worse dependence on @math , we establish stability with respect to approximate sparsity, as well as full vector recovery results.
Standard compressive sensing with partial circulant matrices. In standard (unquantized) compressive sensing, the task is to recover an (approximately) sparse vector @math from measurements @math , where @math with @math . A number of reconstruction algorithms have been introduced, most notably @math -minimization which computes the minimizer of [ z ^N |z |_1 subject to A z = Ax. ] The ( @math -)restricted isometry property is a classical way of analyzing the performance of compressive sensing @cite_9 . The restricted isometry constant @math is defined as the smallest constant @math such that If @math then all @math -sparse signals can be reconstructed via @math -minimization exactly, see e.g. @cite_17 @cite_9 . Stability under noise and sparsity defect can be shown as well and similar guarantees also hold for other reconstruction algorithms @cite_9 . It is well-known that Gaussian random matrices satisfy @math with probability at least @math if @math [Chapter 9] fora13 .
@cite_9 @cite_17
2032291279 2000150201
In this paper we consider memoryless one-bit compressed sensing with randomly subsampled Gaussian circulant matrices. We show that in a small sparsity regime and for small enough accuracy @math , @math measurements suffice to reconstruct the direction of any @math -sparse vector up to accuracy @math via an efficient program. We derive this result by proving that partial Gaussian circulant matrices satisfy an @math RIP-property. Under a slightly worse dependence on @math , we establish stability with respect to approximate sparsity, as well as full vector recovery results. Hoeffding's U-statistics model combinatorial-type matrix parameters (appearing in CS theory) in a natural way. This paper proposes using these statistics for analyzing random compressed sensing matrices, in the non-asymptotic regime (relevant to practice). The aim is to address certain pessimisms of worst-case restricted isometry analyses, as observed by both Blanchard and Dossal, We show how U-statistics can obtain average-case analyses, by relating to statistical restricted isometry property (StRIP) type recovery guarantees. However unlike standard StRIP, random signal models are not required; the analysis used here holds in the almost sure (probabilistic) sense. For Gaussian bounded entry matrices, we show that both @math -minimization and LASSO essentially require on the order of @math measurements to respectively recover at least @math fraction, and @math fraction, of the signals. Noisy conditions are considered. Empirical evidence suggests our analysis to compare well to Donoho and Tanner's recent large deviation bounds for @math -equivalence, in the regime of block lengths @math with high undersampling ( @math measurements); similar system sizes are found in recent CS implementation. In this work, it is assumed throughout that matrix columns are independently sampled.