A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion

Yangyang Xu University of Alabama Wotao Yin UCLA

Numerical Analysis and Scientific Computing Optimization and Control mathscidoc:1703.25019

Gold Award Paper in 2017

SIAM Journal on Imaging Sciences, 6, (3), 1758-1789, 2013
This paper considers regularized block multiconvex optimization, where the feasible set and objective function are generally nonconvex but convex in each block of variables. It also accepts nonconvex blocks and requires these blocks to be updated by proximal minimization. We review some interesting applications and propose a generalized block coordinate descent method. Under certain conditions, we show that any limit point satisfies the Nash equilibrium conditions. Furthermore, we establish global convergence and estimate the asymptotic convergence rate of the method by assuming a property based on the Kurdyka-Lojasiewicz inequality. The proposed algorithms are tested on nonnegative matrix and tensor factorization, as well as matrix and tensor recovery from incomplete observations. The tests include synthetic data and hyperspectral data, as well as image sets from the CBCL and ORL databases. Compared to the existing state-of-the-art algorithms, the proposed algorithms demonstrate superior performance in both speed and solution quality. The MATLAB code of nonnegative matrix/tensor decomposition and completion, along with a few demos, are accessible from the authors' homepages.
block coordinate descent, Kurdyka-Lojasiewicz inequality, nonnegative matrix and tensor factorization, tensor completion
[ Download ] [ 2017-03-14 09:13:41 uploaded by yangyangxu ] [ 6528 downloads ] [ 0 comments ]
@inproceedings{yangyang2013a,
  title={A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion},
  author={Yangyang Xu, and Wotao Yin},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170314091341589116687},
  booktitle={SIAM Journal on Imaging Sciences},
  volume={6},
  number={3},
  pages={1758-1789},
  year={2013},
}
Yangyang Xu, and Wotao Yin. A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. 2013. Vol. 6. In SIAM Journal on Imaging Sciences. pp.1758-1789. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20170314091341589116687.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved