Summary: Suppose \(x\) is an unknown vector in \(\mathbb R^m\) (a digital image or signal); we plan to measure \(n\) general linear functionals of \(x\) and then reconstruct. If \(x\) is known to be compressible by transform coding with a known transform, and we reconstruct via the nonlinear procedure defined here, the number of measurements \(n\) can be dramatically smaller than the size \(m\). Thus, certain natural classes of images with \(m\) pixels need only \(n=O(m^{1/4}\log^{5/2}(m))\) nonadaptive nonpixel samples for faithful recovery, as opposed to the usual \(m\) pixel samples. More specifically, suppose \(x\) has a sparse representation in some orthonormal basis (e.g., wavelet, Fourier) or tight frame (e.g., curvelet, Gabor) -- so the coefficients belong to an \(\ell^p\) ball for \(0