使用Givens旋转的快速主成分提取方法

需积分: 10 60 浏览量更新于2024-09-09 收藏 579KB PDF 举报

"这篇论文提出了一种快速主成分分析（PCA）的新方法，利用Givens旋转进行高效计算。这种方法称为PC-OPAST，旨在精确提取和跟踪正定Hermitian协方差矩阵的主要特征向量，而不仅仅是随机基础的主子空间。它保证了在每次迭代时权重矩阵的正交性，并且具有较低的计算复杂度。" 正文: 在信号处理和数据分析领域，主成分分析(PCA)是一种常用的技术，用于降维和发现数据集中的主要结构。PCA通过找到数据协方差矩阵的特征向量来实现这一目标，这些特征向量对应于最大的特征值，代表了数据的最大变化方向。然而，传统PCA的计算成本较高，特别是对于大规模数据集。该文"Fast Principal Component Extraction Using Givens Rotations"提出了PC-OPAST算法，这是一种优化的PCA实现，它使用Givens旋转来降低计算复杂度。Givens旋转是一种线性代数操作，通过一系列简单的算术运算（乘法、除法和平方根）来旋转数据矩阵的行或列，从而改变其特定元素，这在保持矩阵正交性的前提下，可以有效地近似进行矩阵的QR分解。 PC-OPAST算法的关键优势在于它不仅追踪主子空间的随机基，还能精确估计协方差矩阵的主要特征向量。这意味着它可以更准确地捕捉数据的主要模式，这对于许多应用，如模式识别、图像处理和金融数据分析，都是至关重要的。此外，PC-OPAST在每次迭代时都保证了权重矩阵的正交性，这有助于保持解的质量和稳定性。算法的计算复杂度为O(n^2)，其中n是观测向量的大小，而要估计的特征向量的数量为k。这个复杂度相比传统的PCA算法（如幂迭代或奇异值分解SVD）显著降低，使得PC-OPAST更适合处理大数据和实时监控场景。论文通过仿真结果展示了PC-OPAST的估计精度和跟踪性能，并将其与著名的Singular Value Decomposition (SVD)方法进行了比较。SVD是最常用的PCA实现之一，但其计算成本较高。相比之下，PC-OPAST在保持性能的同时，提供了更快的计算速度。总结来说，"Fast Principal Component Extraction Using Givens Rotations"提供了一种创新的PCA实现，通过Givens旋转实现了高效的特征向量提取和跟踪，尤其适用于需要实时处理和分析大型数据集的应用。这种算法的出现为高效率和低复杂度的PCA计算开辟了新的途径，对未来的数据分析和信号处理研究具有重要意义。

IEEE SIGNAL PROCESSING LETTERS, VOL. 15, 2008 369

Fast Principal Component Extraction

Using Givens Rotations

S. Bartelmaos and K. Abed-Meraim

Abstract—In this letter, we elaborate a new version of the orthog-

onal projection approximation and subspace tracking (OPAST)

for the extraction and tracking of the principal eigenvectors of a

positive Hermitian covariance matrix. The proposed algorithm re-

ferred to as principal component OPAST (PC-OPAST) estimates

the principal eigenvectors (not only a random basis of the principal

subspace as for OPAST) of the considered covariance matrix. Also,

it guarantees the orthogonality of the weight matrix at each itera-

tion and requires

( )

ﬂops per iteration, where is the size of

the observation vector and

is the number of eigenvectors

to estimate. (The number of ﬂops per iteration represents the total

number of multiplication, division, and square root operations that

are required to extract the desired eigenvectors at each iteration.)

The estimation accuracy and tracking properties of PC-OPAST

are illustrated through simulation results and compared with the

well-known singular value decomposition (SVD) method and other

recently proposed PCA algorithms.

Index Terms—Fast adaptive algorithms, Givens rotations, prin-

cipal component analysis (PCA).

I. INTRODUCTION

RINCIPAL component analysis (PCA) and principal

subspace analysis (PSA), as feature extraction techniques,

have been widely used in many modern information processing

ﬁelds such as: telecommunication, adaptive ﬁltering, antenna

array processing, statistical parameter estimation, neural net-

