Computing eigenvalues of large scale sparse tensors arising from a hypergraph

Jingya Chang, Yannan Chen, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)

Abstract

The spectral theory of higher-order symmetric tensors is an important tool for revealing some important properties of a hypergraph via its adjacency tensor, Laplacian tensor, and signless Laplacian tensor. Owing to the sparsity of these tensors, we propose an efficient approach to calculate products of these tensors and any vectors. By using the state-of-the-art L-BFGS approach, we develop a first-order optimization algorithm for computing H- and Z-eigenvalues of these large scale sparse tensors (CEST). With the aid of the Lojasiewicz inequality, we prove that the sequence of iterates generated by CEST converges to an eigenvector of the tensor. When CEST is started from multiple random initial points, the resulting best eigenvalue could touch the extreme eigenvalue with a high probability. Finally, numerical experiments on small hypergraphs show that CEST is efficient and promising. Moreover, CEST is capable of computing eigenvalues of tensors related to a hypergraph with millions of vertices.
Original languageEnglish
Pages (from-to)A3618-A3643
JournalSIAM Journal on Scientific Computing
Volume38
Issue number6
DOIs
Publication statusPublished - 1 Jan 2016

Keywords

  • Eigenvalue
  • Hypergraph
  • L-BFGS
  • Laplacian tensor
  • Large scale tensor
  • Lojasiewicz inequality
  • Sparse tensor
  • Spherical optimization

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Cite this