A coding theorem for f-separable distortion measures

Rate-distortion theory is a branch of information theory that provides theoretical foundation for lossy data compression. In this setting, the decompressed data need not match original data exactly; however, it must be reconstructed with a prescribed fidelity, which is modeled by a distortion measure. An ubiquitous assumption in rate-distortion literature is that such distortion measures are separable: that is, the distortion measure can be expressed as an arithmetic average of single-letter distortions. Such set up gives nice theoretical results at the expense of a very restrictive model. Separable distortion measures are linear functions of single-letter distortions; real-world distortion measures rarely have such nice structure. In this work we relax the separability assumption and propose f-separable distortion measures, which are well suited to model non-linear penalties. We prove a rate-distortion coding theorem for stationary ergodic sources with f-separable distortion measures, and provide some illustrative examples of the resulting rate-distortion functions.