A necessary and sufficient condition for transform optimality in source coding

It is well-known for transform coding of multivariate Gaussian sources, that the Karhunen Loeve transform (KLT) minimizes the mean square error distortion. However, finding the optimal transform for general non-Gaussian sources has been an open problem for decades, despite several important advances that provide some partial answers regarding KLT optimality. In this paper, we present a necessary and sufficient condition for optimality of a transform when high resolution, variable rate quantizers are employed. We present not only a complete characterization of when KLT is optimal, but also a determining condition for optimality of a general (non-KLT) transform. This necessary and sufficient condition is shown to have direct connections to the well studied source separation problem. This observation can impact source separation itself, as illustrated with a new optimality result. Finally, we combine the transform optimality condition with algorithmic tools from source separation, to derive a practical numerical method to search for the optimal transform in source coding.