  We study a new class of codes for lossy compression with the squared-error
distortion criterion, designed using the statistical framework of
high-dimensional linear regression. Codewords are linear combinations of
subsets of columns of a design matrix. Called a Sparse Superposition or Sparse
Regression codebook, this structure is motivated by an analogous construction
proposed recently by Barron and Joseph for communication over an AWGN channel.
For i.i.d Gaussian sources and minimum-distance encoding, we show that such a
code can attain the Shannon rate-distortion function with the optimal error
exponent, for all distortions below a specified value. It is also shown that
sparse regression codes are robust in the following sense: a codebook designed
to compress an i.i.d Gaussian source of variance $\sigma^2$ with
(squared-error) distortion $D$ can compress any ergodic source of variance less
than $\sigma^2$ to within distortion $D$. Thus the sparse regression ensemble
retains many of the good covering properties of the i.i.d random Gaussian
ensemble, while having having a compact representation in terms of a matrix
whose size is a low-order polynomial in the block-length.
