Timezone: »

 
Poster
Dual Principal Component Pursuit: Improved Analysis and Efficient Algorithms
Zhihui Zhu · Yifan Wang · Daniel Robinson · Daniel Naiman · René Vidal · Manolis Tsakiris

Wed Dec 05 02:00 PM -- 04:00 PM (PST) @ Room 517 AB #170
in Wed Poster Session B »

Recent methods for learning a linear subspace from data corrupted by outliers are based on convex L1 and nuclear norm optimization and require the dimension of the subspace and the number of outliers to be sufficiently small [27]. In sharp contrast, the recently proposed Dual Principal Component Pursuit (DPCP) method [22] can provably handle subspaces of high dimension by solving a non-convex L1 optimization problem on the sphere. However, its geometric analysis is based on quantities that are difficult to interpret and are not amenable to statistical analysis. In this paper we provide a refined geometric analysis and a new statistical analysis that show that DPCP can tolerate as many outliers as the square of the number of inliers, thus improving upon other provably correct robust PCA methods. We also propose a scalable Projected Sub-Gradient Descent method (DPCP-PSGD) for solving the DPCP problem and show it admits linear convergence even though the underlying optimization problem is non-convex and non-smooth. Experiments on road plane detection from 3D point cloud data demonstrate that DPCP-PSGD can be more efficient than the traditional RANSAC algorithm, which is one of the most popular methods for such computer vision applications.

Keywords: Components Analysis (e.g., CCA, ICA, LDA, PCA) · Non-Convex Optimization
[ Paper] 

Author Information

Zhihui Zhu (Johns Hopkins University)
Yifan Wang (University of Washington)
Daniel Robinson (Johns Hopkins University)
Daniel Naiman (Johns Hopkins University)
René Vidal (Johns Hopkins University)
Manolis Tsakiris (ShanghaiTech University)

More from the Same Authors