Repository logo
 

The Rate-Distortion Function and Excess-Distortion Exponent of Sparse Regression Codes with Optimal Encoding

Accepted version
Peer-reviewed

Loading...
Thumbnail Image

Type

Article

Change log

Authors

Venkataramanan, Ramji  ORCID logo  https://orcid.org/0000-0001-7915-5432
Tatikonda, Sekhar 

Abstract

This paper studies the performance of sparse regression codes for lossy compression with the squared-error distortion criterion. In a sparse regression code, codewords are linear combinations of subsets of columns of a design matrix. It is shown that with minimum-distance encoding, sparse regression codes achieve the Shannon rate-distortion function for i.i.d. Gaussian sources R∗(D) as well as the optimal excess-distortion exponent. This completes a previous result which showed that R∗(D) and the optimal exponent were achievable for distortions below a certain threshold. The proof of the rate-distortion result is based on the second moment method, a popular technique to show that a non-negative random variable X is strictly positive with high probability. In our context, X is the number of codewords within target distortion D of the source sequence. We first identify the reason behind the failure of the standard second moment method for certain distortions, and illustrate the different failure modes via a stylized example. We then use a refinement of the second moment method to show that R∗(D) is achievable for all distortion values. Finally, the refinement technique is applied to Suen's correlation inequality to prove the achievability of the optimal Gaussian excess-distortion exponent.

Description

Keywords

cs.IT, cs.IT, math.IT, math.ST, stat.TH

Journal Title

IEEE Transactions on Information Theory, Vol. 63, no. 8, pp. 5228-5243 (August 2017)

Conference Name

Journal ISSN

0018-9448
1557-9654

Volume Title

63

Publisher

Institute of Electrical and Electronics Engineers (IEEE)
Sponsorship
European Commission (631489)