Computing eigenvalues of large scale sparse tensors arising from a hypergraph
From MaRDI portal
eigenvaluehypergraphLaplacian tensorL-BFGSspherical optimizationlarge scale tensorsparse tensorŁojasiewicz inequality
Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35) Eigenvalues, singular values, and eigenvectors (15A18) Multilinear algebra, tensor calculus (15A69) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Methods of quasi-Newton type (90C53) Hypergraphs (05C65)
Abstract: The spectral theory of higher-order symmetric tensors is an important tool to reveal 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. 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 Kurdyka-{L}ojasiewicz property, we prove that the sequence of iterates generated by CEST converges to an eigenvector of the tensor.When CEST is started from multiple randomly 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 corresponding to a hypergraph with millions of vertices.
Recommendations
- Computing the largest H-eigenvalue of large-scale tensors generated from directed hypergraphs
- Spectral theory of weighted hypergraphs via tensors
- A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test.
- An adaptive cubic regularization algorithm for computing H- and Z-eigenvalues of real even-order supersymmetric tensors
- On spectral hypergraph theory of the adjacency tensor
Cites work
- scientific article; zbMATH DE number 5223994 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 3371284 (Why is no real title available?)
- 3-D Object Retrieval and Recognition With Hypergraph Analysis
- A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion
- A feasible method for optimization with orthogonality constraints
- A quadratically convergent algorithm for finding the largest eigenvalue of a nonnegative homogeneous polynomial map
- A sequential subspace projection method for extreme Z-eigenvalues of supersymmetric tensors.
- Adaptive Hypergraph Learning and its Application in Image Classification
- All real eigenvalues of symmetric tensors
- An adaptive shifted power method for computing generalized tensor eigenpairs
- An always convergent algorithm for the largest eigenvalue of an irreducible nonnegative tensor
- An unconstrained optimization approach for finding real eigenvalues of even order symmetric tensors
- Approximate hypergraph partitioning and applications
- Computing extreme eigenvalues of large scale Hankel tensors
- Computing tensor eigenvalues via homotopy methods
- Consistency of spectral clustering in stochastic block models
- Convergence of the Iterates of Descent Methods for Analytic Cost Functions
- Efficient algorithms for computing the largest eigenvalue of a nonnegative tensor
- Eigenvalues of a real supersymmetric tensor
- Finding the largest eigenvalue of a nonnegative tensor
- Generalized tensor eigenvalue problems
- Laplacian and signless Laplacian Z-eigenvalues of uniform hypergraphs
- Most tensor problems are NP-hard
- Multilinear PageRank
- On eigenvalue problems of real symmetric tensors
- On spectral hypergraph theory of the adjacency tensor
- On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
- On the largest eigenvalue of a symmetric nonnegative tensor.
- On the limited memory BFGS method for large scale optimization
- Partitioning hypergraphs in scientific computing applications through vertex separators on graphs
- Perron-Frobenius theorem for nonnegative multilinear forms and extensions
- Primitivity, the Convergence of the NQZ Method, and the Largest Eigenvalue for Nonnegative Tensors
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Shifted power method for computing tensor eigenpairs
- Some spectral properties and characterizations of connected odd-bipartite uniform hypergraphs
- Spectra of uniform hypergraphs
- Spectral clustering and the high-dimensional stochastic blockmodel
- The \(H\)-spectra of a class of generalized power hypergraphs
- The clique and coclique numbers' bounds based on the H-eigenvalues of uniform hypergraphs
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
- Two-Point Step Size Gradient Methods
- Updating Quasi-Newton Matrices with Limited Storage
- Z-eigenvalue methods for a global polynomial optimization problem
- \(H^{+}\)-eigenvalues of Laplacian and signless Laplacian tensors
- \(M\)-tensors and nonsingular \(M\)-tensors
- \(M\)-tensors and some applications
Cited in
(22)- A combinatorial method for computing characteristic polynomials of starlike hypergraphs
- A tensor optimization algorithm for computing Lagrangians of hypergraphs
- A trust region algorithm for computing extreme eigenvalues of tensors
- Eigenvalue bounds of third-order tensors via the minimax eigenvalue of symmetric matrices
- A family of gradient methods using Householder transformation with application to hypergraph partitioning
- Computing the \(p\)-spectral radii of uniform hypergraphs with applications
- A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test.
- Computing extreme eigenvalues of large scale Hankel tensors
- The Fiedler vector of a Laplacian tensor for hypergraph partitioning
- Computing the largest H-eigenvalue of large-scale tensors generated from directed hypergraphs
- The \(Z\)-eigenvalues of a symmetric tensor and its application to spectral hypergraph theory.
- \(H\)-eigenvalue inclusion sets for sparse tensors
- Hypergraph clustering using a new Laplacian tensor with applications in image processing
- Hyperspectral super-resolution via low rank tensor triple decomposition
- Riemannian conjugate gradient methods for computing the extreme eigenvalues of symmetric tensors
- Even order uniform hypergraph via the Einstein product
- Computing all Laplacian H-eigenvalues for a uniform loose path of length three
- A derivative-free algorithm for spherically constrained optimization
- Locally Optimal Eigenpairs of Orthogonally Decomposable Tensors: A Generalized Proof
- Finding all \(H\)-eigenvalues of signless Laplacian tensor for a uniform loose path of length three
- An adaptive cubic regularization algorithm for computing H- and Z-eigenvalues of real even-order supersymmetric tensors
- Spectral theory of weighted hypergraphs via tensors
This page was built for publication: Computing eigenvalues of large scale sparse tensors arising from a hypergraph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2833535)
