  Compressed sensing (CS) involves sampling signals at rates less than their
Nyquist rates and attempting to reconstruct them after sample acquisition. Most
such algorithms have parameters, for example the regularization parameter in
LASSO, which need to be chosen carefully for optimal performance. These
parameters can be chosen based on assumptions on the noise level or signal
sparsity, but this knowledge may often be unavailable. In such cases, cross
validation (CV) can be used to choose these parameters in a purely data-driven
fashion. Previous work analysing the use of CV in CS has been based on the
$\ell_2$ cross-validation error with Gaussian measurement noise. But it is well
known that the $\ell_2$ error is not robust to impulse noise and provides a
poor estimate of the recovery error, failing to choose the best parameter. Here
we propose using the $\ell_1$ CV error which provides substantial performance
benefits given impulse measurement noise. Most importantly, we provide a
detailed theoretical analysis and error bounds for the use of $\ell_1$ CV error
in CS reconstruction. We show that with high probability, choosing the
parameter that yields the minimum $\ell_1$ CV error is equivalent to choosing
the minimum recovery error (which is not observable in practice). To our best
knowledge, this is the first paper which theoretically analyzes $\ell_1$-based
CV in CS.
