1. Manifold Proximal Point Algorithms for Dual Principal Component Pursuit and Orthogonal Dictionary Learning
- Author
-
Zengde Deng, Anthony Man-Cho So, Shixiang Chen, and Shiqian Ma
- Subjects
Signal Processing (eess.SP) ,FOS: Computer and information sciences ,Computer Science - Machine Learning ,Sublinear function ,Computer science ,Heuristic (computer science) ,Computer Vision and Pattern Recognition (cs.CV) ,Computer Science - Computer Vision and Pattern Recognition ,Machine Learning (stat.ML) ,010103 numerical & computational mathematics ,02 engineering and technology ,01 natural sciences ,Machine Learning (cs.LG) ,law.invention ,Stiefel manifold ,Principal component pursuit ,Statistics - Machine Learning ,law ,Convergence (routing) ,FOS: Mathematics ,FOS: Electrical engineering, electronic engineering, information engineering ,0202 electrical engineering, electronic engineering, information engineering ,Electrical Engineering and Systems Science - Signal Processing ,0101 mathematics ,Electrical and Electronic Engineering ,Mathematics - Optimization and Control ,Augmented Lagrangian method ,020206 networking & telecommunications ,Manifold ,Dual (category theory) ,Proximal point ,Rate of convergence ,Optimization and Control (math.OC) ,Norm (mathematics) ,Signal Processing ,Manifold (fluid mechanics) ,Dictionary learning ,Algorithm ,Subspace topology - Abstract
We consider the problem of maximizing the $\ell_1$ norm of a linear map over the sphere, which arises in various machine learning applications such as orthogonal dictionary learning (ODL) and robust subspace recovery (RSR). The problem is numerically challenging due to its nonsmooth objective and nonconvex constraint, and its algorithmic aspects have not been well explored. In this paper, we show how the manifold structure of the sphere can be exploited to design fast algorithms for tackling this problem. Specifically, our contribution is threefold. First, we present a manifold proximal point algorithm (ManPPA) for the problem and show that it converges at a sublinear rate. Furthermore, we show that ManPPA can achieve a quadratic convergence rate when applied to the ODL and RSR problems. Second, we propose a stochastic variant of ManPPA called StManPPA, which is well suited for large-scale computation, and establish its sublinear convergence rate. Both ManPPA and StManPPA have provably faster convergence rates than existing subgradient-type methods. Third, using ManPPA as a building block, we propose a new approach to solving a matrix analog of the problem, in which the sphere is replaced by the Stiefel manifold. The results from our extensive numerical experiments on the ODL and RSR problems demonstrate the efficiency and efficacy of our proposed methods., Comment: Accepted in IEEE Transactions on Signal Processing
- Published
- 2021