Avoiding Optimal Mean Robust PCA/2DPCA with Non-greedy ℓ1-Norm Maximization

Minnan Luo, Feiping Nie, Xiaojun Chang, Yi Yang, Alexander G. Hauptmann, Qinghua Zheng

Abstract

Principal Component Analysis (PCA) is a fundamental technique for dimensionality reduction, but its reliance on the $\ell_2$-norm and the arithmetic mean makes it highly sensitive to outliers. While Robust PCA (RPCA) using the $\ell_1$-norm addresses sensitivity to extreme values, it typically requires calculating an "optimal mean," a process that is computationally intensive and often bypassed in practice. This paper introduces RPCA-AOM (Avoiding Optimal Mean), a novel approach that reformulates the PCA objective to maximize the $\ell_1$-norm of pairwise differences between data points. This mathematical shift eliminates the mean term entirely, enhancing both robustness and efficiency. We extend this framework to 2D data (2DPCA-AOM) and employ a non-greedy iterative re-weighted algorithm for optimization. Experimental results on benchmark facial recognition datasets demonstrate that our method consistently outperforms existing robust PCA variants, particularly in the presence of significant data corruption.

Introduction: The Liability of the Mean

Standard PCA seeks to find a projection that minimizes the mean square error ($\ell_2$-norm) relative to the data's arithmetic mean. However, a single outlier can significantly shift the mean, leading to a skewed projection. Robust PCA (RPCA) mitigates this by using the $\ell_1$-norm, which is less sensitive to outliers.

Despite this improvement, a critical challenge remains: the data must be centered. In robust settings, the standard arithmetic mean is biased by outliers. While an "optimal mean" can be calculated for $\ell_1$ objectives, it adds significant computational complexity. Consequently, many researchers use the standard $\ell_2$ mean for $\ell_1$ problems, undermining the robustness of the entire model.

Methodology: The Pairwise Pivot

The core contribution of this work is the realization that the traditional PCA objective can be mathematically reformulated. The authors prove that maximizing the distance from a central mean is equivalent to maximizing the sum of projected differences between every pair of instances in the dataset:

$$\max_W \sum_{i,j} \|W^T(x_i - x_j)\|_1$$

By focusing on pairwise differences, the mean term disappears from the optimization objective. This leads to the RPCA-AOM model.

Non-Greedy Optimization

To solve this $\ell_1$ maximization problem, the authors avoid "greedy" methods that find one projection vector at a time and often stall in local optima. Instead, they utilize an iterative re-weighted algorithm that optimizes all projection directions simultaneously, ensuring better convergence and stability.

Extension to 2D

The framework is further extended to 2DPCA, which operates directly on image matrices. This preserves the spatial structure of images, which is often lost when flattening them into 1D vectors for standard PCA.

Experimental Results

The proposed method was evaluated on several benchmark datasets, including JAFFE, UMIST, ORL, COIL-20, and USPS.

Recognition Accuracy and Robustness

The 2D version, 2DPCA-AOM, was compared against greedy (2DPCA-G) and non-greedy (2DPCA-NG) versions that assume a zero mean. As shown in the figures below, 2DPCA-AOM consistently achieves higher recognition accuracy across various feature dimensions.

Recognition accuracy comparison on benchmark datasets. 2DPCA-AOM (red stars) consistently achieves higher accuracy across varying dimensions compared to traditional 2DPCA approaches.

A key finding is the method's superior performance in the presence of corruption. When training images are corrupted with noise or occlusions, the performance gap between 2DPCA-AOM and its predecessors widens, highlighting the inherent robustness of the mean-invariant formulation.

Recognition accuracy comparison on corrupted datasets. As corruption levels increase (from a to d), the 2DPCA-AOM method maintains a significant performance advantage over greedy (G) and non-greedy (NG) baselines.

Efficiency and Convergence

Despite the $n^2$ pairwise terms, the authors demonstrate that the gradient can be computed efficiently in $O(n \log n)$ or $O(n)$ time. The non-greedy algorithm typically converges within 10 iterations, making it computationally competitive with standard robust methods.

Conclusion

By eliminating the need for an optimal mean, RPCA-AOM provides a more robust and mathematically elegant solution for dimensionality reduction in the presence of outliers. The pairwise formulation not only simplifies the optimization objective but also ensures rotational invariance and superior performance in real-world image recognition tasks. Future work may explore the application of this framework to other robust norms and its scalability to extremely large-scale datasets.

Summary updated

Abstract

Robust principal component analysis (PCA) is one of the most important dimension reduction techniques to handle high-dimensional data with outliers. However, the existing robust PCA presupposes that the mean of the data is zero and incorrectly utilizes the Euclidean distance based optimal mean for robust PCA with l1-norm. Some studies consider this issue and integrate the estimation of the optimal mean into the dimension reduction objective, which leads to expensive computation. In this paper, we equivalently reformulate the maximization of variances for robust PCA, such that the optimal projection directions are learned by maximizing the sum of the projected difference between each pair of instances, rather than the difference between each instance and the mean of the data. Based on this reformulation, we propose a novel robust PCA to automatically avoid the calculation of the optimal mean based on l1-norm distance. This strategy also makes the assumption of centered data unnecessary. Additionally, we intuitively extend the proposed robust PCA to its 2D version for image recognition. Efficient non-greedy algorithms are exploited to solve the proposed robust PCA and 2D robust PCA with fast convergence and low computational complexity. Some experimental results on benchmark data sets demonstrate the effectiveness and superiority of the proposed approaches on image reconstruction and recognition.
BibTeX
@inproceedings{luo2016avoiding,
  author = {Minnan Luo and Feiping Nie and Xiaojun Chang and Yi Yang and Alexander G. Hauptmann and Qinghua Zheng},
  title = {{Avoiding Optimal Mean Robust PCA/2DPCA with Non-greedy ℓ1-Norm Maximization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=IDEIQidzI_l},
}
Figure