# Dual Principal Component Pursuit

arXiv: https://arxiv.org/abs/1510.04390 · HTML: https://mlsanity.com/paper/1510.04390/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2015.

## Built on by (most cited first, 19 of 19)

- [The Ideal Continual Learner: An Agent That Never Forgets](https://mlsanity.com/paper/2305.00316/) (2023)
- [ARCS: Accurate Rotation and Correspondence Search](https://mlsanity.com/paper/2203.14493/) (2022)
- [Stabilizing Adversarially Learned One-Class Novelty Detection Using Pseudo Anomalies](https://mlsanity.com/paper/2203.13716/) (2022)
- [Unlabeled Principal Component Analysis and Matrix Completion](https://mlsanity.com/paper/2101.09446/) (2021)
- [Fun with Flags: Robust Principal Directions via Flag Manifolds](https://mlsanity.com/paper/2401.04071/) (2024)
- [A Riemannian ADMM](https://mlsanity.com/paper/2211.02163/) (2022)
- [Unknown Face Presentation Attack Detection via Localised Learning of Multiple Kernels](https://mlsanity.com/paper/2204.10675/) (2022)
- [Nested subspace learning with flags](https://mlsanity.com/paper/2502.06022/) (2025)
- [A Riemannian smoothing steepest descent method for non-Lipschitz optimization on submanifolds](https://mlsanity.com/paper/2104.04199/) (2021)
- [Beyond the Known: Adversarial Autoencoders in Novelty Detection](https://mlsanity.com/paper/2404.04456/) (2024)
- [Unsupervised Congestion Status Identification Using LMP Data](https://mlsanity.com/paper/2411.10058/) (2024)
- [A Flag Decomposition for Hierarchical Datasets](https://mlsanity.com/paper/2502.07782/) (2025)
- [Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search](https://mlsanity.com/paper/2106.12190/) (2021)
- [Boosting RANSAC via Dual Principal Component Pursuit](https://mlsanity.com/paper/2110.02918/) (2021)
- [Implicit Bias of Projected Subgradient Method Gives Provable Robust Recovery of Subspaces of Unknown Codimension](https://mlsanity.com/paper/2201.09079/) (2022)
- [Fast geometric trim fitting using partial incremental sorting and accumulation](https://mlsanity.com/paper/2209.02034/) (2022)
- [A Robust Likelihood Model for Novelty Detection](https://mlsanity.com/paper/2306.03331/) (2023)
- [AdaContour: Adaptive Contour Descriptor with Hierarchical Representation](https://mlsanity.com/paper/2404.08292/) (2024)
- [Robust Fuzzy local k-plane clustering with mixture distance of hinge loss and L1 norm](https://mlsanity.com/paper/2604.22405/) (2026)

## Abstract (arXiv)

We consider the problem of learning a linear subspace from data corrupted by outliers. Classical approaches are typically designed for the case in which the subspace dimension is small relative to the ambient dimension. Our approach works with a dual representation of the subspace and hence aims to find its orthogonal complement; as such, it is particularly suitable for subspaces whose dimension is close to the ambient dimension (subspaces of high relative dimension). We pose the problem of computing normal vectors to the inlier subspace as a non-convex ℓ1 minimization problem on the sphere, which we call Dual Principal Component Pursuit (DPCP) problem. We provide theoretical guarantees under which every global solution to DPCP is a vector in the orthogonal complement of the inlier subspace. Moreover, we relax the non-convex DPCP problem to a recursion of linear programs whose solutions are shown to converge in a finite number of steps to a vector orthogonal to the subspace. In particular, when the inlier subspace is a hyperplane, the solutions to the recursion of linear programs converge to the global minimum of the non-convex DPCP problem in a finite number of steps. We also propose algorithms based on alternating minimization and iteratively re-weighted least squares, which are suitable for dealing with large-scale data. Experiments on synthetic data show that the proposed methods are able to handle more outliers and higher relative dimensions than current state-of-the-art methods, while experiments in the context of the three-view geometry problem in computer vision suggest that the proposed methods can be a useful or even superior alternative to traditional RANSAC-based approaches for computer vision and other applications.