We study minimax mean-squared error of sparse signal recovery from noisy
linear measurements -- the minimum is over all possible recovery algorithms and
the maximum is over all vectors obeying a sparsity constraint. This quantity
characterizes the robustness of compressed sensing to signal uncertainty and its
analysis provides insights about optimal recovery procedures and worst-case
distributions. We show how the minimax behavior can be analyzed in terms of a
related scalar estimation problem; we discuss connections with robust estimation
and the performance of greedy algorithms;  and we derive a non-asymptotic upper
bound. One consequence is that the Bayes optimal phase
transitions of Wu and Verdu can be obtained uniformly over the class of all
sparse vectors.