Kernel principal component analysis

In the field of multivariate statistics, kernel principal component analysis (kernel PCA) is an extension of principal component analysis (PCA) using techniques of kernel methods. Using a kernel, the originally linear operations of PCA are performed in a reproducing kernel Hilbert space. Background: Linear PCA Recall that conventional PCA operates on zero-centered data; that is, :\frac{1}{N}\sum_{i=1}^N \mathbf{x}_i = \mathbf{0}, where \mathbf{x}i is one of the N multivariate observations. It operates by diagonalizing the covariance matrix, :C=\frac{1}{N}\sum{i=1}^N \mathbf{x}_i\mathbf{x}_i^\top in other words, it gives an eigendecomposition of the covariance matrix: :\lambda \mathbf{v}=C\mathbf{v} which can be rewritten as :\lambda \mathbf{x}_i^\top \mathbf{v}=\mathbf{x}_i^\top C\mathbf{v} \quad \textrm{for}~i=1,\ldots,N. (See also: Covariance matrix as a linear operator) Introduction of th

Procrustes Metrics and Optimal Transport for Covariance Operators

Valentina Masarotto

Covariance operators play a fundamental role in functional data analysis, providing the canonical means to analyse functional variation via the celebrated Karhunen-Loève expansion. These operators may themselves be subject to variation, for instance in contexts where multiple functional populations are to be compared. Statistical techniques to analyse such variation are intimately linked with the choice of metric on the space of such operators, as well as with their intrinsic infinite-dimensionality. We will show that we can identify the space of infinite-dimensional covariance operators equipped with the Procrustes size-and-shape metric from shape theory, with that of centred Gaussian processes, equipped with the Wasserstein metric of optimal transportation. We then describe key geometrical and topological aspects of the space of covariance operators endowed with the Procrustes metric. Through the notion of multicoupling of Gaussian measures, we establish existence, uniqueness and stability for the Fréchet mean of covariance operators with respect to the Procrustes metric. Furthermore, we will provide generative models that are canonical for such metric. We then turn to the problem of comparing several samples of stochastic processes with respect to their second-order structure, and we subsequently describe the main modes of variation in this second order structure. These two tasks are carried out via an Analysis of Variance (ANOVA) and a Principal Component Analysis (PCA) of covariance operators respectively. In order to perform ANOVA, we introduce a novel approach based on optimal (multi)transport and identify each covariance with an optimal transport map. These maps are then contrasted with the identity with respect to a norm-induced distance. The resulting test statistic, calibrated by permutation, outperforms the state-of-the-art in the functional case. If the null hypothesis postulating equality of the operators is rejected, thanks to a geometric interpretation of the transport maps we can construct a PCA on the tangent space with the aim of understanding the sample variability. Finally, we provide a further example of use of the optimal transport framework, by applying it to the problem of clustering of operators. Two different clustering algorithms are presented, one of which is innovative. The transportation ANOVA, PCA and clustering are validated both on simulated scenarios and real dataset.

EPFL2019

Structural Analysis of Network Traffic Matrix via Relaxed Principal Component Pursuit

Xiaowen Dong, Zhe Wang, Ke Xu

The network traffic matrix is widely used in network operation and management. It is of crucial importance to analyze the composition and the structure of the network traffic matrix, for which some mathematical approaches such as Principal Component Analysis (PCA) were proposed to handle that problem. In this paper, we first argue that PCA performs poorly for analyzing traffic matrices that are polluted by large volume anomalies, and then propose a new decomposition model for the network traffic matrix. According to our model, structural analysis is carried out by decomposing the network traffic matrix into three sub-matrices, which is similar to the Robust Principal Component Analysis (RPCA) problem previously studied in [13]. Based on the Relaxed Principal Component Pursuit (Relaxed PCP) method and the Accelerated Proximal Gradient (APG) algorithm, an iterative algorithm for decomposing a traffic matrix is presented, and our experimental results demonstrate its efficiency and flexibility. Finally, further discussions on the deterministic traffic and the traffic noise are carried out. Our study gives a proper method for structural analysis of the traffic matrix, which is robust against pollution of large volume anomalies.

2012

An online Hebbian learning rule that performs Independent Component Analysis

Claudia Clopath, Wulfram Gerstner, André Longtin

Independent component analysis (ICA) is a powerful method to decouple signals. Most of the algorithms performing ICA do not consider the temporal correlations of the signal, but only higher moments of its amplitude distribution. Moreover, they require some preprocessing of the data (whitening) so as to remove second order correlations. In this paper, we are interested in understanding the neural mechanism responsible for solving ICA. We present an online learning rule that exploits delayed correlations in the input. This rule performs ICA by detecting joint variations in the firing rates of pre- and postsynaptic neurons, similar to a local rate-based Hebbian learning rule.

MIT Press2008

Procrustes Metrics and Optimal Transport for Covariance Operators

Valentina Masarotto

EPFL2019