Lossy compression via sparse linear regression: Computationally efficient encoding and decoding

We study a new class of codes for lossy compression with the squared-error distortion crite-rion, 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 Superposi-tion 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 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 de-signed to compress an i.i.d Gaussian source of variance σ2 with (squared-error) distortion D can compress any ergodic source of variance less than σ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.