Properties and methods for finding the best rank-one approximation to higher-order tensors

Yuning Yang, Qingzhi Yang, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)

Abstract

The problem of finding the best rank-one approximation to higher-order tensors has extensive engineering and statistical applications. It is well-known that this problem is equivalent to a homogeneous polynomial optimization problem. In this paper, we study theoretical results and numerical methods of this problem, particularly focusing on the 4-th order symmetric tensor case. First, we reformulate the polynomial optimization problem to a matrix programming, and show the equivalence between these two problems. Then, we prove that there is no duality gap between the reformulation and its Lagrangian dual problem. Concerning the approaches to deal with the problem, we propose two relaxed models. The first one is a convex quadratic matrix optimization problem regularized by the nuclear norm, while the second one is a quadratic matrix programming regularized by a truncated nuclear norm, which is a D.C. function and therefore is nonconvex. To overcome the difficulty of solving this nonconvex problem, we approximate the nonconvex penalty by a convex term. We propose to use the proximal augmented Lagrangian method to solve these two relaxed models. In order to obtain a global solution, we propose an alternating least eigenvalue method after solving the relaxed models and prove its convergence. Numerical results presented in the last demonstrate, especially for nonpositive tensors, the effectiveness and efficiency of our proposed methods.
Original languageEnglish
Pages (from-to)105-132
Number of pages28
JournalComputational Optimization and Applications
Volume58
Issue number1
DOIs
Publication statusPublished - 1 Jan 2014

Keywords

  • Algorithm
  • Best rank-one approximation
  • Nonnegative tensors
  • Nuclear norm regularization
  • Strong duality
  • Z-eigenvalue

ASJC Scopus subject areas

  • Applied Mathematics
  • Computational Mathematics
  • Control and Optimization

Cite this