Record Details

Lossy Compression via Sparse Linear Regression: Computationally Efficient Encoding and Decoding

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Lossy Compression via Sparse Linear Regression: Computationally Efficient Encoding and Decoding
 
Creator VENKATARAMANAN, R
SARKAR, T
TATIKONDA, S
 
Subject Lossy compression
computationally efficient encoding
squared error distortion
Gaussian rate-distortion
sparse regression
compressed sensing
RATE-DISTORTION
SUCCESSIVE REFINEMENT
SUPERPOSITION CODES
FIDELITY-CRITERION
ERROR EXPONENT
ALGORITHMS
DICTIONARIES
QUANTIZATION
INFORMATION
LATTICE
 
Description We propose computationally efficient encoders and decoders for lossy compression using a sparse regression code. The codebook is defined by a design matrix and codewords are structured linear combinations of columns of this matrix. The proposed encoding algorithm sequentially chooses columns of the design matrix to successively approximate the source sequence. It is shown to achieve the optimal distortion-rate function for independent identically distributed (i.i.d) Gaussian sources under the squared-error distortion criterion. For a given rate, the parameters of the design matrix can be varied to tradeoff distortion performance with encoding complexity. An example of such a tradeoff as a function of the block length n is the following. With computational resource (space or time) per source sample of O((n/log n)(2)), for a fixed distortion-level above the Gaussian distortion-rate function, the probability of excess distortion decays exponentially in n. The sparse regression code is robust in the following sense: for any ergodic source, the proposed encoder achieves the optimal distortion-rate function of an i.i.d Gaussian source with the same variance. Simulations show that the encoder has good empirical performance, especially at low and moderate rates.
 
Publisher IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
 
Date 2014-12-28T14:16:48Z
2014-12-28T14:16:48Z
2014
 
Type Article
 
Identifier IEEE TRANSACTIONS ON INFORMATION THEORY, 60(6)3265-3278
0018-9448
1557-9654
http://dx.doi.org/10.1109/TIT.2014.2314676
http://dspace.library.iitb.ac.in/jspui/handle/100/16730
 
Language English