  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.