works, etc. The main difference between the PSA (e.g., [1],

[2]) and the PCA is that the latter requires the estimation of

the eigenvectors of the covariance matrix of an input vector

sequence while the former (PSA) estimates only a basis of

the principal subspace. The conventional matrix algebraic ap-

proaches, which include singular value decomposition (SVD)

of the data matrix, are often unsuitable for large dimensional

input data as well as for the adaptive PCA due to their high

computational load. Hence, seeking fast, online algorithms to

compute adaptively the PCA is an ongoing research topic in

signal processing and communications. As shown in [6], the

PCA method may be grouped in two categories: sequential and

parallel versions. In the ﬁrst group [4], [7], the implementation

is based on the deﬂation technique. The basic idea of the deﬂa-

tion is the sequential estimation of the principal components.

First the most dominant eigenvector is updated by applying a

Manuscript received May 29, 2007; revised July 26, 2007. The associate ed-

itor coordinating the review of this manuscript and approving it for publication

was Dr. Ivan W. Selesnick.

The authors are with the TSI Department, Telecom Paris, 75014 Paris, France

(e-mail: bartelmaos@tsi.enst.fr; abed@tsi.enst.fr).

Color versions of one or more of the ﬁgures in this paper are available online

at http://ieeexplore.ieee.org.

Digital Object Identiﬁer 10.1109/LSP.2008.920006

subspace algorithm with

. Then we remove the projection

of the current data vector

onto this eigenvector from

itself. Thus, the second dominant eigenvector can be extracted

in the same way as it becomes the most dominant one in the

updated data vector. This process is repeated

times to extract

the

dominant eigenvectors. In the parallel version, the de-

sired principal components are extracted simultaneously. The

parallel version has been studied extensively [3], [5], [6], [8]

since it overcomes the drawbacks of the sequential version that

makes use of a large amount of memory to store the repeatedly

used input samples, and it produces a long processing delay due

to the extraction of the desired components one after another.

In this letter, we propose to modify the subspace tracking

tracking algorithm orthogonal projection approximation sub-

space tracking (OPAST) [1] in order to perform the PCA while

preserving the same linear complexity as OPAST. This modi-

ﬁcation is accomplished by the use of Givens rotations which

allow us to transform the principal subspace matrix obtained

by the OPAST algorithm into the desired principal component

matrix. We present some simulation results to assess the perfor-

mance of our algorithm and compare it with the well-known and

efﬁcient SVD method and other recently proposed fast PCA al-

gorithms [6], [8].

II. PC-OPAST A

LGORITHM

Let

be a sequence of random vectors with covari-

ance matrix

. Consider the problem of ex-

tracting

principal eigenvectors of the covariance matrix.

To solve this problem, several principal component algorithms

have so far been proposed as these following adaptive methods

[3]–[6], [8].

Let us start by presenting the OPAST algorithm for PSA. For

that, consider the scalar function

(1)

with a matrix argument

. Here, denotes the

trace of a square matrix

and is the Frobenus norm. It is

shown in [4] that

•

is a stationary point of if and only if

, where is a matrix containing any distinct

eigenvectors of

, and is any unitary matrix.

• All stationary points of

are saddle points, except

when

contains the dominant eigenvectors of .In

that case,

attains the global minimum.

下载后可阅读完整内容，剩余3页未读，立即下载

welcome8793

粉丝: 0
资源: 4

使用Givens旋转的快速主成分提取方法

分享自己做的主成份分析的GUI含原文件-GUI of Principal component analysis using MALAB.rar

Application of Principal Component Extraction Technique in Processing Cloud Images

Principal component analysis or kernel principal component analysis based joint spectral subspace method for calibration transfer

Two-Dimensional Color Uncorrelated Principal Component Analysis for Feature Extraction with Application to Face Recognition

PCA.rar_Principal-component_principal component

Principal component Analysis

Principal Component Analysis / Hebbian-based Max Eigenfilter: Principal Component Analysis and Hebbian-based Maximum Eigenfilter-matlab开发

Bayesian Fault Diagnosis Using Principal Component Analysis Approach with Continuous Evidence

risk parity stock optimization using principal component quantile simulation.pdf

Statistical evaluation of the tissue specified specific absorption rate using principal component regression

最新资源