Lossy Compression via Sparse Regression Codes: Generalized Construction and Finite-length Bounds
2026-08-14 • Information Theory
Information Theory
AI summaryⓘ
The authors study special types of codes called sparse regression codes (SPARCs) used for compressing data with some loss in quality. They look at simple ways to encode data using these codes and generalize the approach to a broader class called additive orthogonal regression codes. By analyzing how errors change during encoding, they find precise bounds on the compression quality and show how distributing power carefully among code parts helps reduce errors. This leads to better compression performance for practical versions of these codes with lower complexity.
Sparse regression codesLossy compressionEncoding algorithmsSquared-error distortionPower allocationAdditive orthogonal codesFinite-length performanceCompression boundsGreedy encoding
Authors
Galen Reeves, Ramji Venkataramanan
Abstract
We study sparse regression codes (SPARCs) for lossy compression under simple greedy encoding rules, including both correlation-based and distance-based methods. We generalize the SPARC construction, and consider the class of \emph{additive orthogonal} regression codes, of which standard SPARCs are a special case. For this class of codes, we derive nonasymptotic bounds on the squared-error distortion by tracking the evolution of the encoding residual across stages. Our results highlight the role of power allocation in controlling the distortion, allowing us to optimize the allocation based on the parameters of the code. The optimized allocation improves the finite-length compression performance of SPARCs, and our bounds provide distortion guarantees for lower complexity variants of SPARCs, like signed SPARCs and $K$-sparse SPARCs.