Abstract
In this paper we study the ℓp (or Schatten-p quasi-norm) regularized low-rank approximation problems. In particular, we introduce a class of first-order stationary points for them and show that any local minimizer of these problems must be a first-order stationary point. In addition, we derive lower bounds for the nonzero singular values of the first-order stationary points and hence also of the local minimizers of these problems. The iterative reweighted singular value minimization (IRSVM) methods are then proposed to solve these problems, whose subproblems are shown to have a closed-form solution. Compared to the analogous methods for the ℓp regularized vector minimization problems, the convergence analysis of these methods is significantly more challenging. We develop a novel approach to establishing the convergence of the IRSVM methods, which makes use of the expression of a specific solution of their subproblems and avoids the intricate issue of finding the explicit expression for the Clarke subdifferential of the objective of their subproblems. In particular, we show that any accumulation point of the sequence generated by the IRSVM methods is a first-order stationary point of the problems. Our computational results demonstrate that the IRSVM methods generally outperform the recently developed iterative reweighted least squares methods in terms of solution quality and/or speed.
Original language | English (US) |
---|---|
Pages (from-to) | 619-642 |
Number of pages | 24 |
Journal | Computational Optimization and Applications |
Volume | 68 |
Issue number | 3 |
DOIs | |
State | Published - Dec 1 2017 |
Externally published | Yes |
Bibliographical note
Funding Information:Zhaosong Lu was supported in part by NSERC Discovery Grant. Jian Lu was supported in part by the National Natural Science Foundation of China under Grants 61373087, 61472257, by the Natural Science Foundation of Guangdong, China under Grants 2015A030313550, 2015A030313557.
Publisher Copyright:
© 2017, Springer Science+Business Media, LLC.
Keywords
- Iterative reweighted least squares
- Iterative reweighted singular value minimization
- Low-rank approximation
- Schatten-p quasi-norm regularized matrix minimization