Robust Kernel Principal Component Analysis

Minh Hoai Nguyen, Fernando De la TorreNeurIPS 2008 · OpenReview

Overview

This paper introduces Robust Kernel PCA (RKPCA), a unified framework that extends the power of non-linear feature extraction to handle noisy, occluded, or missing data. By optimizing a novel cost function that balances proximity to the input data with proximity to a learned "clean" subspace, the authors provide a way to reconstruct high-quality images and data points even when the original samples are heavily corrupted.

What Problem Does This Paper Address?

Principal Component Analysis (PCA) is a staple for data modeling, but it struggles with non-linear structures. Kernel PCA (KPCA) solves this by mapping data into a high-dimensional "feature space" where linear patterns emerge. However, KPCA has a major Achilles' heel: robustness.

In the real world, data is messy—think of a face partially hidden by a hand (occlusion), a grainy photo (noise), or a sensor failure (missing data). Standard KPCA reconstruction (the "pre-image" problem) is highly sensitive to these artifacts. Because the feature space is "implicit" (we only know the distances between points, not their exact coordinates), directly applying robust statistics is mathematically difficult. Previous methods often produced "clean" versions of data that were still biased by the very noise they were trying to remove.

Methods

The core innovation of RKPCA is a fundamental shift in how we approach data reconstruction.

Comparison of traditional pre-image mapping vs. the proposed robust cost function in feature space.
  1. The New Cost Function: Traditional methods find a reconstructed point $z$ that is as close as possible to the projection of the noisy input $x$ onto the principal subspace. The authors argue this is flawed because if $x$ is noisy, its projection is also noisy. Instead, they propose a cost function with two competing terms:
  2. Term 1: Keep the reconstruction $z$ close to the input $x$ (acting as an "anchor").
  3. Term 2: Keep the reconstruction $z$ close to the principal subspace (the "clean" model).
  4. Robust Kernels: To handle severe outliers (like a hand covering a face), they replace standard distance measures with robust functions, such as the Geman-McClure function. This allows the algorithm to effectively "ignore" pixels that deviate too far from the expected model.
  5. Optimization: Since the resulting objective function is non-convex, the authors derive a fixed-point iteration algorithm. This allows for efficient inference, iteratively pulling the corrupted sample toward the "clean" manifold of the data without needing explicit coordinates in the infinite-dimensional feature space.

Datasets and Key Insights

The authors evaluated their method on two distinct types of data to test different forms of corruption:

  • CMU Multi-PIE Database: A massive collection of facial images used to test robustness against synthetic occlusions (random blocks), natural occlusions (hands), specular reflections, and Gaussian noise.
  • Oil Flow Dataset: A 12-dimensional synthetic dataset modeling the flow of oil, water, and gas in a pipe, used specifically to test the recovery of missing attribute values.

A major theoretical insight from this work is the unified treatment of data corruption. Unlike previous specialized fixes, this framework treats noise, outliers, and missing data as different flavors of the exact same optimization problem.

Key Results

Visual comparison of face reconstruction under various corruptions (noise, occlusion, specular reflection).
  • Face Recovery: On the Multi-PIE dataset, RKPCA significantly outperformed standard KPCA and Robust Linear PCA. Even with severe 40-pixel occlusions, RKPCA maintained a much lower reconstruction error (e.g., an error of 14.3 vs. 20.9 for the next best KPCA variant).
  • Visual Quality: Qualitatively, the denoised images from RKPCA preserve much finer details—like the shape of the mouth and eyes—compared to PCA or other kernel methods, which often produce blurry or distorted results when faced with occlusion or heavy noise.
  • Missing Data: In the Oil Flow experiments, RKPCA consistently beat other methods (like Probabilistic PCA and 1-Nearest Neighbor) across all levels of missing data. For instance, with 50% of data missing, RKPCA achieved a reconstruction error of 83, while the next best method (PKPCA) lagged behind at 100.

Limitations and Future Work

While powerful, the RKPCA framework has a few limitations:

  • Non-Convexity: The objective function is non-convex, meaning the algorithm could potentially get stuck in local minima depending on its initialization point.
  • Kernel Selection: The current optimization derivation is tailored specifically for the Gaussian kernel. Extending the specific fixed-point updates to other kernel types would require further mathematical derivation.
  • Computational Cost: Performing non-linear inference via fixed-point updates is still more computationally demanding than linear PCA, which might limit its use in real-time applications on very high-resolution video streams.

Summary updated

Abstract

Kernel Principal Component Analysis (KPCA) is a popular generalization of linear PCA that allows non-linear feature extraction. In KPCA, data in the input space is mapped to higher (usually) dimensional feature space where the data can be linearly modeled. The feature space is typically induced implicitly by a kernel function, and linear PCA in the feature space is performed via the kernel trick. However, due to the implicitness of the feature space, some extensions of PCA such as robust PCA cannot be directly generalized to KPCA. This paper presents a technique to overcome this problem, and extends it to a unified framework for treating noise, missing data, and outliers in KPCA. Our method is based on a novel cost function to perform inference in KPCA. Extensive experiments, in both synthetic and real data, show that our algorithm outperforms existing methods.
BibTeX
@inproceedings{nguyen2008robust,
  author = {Minh Hoai Nguyen and Fernando De la Torre},
  title = {{Robust Kernel Principal Component Analysis}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2008},
  url = {https://openreview.net/forum?id=HkWmSOWO-H},
}
Figure