Deterministic Graph Spectral Sparsification

Abstract

An important technique in data analysis is principal component analysis or PCA. Given a covariance matrix S, in PCA we need to compute the eigenvector associated to a greatest eigenvalue of S in order to determine the direction of the so-called principal components [3]. It is well know that computation of eigenvalues of general matrices is expensive, and therefore, several authors use techniques of numerical approximation [5]. Furthermore, computations are more efficient whenever the matrices are sparse.