Forward adaptive transform coding requires a codebook of transform matrices from which the best transform can be chosen for each macroblock in an image. Codebook construction involves designing a vector quantizer for a sample set of KarhunenLoeve transform (KLT) matrices. While several approaches to designing such matrix codebooks have been proposed in previous work [1] , [2] , these non-parametric methods carry out matrix quantization in very high dimensional spaces which can suffer from the curse of dimensionality. Furthermore, the resulting transform matrices are not scalable - if multiple transform block sizes are to be used, such as in video compression, a separate matrix codebook must be designed for each block size.

We present a novel algorithm for designing a transform codebook for adaptive transform coding a non-stationary source, where the codebook contains a set of or-thonormal transform matrices. The non-stationary source is modeled by a block-wise (locally) stationary process so that all vectors in a given block can be coded using a single transform-matrix chosen from the codebook. The transform-matrix codebook is designed such that the mean-square error (MSE) of coding locally stationary blocks, averaged over the ensemble of blocks (AMSE) is minimized. First, a sequence of training vectors from the non-stationary source (such as blocks of pixels extracted from images) is segmented into locally stationary blocks of vectors. Our design algorithm starts with an initial codebook and iteratively updates the codebook for the training set, similar to the well-known generalized Lloyd algorithm for vector quantizer design. Each iteration consists of two steps: 1) the training set is partitioned into subsets by encoding the training set using the current transform codebook, and 2) the code-book is updated by computing a centroid transform-matrix for each subset. A major difference compared to the standard Lloyd algorithm however is the requirement to enforce an orthonormality constraint on the matrices in the codebook during the computation of centroids. This is accomplished by mapping the constrained problem in Euclidean space to an unconstrained problem on the Stiefel manifold. Gradient-descent on the Stiefel manifold is then used to compute the centroids. Essential to the implementation of manifold gradient-descent is an expression for the AMSE which is differentiable with respect to the transform matrix. Towards this end, we present two expressions whose matrix derivatives can be analytically obtained: 1) an approximate high-rate expression assuming Gaussian distributed source vectors, and 2) an exact finite-rate expression assuming Laplace distributed transform coefficients.