A Simple and Fast Algorithm for L1-norm Kernel PCA
This work addresses a specific computational bottleneck in robust dimensionality reduction for machine learning applications, offering an incremental improvement over existing methods.
The paper tackles the problem of L1-norm kernel PCA, which is non-convex and non-smooth, by proposing a novel reformulation and a fixed-point algorithm that converges to a local optimum with a proven linear rate. In experiments, the algorithm demonstrates robustness to perturbations and scalability in large-scale settings, outperforming benchmarks in outlier detection.
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.