Computing eigenvalues of large scale sparse tensors arising from a hypergraph
From MaRDI portal
eigenvaluehypergraphL-BFGSLaplacian tensorlarge scale tensorsparse tensorspherical optimizationŁojasiewicz inequality
Hypergraphs (05C65) Eigenvalues, singular values, and eigenvectors (15A18) Multilinear algebra, tensor calculus (15A69) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35) Methods of quasi-Newton type (90C53)
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
- 3-D Object Retrieval and Recognition With Hypergraph Analysis
- \(H^{+}\)-eigenvalues of Laplacian and signless Laplacian tensors
- \(M\)-tensors and nonsingular \(M\)-tensors
- \(M\)-tensors and some applications
- 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
- 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?)
- 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
Cited in
(26)- Computing the \(p\)-spectral radii of uniform hypergraphs with applications
- Riemannian conjugate gradient methods for computing the extreme eigenvalues of symmetric tensors
- Computing all Laplacian H-eigenvalues for a uniform loose path of length three
- A combinatorial method for computing characteristic polynomials of starlike hypergraphs
- Eigenvalue bounds of third-order tensors via the minimax eigenvalue of symmetric matrices
- Computing the largest H-eigenvalue of large-scale tensors generated from directed hypergraphs
- A derivative-free algorithm for spherically constrained optimization
- Computing extreme eigenvalues of large scale Hankel tensors
- The Z-eigenvalues of a symmetric tensor and its application to spectral hypergraph theory.
- The Fiedler vector of a Laplacian tensor for hypergraph partitioning
- A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test.
- Hypergraph clustering using a new Laplacian tensor with applications in image processing
- Finding all \(H\)-eigenvalues of signless Laplacian tensor for a uniform loose path of length three
- A tensor optimization algorithm for computing Lagrangians of hypergraphs
- Even order uniform hypergraph via the Einstein product
- An adaptive cubic regularization algorithm for computing H- and Z-eigenvalues of real even-order supersymmetric tensors
- A family of gradient methods using Householder transformation with application to hypergraph partitioning
- Spectral theory of weighted hypergraphs via tensors
- \(H\)-eigenvalue inclusion sets for sparse tensors
- Hyperspectral super-resolution via low rank tensor triple decomposition
- Locally Optimal Eigenpairs of Orthogonally Decomposable Tensors: A Generalized Proof
- A scalable optimization approach for the multilinear system arising from scattered data interpolation
- Characterizing upper bounds of Z-spectral radius of uniform hypergraphs
- Sharp bounds and structural insights: spectral radius for directed hypergraphs
- A feasible conjugate gradient method for calculating \(\mathcal{B}\)-eigenpairs of symmetric tensors
- A trust region algorithm for computing extreme eigenvalues of 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)
