Dual Principal Component Pursuit: Improved Analysis and Efficient Algorithms
Recent methods for learning a linear subspace from data corrupted by outliers are based on convex 1 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 1 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 Method (DPCP-PSGM) for solving the DPCP problem and show that it achieves 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-PSGM can be more efficient than the traditional RANSAC algorithm, which is one of the most popular methods for such computer vision applications.
This work has provided an improved analysis for global optimality of the (nonconvex) dual PCA problem based on random model assumption, and a more efficient optimization method based sub-gradient descent with a local linear convergent rate. The paper is well-organized overall, and the theoretical improvement is substantial compared to the existing work. The explanations of analysis in Section 2 and algorithms in Section 3 are not very clear and can be improved in the future. Below are some more detailed comments:  1. Assumptions of the random model: First, aside from the benefits of the analysis, how does the random spherical model of the subspace relates to applications? Does real data (both outliers and subspace) follow random spherical distribution? The reviewer feels that more validation is needed. Second, the description of the random model of the subspace in Theorem 2 is not very clear. From the reviewer’s understanding, is it that the columns of O is uniformly drawn from the sphere S^{D-1}, and the columns of X is uniformly drawn from a lower dimension sphere that S^{D-1} \cap A, where A is and dimensional subspace? The current description is not very clear and quite misleading. Besides, is there any assumption for the properties of the subspace A?   2. The relationship between M and N. From Theorem 2, if the reviewer understand correctly, the authors hid the dimension D  and d in the relation of M and N. If the dimension D and the subspace dimension d are counted, it should be M<=O(d/D*N^2), which makes sense as the subspace dimension d (ambient dimension D) gets bigger, more (fewer) outliers are tolerated. As the dimension D could be very large for many applications, the reviewer feels those parameters (d and D) cannot be ignored and should be accounted and explained in the introduction and the remarks.  3. For the subgradient method, could the author explain the intuition behind the choice of the initialization? Why does such a choice produce an initialization with small principle angle? On the other hand, for the subgradient method, does the linear convergence of subgradient method mainly due to the choice of the step size or due to the structure of the problem? For general convex nonsmooth problems, the convergence rate of subgradient method is usually sublinear. The reviewer feels that the reason could be that the local region around the optimal solutions has certain benign geometric structures (i.e. satisfies certain regularization conditions) that make linear convergence possible. It would be better if the author provides better explanation of this ``surprising’’ algorithmic property.  4. Possible Extensions: (1) The current work only considers finding a single subspace, does the current analysis possible to be extended to multiple (orthogonal) subspaces (e.g. using deflation or optimization over oblique manifold)?  (2) Instead of l1 norm loss, the author could consider a Huber loss as analyzed in [21], which is first order smooth which is much easier to analyze.  5. typos: Riemann gradient => Riemannian gradient