Robust Kernel Dictionary Learning Using a Whole Sequence Convergent Algorithm

Huaping Liu, Jie Qin, Hong Cheng, Fuchun SunIJCAI 2015 · OpenReview

Introduction

Sparse coding is a fundamental technique in machine learning, used to represent data as a combination of a few "atoms" from a learned dictionary. When dealing with non-linear data, the "kernel trick" allows these patterns to be captured in a high-dimensional feature space. However, standard kernel dictionary learning (KDL) is highly sensitive to outliers; a few "garbage" data points can significantly corrupt the learned dictionary. This paper, presented at IJCAI 2015, addresses this by proposing a robust KDL model that explicitly isolates outliers during the training phase.

The Robust Model: Outliers as Self-Representation

The authors' primary innovation is a model that decomposes reconstruction error into two parts: standard dense noise and large, sparse outliers. In the kernel space, they represent the outlier matrix $E$ as the product of the training samples and a diagonal coefficient matrix $R$ ($E = \Phi(Y)R$).

By enforcing sparsity on $R$, the model effectively identifies which specific training samples are outliers that cannot be well-explained by the dictionary. This "self-representation" mechanism allows the algorithm to ignore these points when building the dictionary, leading to "purer" atoms.

Outlier detection via sparse coefficients r

In synthetic experiments, this approach perfectly identified the indices of injected outliers, whereas traditional methods like K-KSVD were heavily influenced by them.

A Mathematically Rigorous Convergent Algorithm

Dictionary learning is a non-convex optimization problem, which often means algorithms may not settle at a stable solution. To solve this, the authors developed a "whole sequence convergent algorithm" based on the alternating proximal linearized method.

Unlike previous methods that only guarantee a decrease in the objective function's value, this algorithm is mathematically proven to produce a Cauchy sequence. This ensures that the variables—the dictionary and its coefficients—actually converge to a stable critical point, providing much-needed reliability for real-world applications.

Key Results and Performance

The researchers evaluated the proposed method against several benchmarks, including K-Means and K-KSVD, using datasets like USPS handwritten digits and UCMERCED aerial scenes.

Resilience to High Noise

The model's robustness was most evident in high-noise scenarios. On the UCMERCED dataset with 50% outliers, the proposed method maintained approximately 80% classification accuracy, while competing methods plummeted to below 65%. This performance gain is attributed to the cleaner dictionaries learned by isolating the outliers during training.

Convergence Stability

The algorithm is not only robust but also efficient and stable. It typically reaches a stable solution within 20 to 40 iterations.

Convergence comparison between the proposed method and K-KSVD

As shown in the convergence plots, the proposed method (left) exhibits a smooth and rapid descent to zero for the coefficient difference $\|C^{k+1}-C^k\|_2$, whereas K-KSVD (right) shows significantly more instability and slower convergence.

Conclusion

By integrating an explicit outlier detection term with a mathematically guaranteed convergent algorithm, this work provides a robust framework for kernel dictionary learning. While the computational cost of $N \times N$ kernel matrices remains a consideration for massive datasets, the method offers superior accuracy and stability in the presence of significant noise and outliers.

Summary updated

Abstract

Kernel sparse coding is an effective strategy to capture the non-linear structure of data samples. However, how to learn a robust kernel dictionary remains an open problem. In this paper, we propose a new optimization model to learn the robust kernel dictionary while isolating outliers in the training samples. This model is essentially based on the decomposition of the reconstruction error into small dense noises and large sparse outliers. The outlier error term is formulated as the product of the sample matrix in the feature space and a diagonal coefficient matrix. This facilitates the kernelized dictionary learning. To solve the non-convex optimization problem, we develop a whole sequence convergent algorithm which guarantees the obtained solution sequence is a Cauchy sequence. The experimental results show that the proposed robust kernel dictionary learning method provides significant performance improvement.
BibTeX
@inproceedings{liu2015robust,
  author = {Huaping Liu and Jie Qin and Hong Cheng and Fuchun Sun},
  title = {{Robust Kernel Dictionary Learning Using a Whole Sequence Convergent Algorithm}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=By-4sXz_-S},
}
Figure