One-bit compressed sensing with partial Gaussian circulant matrices

2017/10/09 by Dirksen, Sjoerd, Jung, Hans Christian, Rauhut, Holger
#60B20 #94A20 #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR)

paper · doi:10.48550/arxiv.1710.03287

Abstract

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 δ, m∼ δ^-4 slog(N/sδ) measurements suffice to reconstruct the direction of any s-sparse vector up to accuracy δ via an efficient program. We derive this result by proving that partial Gaussian circulant matrices satisfy an ℓ₁/ℓ₂ RIP-property. Under a slightly worse dependence on δ, we establish stability with respect to approximate sparsity, as well as full vector recovery results.

Related

• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors
• Circulant and Toeplitz matrices in compressed sensing
• Robust one-bit compressed sensing with partial circulant matrices
• One-bit compressed sensing with non-Gaussian measurements
• One-bit compressed sensing by linear programming