Two-Part Reconstruction with Noisy-Sudocodes

Abstract

We develop a two-part reconstruction framework for signal recovery in compressed sensing (CS), where a fast algorithm is applied to provide partial recovery in Part 1, and a CS algorithm is applied to complete the residual problem in Part 2. Partitioning the reconstruction process into two complementary parts provides a natural trade-off between runtime and reconstruction quality. To exploit the advantages of the two-part framework, we propose a Noisy-Sudocodes algorithm that performs two-part reconstruction of sparse signals in the presence of measurement noise. Specifically, we design a fast algorithm for Part 1 of Noisy-Sudocodes that identifies the zero coefficients of the input signal from its noisy measurements. Many existing CS algorithms could be applied to Part 2, and we investigate approximate message passing (AMP) and binary iterative hard thresholding (BIHT). For Noisy-Sudocodes with AMP in Part 2, we provide a theoretical analysis that characterizes the trade-off between runtime and reconstruction quality. In a 1-bit CS setting where a new 1-bit quantizer is constructed for Part 1 and BIHT is applied to Part 2, numerical results show that the Noisy-Sudocodes algorithm improves over BIHT in both runtime and reconstruction quality.

23 pages, 7 figures, to appear in IEEE Transactions on Signal Processing

References in corpus (8)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• Performance bounds for expander-based compressed sensing in Poisson noise
• Variational Bayesian algorithm for quantized compressed sensing
• Generalized Approximate Message Passing for Estimation with Random Linear Mixing

Cited by in corpus (5)

• A robust parallel algorithm for combinatorial compressed sensing
• HISTORY: An Efficient and Robust Algorithm for Noisy 1-bit Compressed Sensing
• Statistical Physics and Information Theory Perspectives on Linear Inverse Problems
• Performance Trade-Offs in Multi-Processor Approximate Message Passing
• The Hörmander index in the finite-dimensional case