K-L 转换

K-L转换(Karhunen-Loève Transform)是建立在统计特性基础上的一种转换，它是均方差(MSE, Mean Square Error)意义下的最佳转换，因此在资料压缩技术中占有重要的地位。

K-L转换名称来自Kari Karhunen和Michel Loève。

K-L转换是对输入的向量x，做一个正交变换，使得输出的向量得以去除数据的相关性。

然而，K-L转换虽然具有均方差(MSE)意义下的最佳转换，但必须事先知道输入的讯号，并且需经过一些繁杂的数学运算，例如协方差(covariance)以及特征向量(eigenvector)的计算。因此在工程实践上K-L转换并没有被广泛的应用，不过K-L转换是理论上最佳的方法，所以在寻找一些不是最佳、但比较好实现的一些转换方法时，K-L转换能够提供这些转换性能的评价标准。

以处理图片为范例，在K-L转换途中，图片的能量会变得集中，有助于压缩图片，但是实际上，KL转算为input-dependent，即需要对每张输入图片存下一个转换机制，每张图都不一样，这在实务应用上是不实际的。

KL转换属于正交转换，其处输入讯号的原理如下：

对输入向量${\displaystyle \mathbf{x}}$做KL传换后，输出向量${\displaystyle \mathbf{X}}$之元素间(${\displaystyle u_1\ne <!--\; \ne \; -->u_2}$, ${\displaystyle u_1}$和${\displaystyle u_2}$为${\displaystyle \mathbf{X}}$之元素的index)的相关性为零，即：${\displaystyle E-<!--\; -\; -->\stackrel{¯<!--\; ¯\; -->}{X})(X-<!--\; -\; -->\stackrel{¯<!--\; ¯\; -->}{X})]=0}$

展开上式并做消去：

${\displaystyle EX]-<!--\; -\; -->\stackrel{¯<!--\; ¯\; -->}{X}\stackrel{¯<!--\; ¯\; -->}{X}=0}$

如果${\displaystyle \stackrel{¯<!--\; ¯\; -->}{x}=0}$，因为KL转换式线性转换的关系，${\displaystyle \stackrel{¯<!--\; ¯\; -->}{X}=0}$，则可以达成以下式，所以这里得输入向量${\displaystyle \mathbf{x}}$之平均值${\displaystyle \stackrel{¯<!--\; ¯\; -->}{x}}$需为${\displaystyle 0}$，所以KLT是专门用于随机程序的分析：

${\displaystyle EX]=0}$

其中${\displaystyle u_1\ne <!--\; \ne \; -->u_2}$，即输出向量不同元素相关性为${\displaystyle 0}$。

回到矩阵表示形式，令${\displaystyle \mathbf{K}}$为KL转换矩阵，使：

${\displaystyle \mathbf{X}=\mathbf{K}\mathbf{x}}$

以${\displaystyle \mathbf{K}}$和${\displaystyle \mathbf{x}}$表示${\displaystyle \mathbf{X}}$之covariance矩阵：

${\displaystyle E=E=\mathbf{K}E{\mathbf{K}}^T}$

因为${\displaystyle \stackrel{¯<!--\; ¯\; -->}{x}=0}$，${\displaystyle E}$直接等于covariance矩阵：

${\displaystyle E=\mathbf{K}\mathbf{C}{\mathbf{K}}^T}$

其中${\displaystyle \mathbf{C}}$为${\displaystyle \mathbf{x}}$之covariance矩阵。

如果要使${\displaystyle EX]=0}$，则${\displaystyle E}$必须为对角线矩阵，即对角线上之值皆为${\displaystyle 0}$，所以${\displaystyle \mathbf{K}}$必须将传换成对角线矩阵，即${\displaystyle \mathbf{K}}$的每一行皆为${\displaystyle \mathbf{C}}$之特征向量。

K-L转换的目的是将原始数据做转换，使得转换后资料的相关性最小。若输入数据为一维：

${\displaystyle y=\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}Kx}$

${\displaystyle K=e_n}$

其中e_n为输入讯号x共变异数矩阵(covariance matrix)C_x的特征向量(eigenvector)

若输入讯号x为二维：

${\displaystyle y=\underset{m=0}{\overset{M-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}KKx}$

KLT和Principle component analysis (PCA)有相似的特性，二者之间有很细微的差异，其中KLT专门处理随机性的讯号，但PCA则没有这个限制。对PCA而言，这里假设输入讯号为ㄧ向量，输入向量${\displaystyle \mathbf{x}}$在乘上转换矩阵${\displaystyle \mathbf{W}}$之前，会先将输入向量扣去平均值，即:

${\displaystyle \mathbf{X}=\mathbf{W}(\mathbf{x}-<!--\; -\; -->\stackrel{¯<!--\; ¯\; -->}{x})}$

PCA会根据${\displaystyle \mathbf{x}}$之covariance矩阵来选择特征向量做为转换矩阵之内容：

${\displaystyle E={\mathbf{W}\mathbf{\Lambda <!--\; \Lambda \; -->}\mathbf{W}}^T}$

其中${\displaystyle \mathbf{\Lambda <!--\; \Lambda \; -->}}$为对角线矩阵且对角线值为特征值。

由上述可见PCA和KLT之差异在于有没有减去平均值，这是由于输入资料分布的限制造成的，当输入向量支平均值为零时，二这者没有差异。

在影像的压缩上，目的是要将原始的影像档用较少的资料量来表示，由于大部分的影像并不是随机的分布，相邻的像素(Pixal)间存在一些相关性，如果我们能找到一种可逆转换(reversible transformation)，它可以去除数据的相关性，如此一来就能更有效地储存资料，由于K-L转换是一种线性转换，并有去除资料相关性的特性，便可以将它应用在影像的压缩上。此外，由于K-L转换具有将讯号转到特征空间(eigenspace)的特性，因此也可以应用在人脸辨识上。

1. Ding, J. J. (2017). Advanced Digital Signal Processing http://djj.ee.ntu.edu.tw/ADSP8.pdf

2. Gerbrands, J.J., On the relationships between SVD, KLT, and PCA, Pattern Recogn., 14 (1981), pp. 375-381