  Compressed Sensing decoding algorithms can efficiently recover an N
dimensional real-valued vector x to within a factor of its best k-term
approximation by taking m = 2klog(N/k) measurements y = Phi x. If the sparsity
or approximate sparsity level of x were known, then this theoretical guarantee
would imply quality assurance of the resulting compressed sensing estimate.
However, because the underlying sparsity of the signal x is unknown, the
quality of a compressed sensing estimate x* using m measurements is not
assured. Nevertheless, we demonstrate that sharp bounds on the error || x - x*
||_2 can be achieved with almost no effort. More precisely, we assume that a
maximum number of measurements m is pre-imposed; we reserve 4log(p) of the
original m measurements and compute a sequence of possible estimates
(x_j)_{j=1}^p to x from the m - 4log(p) remaining measurements; the errors ||x
- x*_j ||_2 for j = 1, ..., p can then be bounded with high probability. As a
consequence, numerical upper and lower bounds on the error between x and the
best k-term approximation to x can be estimated for p values of k with almost
no cost. Our observation has applications outside of compressed sensing as
well.
