A Caltech Library Service

On the rate-distortion performance and computational efficiency of the Karhunen-Loeve transform for lossy data compression

Feng, Hanying and Effros, Michelle (2002) On the rate-distortion performance and computational efficiency of the Karhunen-Loeve transform for lossy data compression. IEEE Transactions on Image Processing, 11 (2). pp. 113-122. ISSN 1057-7149.

See Usage Policy.


Use this Persistent URL to link to this item:


We examine the rate-distortion performance and computational complexity of linear transforms for lossy data compression. The goal is to better understand the performance/complexity tradeoffs associated with using the Karhunen-Loeve transform (KLT) and its fast approximations. Since the optimal transform for transform coding is unknown in general, we investigate the performance penalties associated with using the KLT by examining cases where the KLT fails, developing a new transform that corrects the KLT's failures in those examples, and then empirically testing the performance difference between this new transform and the KLT. Experiments demonstrate that while the worst KLT can yield transform coding performance at least 3 dB worse than that of alternative block transforms, the performance penalty associated with using the KLT on real data sets seems to be significantly smaller, giving at most 0.5 dB difference in our experiments. The KLT and its fast variations studied here range in complexity requirements from O(n^2) to O(n log n) in coding vectors of dimension n. We empirically investigate the rate-distortion performance tradeoffs associated with traversing this range of options. For example, an algorithm with complexity O(n^3/2) and memory O(n) gives 0.4 dB performance loss relative to the full KLT in our image compression experiments

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:“©2002 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.” Manuscript received January 18, 2000; revised October 3, 2001. This material is based upon work supported in part by the NSF under CAREER Award MIP-9501977, the Intel 2000 program, and the Powell Foundation. The material in this paper was presented in part at the International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Phoenix, AZ, in March 1999. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Joern Osterman. The authors are grateful to the anonymous reviewers for their detailed suggestions and comments.
Subject Keywords:Image compression, Karhunen–Loève transform, optimal transform coding, separable coding, source code design
Issue or Number:2
Record Number:CaltechAUTHORS:FENieeetip02
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1179
Deposited By: Archive Administrator
Deposited On:02 Jan 2006
Last Modified:02 Oct 2019 22:40

Repository Staff Only: item control page