p Regularized low-rank approximation via iterative reweighted singular value minimization

Zhaosong Lu, Yong Zhang, Jian Lu

Research output: Contribution to journalArticle

7 Scopus citations

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 languageEnglish (US)
Pages (from-to)619-642
Number of pages24
JournalComputational Optimization and Applications
Volume68
Issue number3
DOIs
StatePublished - Dec 1 2017
Externally publishedYes

Keywords

  • Iterative reweighted least squares
  • Iterative reweighted singular value minimization
  • Low-rank approximation
  • Schatten-p quasi-norm regularized matrix minimization

Fingerprint Dive into the research topics of 'ℓ<sub>p</sub> Regularized low-rank approximation via iterative reweighted singular value minimization'. Together they form a unique fingerprint.

  • Cite this