基于QR分解的主成分分析外文翻译资料

英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料

基于QR分解的主成分分析

摘要

本文提出了基于QR的主成分分析(PCA)方法。与基于奇异值分解(SVD)的PCA方法相似，该方法具有数值稳定性。我们进行了分析比较和数值比较(在Matlab软件上)，以研究我们的方法的性能(从计算复杂度)。研究表明，基于QR的主成分分析方法在计算复杂度上具有更高的实用性。

关键字

主成分分析；奇异值分解；QR分解；计算复杂度；

1.导言

主成分分析(PCA)是一种重要的降维技术，已应用于模式分类和数据表示领域。它以无监督的方式对训练数据 进行工作，其中d是数据的维数。对于单个特征向量，它不需要类标签。

在常规PCA过程中，形成一个协方差矩阵 (其中并且是训练数据的质心)，并对其进行特征值分解(EVD)以提取与h (ht其中t为H的秩)个主特征值相对应的特征向量(即那些具有最大相关特征值的特征向量或H)。h的值介于[1，t]之间，表示降维空间的维数。

在人脸识别和生物识别领域的许多应用中，维数d大于训练样本数n，它们被称为“小样本问题”[2，7，9，13，16-19，21，22]。在这样的问题中，协方差矩阵的大小为，这将是计算该矩阵的EVD的一个缓慢的过程(需要很大的计算机功率)。然而，FUUNAGA[5]给出了一种快速实现EVD的方法，并在模式识别文献中得到了广泛的应用。在某些应用[3、4、10-12、14、15]中也使用了一些快速但精度有限的其他方法来获取特征向量。正如Fukunaga[5]所解释的那样，的EVD是对 (的特征值和特征向量进行的。然而，这种方法存在一个问题，即它在数值上是不稳定的。这是因为矩阵的形成可能会失去精度(如[6]，236页所示)。由于硬件采用了一种并行算法，所以当方阵HTH形成方阵H中的一个小的十进制值时，它的数值可能会低于硬件的精度极限。这意味着矩阵的形成将失去一个级别或其他信息。由于上述两个原因(计算复杂性和精度)，没有对大尺寸协方差矩阵进行特征值分析，而是直接对矩形矩阵H[20]进行奇异值分解(SVD)。然而，这种基于奇异值分解(SVD)的方法的计算复杂度仍然很高(约为个零运算点)。

在化学计量学文献中，提出了一种快速计算主成分分析的方法，但计算精度有限。例如，延迟基矩阵乘法(PBM)-主成分分析方法已被提出[1，8]。该策略不直接处理数据矩阵X，但是它假设数据矩阵X首先分解为三个矩阵：C、和，其中。矩阵和是B样条基集，因此，需要事先计算才能得到这些矩阵。其次，仅仅是实际数据矩阵X的近似值，因此它的精度不是很高。在本文中，我们的目标是推导出计算效率和数值稳定的主成分分析方法。为了使它计算稳定，我们使用矩阵H；为了使它计算有效，我们使用QR分解。基于QR的主成分分析方法大约只需要个次运算。因此，该方法在数值上是稳定的，而且比基于奇异值分解的主成分分析方法具有更高的计算复杂度。

2.主成分分析

采用PCA变换将d维特征向量转化为h维特征向量。它还可用于从h维特征向量中重建出具有一定精度的三维特征向量，即重建误差。在主成分分析中，这种重建误差在均方误差(MSE)意义上是最小的。极小化的变换矩阵满足，其中是协方差矩阵，是特征值，是对应于的特征向量(i =1,2,3,hellip;,h)。的列向量是主要的特征向量，即这些特征向量对应于最大的特征值。

协方差矩阵是一个对称矩阵，它可以表示为。若维数很大()，则的EVD计算成为一个缓慢的过程。在这种情况下，一种经济的方法是计算的EVD，而不是。然而，的形成可能导致信息的丢失[6]。更准确可靠的方法是利用H的SVD，给出的特征向量和平方根特征值。这需要大约的非常规操作。在许多应用程序中，需要更快但准确的实现。第二节介绍了基于QR分解的PCA方法，该方法与基于奇异值分解的PCA方法相似，能够以数值稳定的方式提取的特征向量和平方根特征值。然而，与基于奇异值分解的主成分分析方法相比，该方法的计算复杂度要低得多。

3.基于QR分解的PCA方法

本节介绍了基于QR的PCA方法。该方法使用矩阵（其中d n）以数值稳定的方式执行=的EVD。 让的秩为t，其中1tn。 矩阵可以分解为正交矩阵和上三角矩阵，使用QR分解：

=

由于 = ，我们得到：

=

矩阵可以通过SVD分解为：

=

其中 和是正交矩阵， 是一个对角矩阵。 用方程 （10）方程（11），我们得到：

=

或 =

或 =

其中=。

由于，变换是一个正交矩阵。 该正交变换也使矩阵对角化。即变换确实是一个特征向量矩阵，是一个的特征值矩阵。

设（其中，）是一个矩阵，它包含的h列向量，对应于的最大h对角项，则PCA变换将是。 基于QR的PCA方法总结在表1中。

基于QR的主成分分析方法的计算复杂度可描述如下。矩形矩阵上的经济QR分解需要 次运算(如果使用Modi的Gram-Schmidt QR方法)或 次运算(如果使用快速Givens QR方法或Householder QR方法)[6]。到对角矩阵、和正交矩阵的经济SVD要求次运算[6]。最后，和的乘法需要第次运算。表2总结了该方法的计算复杂性。

从表2可以看出，如果维数d与样本数n(即)相比非常大，则估计的总计算复杂度为。在特殊情况下，如果只需要一个主特征向量，则计算复杂度约为。

4.实验

基于QR以及基于SVD的PCA方法使用H来计算=的EVD。因此，它们都是数值稳定的。在本节中，我们将这些方法的计算复杂性进行比较。为此，我们生成3000个样本的数据，可变维数从5,000到10,000。数据的等级被设置为1,000。h的值设置为10，图1a显示了基于QR的PCA和基于SVD的PCA方法之间的分析比较。图1b显示了在Matlab软件上实现它们的CPU时间的数值比较。从图中可以看出，所提出的方法在计算上更有效。无论是解析的还是Matlab的，都比基于奇异值分解的主成分分析方法更有效.。另外，基于SVD的PCA方法和基于QR的PCA方法的cpu比率接近于其理论测量值的比率。该方法的计算优势主要来源于利用协方差矩阵的QR分解。QR分解过程将矩阵H分解为正交矩阵和上三角矩阵。此后，可以对上三角矩阵应用SVD过程来计算特征向量。与直接在矩形矩阵H上使用SVD相比，这是一个较快的过程。与基于SVD的PCA方法相比，基于QR的PCA方法的计算有效性对于低秩矩阵H特别重要。

5.总结

本文介绍了一种基于QR的PCA方法。像基于SVD的PCA方法一样，该方法使用H来表示 =的EVD，实现了数值稳定性。 本文提出的方法在计算复杂度方面优于基于SVD的PCA方法。由于计算有效的降维方法在许多研究领域中是至关重要的，因此可以设想基于QR的PCA方法的许多应用。 例如，它可以应用于人脸识别问题[28,29]，属性约简[30]，决策树归纳[31,32]和生物识别应用[33,34]。

图1

参考文献

1. Alsberg BK, Kvalheim OM (1994) Speed improvement of multivariate algorithms by the method of postponed basis matrix multiplication Part I. Principal component analysis. Chemom Intell Lab Syst 24:31–42

2. Belhumeur PN, Hespanha JP, Kriegman DJ (1997) Eigenfaces vs. fisherfaces: recognition using class specific linear projection. IEEE T PAMI 19(7):711–720

3. Chen T-C, Chen K, Liu W, Chen L-G (2009) One-chip principal component analysis with a mean pre-estimation method for spike sorting. In: Proceedings of IEEE international symposium on circuits and systems, pp 3310–3113

4. Chen T-C, Liu W, Chen L-G (2008) VLSI architecture of leading eigenvector generation for on-chip principal component analysis spike sorting system. In: Proceedings of 30th Annual International Conference IEEE engineering in medicine and biology society EMBSrsquo;08, pp 3192–3195

5. Fukunaga K (1990) Introduction to Statistical Pattern Recognition. Academic Press, USA

6. Golub GH, Loan CFV (1996) Matrix Computations. The John Hopkins University Press, Baltimore

7. Jian H, Yuen PC, Wen-Sheng C (2004) A novel subspace LDA algorithms for recognition of face images with illumination and pose variations. Proc Int Conf Mach Learn Cybern 6:3589– 3594

8. Kiers HAL, Harshman RA (1997) Relating two proposed methods for speed up of algorithms for fitting two- and three- way principal component and related multilinear models. Chemom Intell Lab Syst 36:31–40

9. Paliwal KK, Sharma A (2010) Improved direct LDA and its application to DNA microarray gene expression data. Pattern Recogn Lett 31:2489–2492

10. Roweis S (1997) EM Algorithms for PCA and SPCA. Neural Inf Process Syst 10:626–632

11. Sajid I, Ahmed MM, Taj I (2008) Design and implementation of a face recognition system using fast PCA. In: Proceedings of the International Symposium on Computer Science and its Applications CSA, pp 126–130

12. Schilling RJ, Harris SL (2000) Applied Numerical Methods for Engineers Using Matlab and C. Brooks/Cole Publishing, Boston

13. Sharma A, Paliwal KK (2010) Regulari

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[23527]，资料为PDF文档或Word文档，PDF文档可免费转换为Word