A Simple and Fast Algorithm for L1-Norm Kernel PCA.

Area of Science:

• Machine Learning
• Dimensionality Reduction
• Kernel Methods

Background:

• Principal Component Analysis (PCA) is a widely used dimensionality reduction technique.
• L2-norm PCA has efficient solutions via matrix decomposition.
• L1-norm PCA is challenging due to non-convexity and non-smoothness, hindering optimal solution finding.

Purpose of the Study:

• To present an efficient algorithm for L1-norm kernel PCA.
• To provide a convergence and rate of convergence analysis for the proposed algorithm.
• To demonstrate the algorithm's robustness, scalability, and effectiveness in outlier detection.

Main Methods:

• A novel reformulation of L1-norm kernel PCA into a geometrically interpretable problem.
• A fixed-point type algorithm iteratively computing binary weights for observations.
• Utilizing inner products for computational efficiency and applicability of the kernel trick.

Main Results:

• The algorithm converges to a local optimal solution in a finite number of steps.
• A linear rate of convergence is proven for the objective values.
• Numerical experiments show robustness to perturbations and scalability for large datasets.
• The proposed model outperforms benchmarks in outlier detection.

Conclusions:

• The developed algorithm offers an efficient and robust solution for L1-norm kernel PCA.
• The convergence analysis provides theoretical guarantees, including a linear convergence rate.
• The algorithm demonstrates practical utility in large-scale machine learning and outlier detection tasks.