Compressed Sensing with Cross Validation

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.