The emerging area of Compressed Sensing revolves around the surprising fact that underdetermined linear systems of the form Ax = y can be efficiently solved if x is known a priori to be sufficiently sparse, that is, to have sufficiently small support. Most real world signals x are not exactly sparse, but rather approximately sparse, in which case only an approximation to the underlying signal x satisfying Ax = y can be found in general. In this talk, we will show how cross validation-type techniques used in statistics and learning theory naturally apply in the Compressed Sensing setup and offer very efficient tight bounds on the root mean squared error ||x - x*|| between the approximation x* and underlying signal x. Cross Validation techniques can be used for parameter selection in Compressed Sensing as well.