A Simple and Fast Algorithm for L1-norm Kernel PCA

Abstract

We present an algorithm for L1-norm kernel PCA and provide a convergence analysis for it. While an optimal solution of L2-norm kernel PCA can be obtained through matrix decomposition, finding that of L1-norm kernel PCA is not trivial due to its non-convexity and non-smoothness. We provide a novel reformulation through which an equivalent, geometrically interpretable problem is obtained. Based on the geometric interpretation of the reformulated problem, we present a fixed-point type algorithm that iteratively computes a binary weight for each observation. As the algorithm requires only inner products of data vectors, it is computationally efficient and the kernel trick is applicable. In the convergence analysis, we show that the algorithm converges to a local optimal solution in a finite number of steps. Moreover, we provide a rate of convergence analysis, which has been never done for any L1-norm PCA algorithm, proving that the sequence of objective values converges at a linear rate. In numerical experiments, we show that the algorithm is robust in the presence of entry-wise perturbations and computationally scalable, especially in a large-scale setting. Lastly, we introduce an application to outlier detection where the model based on the proposed algorithm outperforms the benchmark algorithms.

14 pages, 7 figures

References in corpus (4)

• Robust PCA via Outlier Pursuit
• Optimal Algorithms for $L_1$-subspace Signal Processing
• Recovery of Coherent Data via Low-Rank Dictionary Pursuit
• Iteratively Reweighted Least Squares Algorithms for L1-Norm Principal Component Analysis

Cited by in corpus (6)

• A Multi-criteria Approach for Fast and Outlier-aware Representative Selection from Manifolds
• Upper and Lower Bounds on the Performance of Kernel PCA
• Supervised Anomaly Detection via Conditional Generative Adversarial Network and Ensemble Active Learning
• Principal Component Analysis Based on T${\ell }_1$-norm Maximization
• Linear Convergence of a Proximal Alternating Minimization Method with Extrapolation for ${\ell }_1$-Norm Principal Component Analysis
• Coordinate Descent Methods for DC Minimization: Optimality Conditions and Global Convergence