A Least-Squares Framework for Component Analysis

Over the last century, Component Analysis (CA) methods such as Principal Component Analysis (PCA), Linear Discriminant Analysis (LDA), Canonical Correlation Analysis (CCA), Locality Preserving Projections (LPP), and Spectral Clustering (SC) have been extensively used as a feature extraction step for modeling, classification, visualization, and clustering. CA techniques are appealing because many can be formulated as eigen-problems, offering great potential for learning linear and nonlinear representations of data in closed-form. However, the eigen-formulation often conceals important analytic and computational drawbacks of CA techniques, such as solving generalized eigen-problems with rank deficient matrices (e.g., small sample size problem), lacking intuitive interpretation of normalization factors, and understanding commonalities and differences between CA methods. This paper proposes a unified least-squares framework to formulate many CA methods. We show how PCA, LDA, CCA, LPP, SC, and its kernel and regularized extensions correspond to a particular instance of least-squares weighted kernel reduced rank regression (LS--WKRRR). The LS-WKRRR formulation of CA methods has several benefits: 1) provides a clean connection between many CA techniques and an intuitive framework to understand normalization factors; 2) yields efficient numerical schemes to solve CA techniques; 3) overcomes the small sample size problem; 4) provides a framework to easily extend CA methods. We derive weighted generalizations of PCA, LDA, SC, and CCA, and several new CA techniques.

1 Introduction

Over the last century, Component Analysis (CA) methods [1] such as Principal Component Analysis (PCA) [2], [3], Linear Discriminant Analysis (LDA) [4], [5], Canonical Correlation Analysis (CCA) [6], Locality Preserving Projections (LPP) [7], and Spectral Clustering (SC) [9] have been extensively used as a feature extraction step in modeling, clustering, classification, and visualization problems. The aim of CA techniques is to decompose a signal into relevant components that are optimal for a given task (e.g., classification, visualization). These components, explicitly or implicitly (e.g., kernel methods), define the representation of the signal. CA techniques are appealing for two main reasons. First, CA models typically have a small number of parameters, and therefore can be estimated using relatively few samples. CA techniques are especially useful to model high-dimensional data because, due to the curse-of-dimensionality, learning models typically requires a large number of samples. Second, many CA techniques can be formulated as eigen-problems, offering great potential for efficient learning of linear and nonlinear models without local minima. The use of eigen-solvers to address statistical problems dates back to the 1930s, and since then many numerically stable and efficient packages have been developed to solve eigen-problems. For these reasons, during the last century many computer vision, computer graphics, signal processing, and statistical problems were posed as problems of learning a low-dimensional CA model.