Back to Search
Start Over
Manifold Proximal Point Algorithms for Dual Principal Component Pursuit and Orthogonal Dictionary Learning
- Source :
- ACSSC
- Publication Year :
- 2021
- Publisher :
- Institute of Electrical and Electronics Engineers (IEEE), 2021.
-
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.<br />Comment: Accepted in IEEE Transactions on Signal Processing
- 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
Subjects
Details
- ISSN :
- 19410476 and 1053587X
- Volume :
- 69
- Database :
- OpenAIRE
- Journal :
- IEEE Transactions on Signal Processing
- Accession number :
- edsair.doi.dedup.....4908c673f98fd521d4406eecde0cd3b2