Accession Number : ADA567404


Title :   A Block Coordinate Descent Method for Multi-Convex Optimization with Applications to Nonnegative Tensor Factorization and Completion


Descriptive Note : Technical rept.


Corporate Author : RICE UNIV HOUSTON TX DEPT OF COMPUTATIONAL AND APPLIED MATHEMATICS


Personal Author(s) : Xu, Yangyang ; Yin, Wotao


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a567404.pdf


Report Date : Aug 2012


Pagination or Media Count : 25


Abstract : This paper considers block multi-convex optimization, where the feasible set and objective function are generally non-convex but convex in each block of variables. We review some of its interesting examples 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 its global convergence and estimate its asymptotic convergence rate by assuming a property based on the Kurdyka-Lojasiewicz inequality. The proposed algorithms are adapted for factorizing nonnegative matrices and tensors, as well as completing them from their incomplete observations. The algorithms were tested on synthetic data, 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 is available for download from the authors' homepages.


Descriptors :   *TENSORS , ALGORITHMS , CONVERGENCE , MATRICES(MATHEMATICS) , OPTIMIZATION


Subject Categories : Theoretical Mathematics
      Operations Research
      Cybernetics


Distribution Statement : APPROVED FOR PUBLIC RELEASE