Best nonnegative rank-one approximations of tensors
From MaRDI portal
Publication:5203971
DOI10.1137/18M1224064zbMATH Open1454.90047arXiv1810.13372OpenAlexW2992276872WikidataQ114074276 ScholiaQ114074276MaRDI QIDQ5203971FDOQ5203971
Authors: Defeng Sun, Kim-Chuan Toh, Shenglong Hu 
Publication date: 9 December 2019
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
Abstract: In this paper, we study the polynomial optimization problem of multi-forms over the intersection of the multi-spheres and the nonnegative orthants. This class of problems is NP-hard in general, and includes the problem of finding the best nonnegative rank-one approximation of a given tensor. A Positivstellensatz is given for this class of polynomial optimization problems, based on which a globally convergent hierarchy of doubly nonnegative (DNN) relaxations is proposed. A (zero-th order) DNN relaxation method is applied to solve these problems, resulting in linear matrix optimization problems under both the positive semidefinite and nonnegative conic constraints. A worst case approximation bound is given for this relaxation method. Then, the recent solver SDPNAL+ is adopted to solve this class of matrix optimization problems. Typically, the DNN relaxations are tight, and hence the best nonnegative rank-one approximation of a tensor can be revealed frequently. Extensive numerical experiments show that this approach is quite promising.
Full work available at URL: https://arxiv.org/abs/1810.13372
Recommendations
- Semidefinite relaxations for best rank-1 tensor approximations
- Properties and methods for finding the best rank-one approximation to higher-order tensors
- The best rank-1 approximation of a symmetric tensor and related spherical optimization problems
- Low-rank nonnegative tensor approximation via alternating projections and sketching
- Rank-1 tensor properties with applications to a class of tensor optimization problems
tensorpolynomialmultiformsdoubly nonnegative relaxation methoddoubly nonnegative semidefinite programnonnegative rank-1 approximation
Eigenvalues, singular values, and eigenvectors (15A18) Inequalities involving eigenvalues and eigenvectors (15A42) Multilinear algebra, tensor calculus (15A69) Semidefinite programming (90C22) Polynomial optimization (90C23)
Cites Work
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Title not available (Why is that?)
- Tensor Decompositions and Applications
- A Newton-CG augmented Lagrangian method for semidefinite programming
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- On the complexity of nonnegative matrix factorization
- Title not available (Why is that?)
- A Multilinear Singular Value Decomposition
- On the Best Rank-1 and Rank-(R1 ,R2 ,. . .,RN) Approximation of Higher-Order Tensors
- A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints
- Learning the parts of objects by non-negative matrix factorization
- Some NP-complete problems in quadratic and nonlinear programming
- Global optimization with polynomials and the problem of moments
- Title not available (Why is that?)
- Title not available (Why is that?)
- Minimizing polynomials via sum of squares over the gradient ideal
- On the best rank-1 approximation of higher-order supersymmetric tensors
- Shifted power method for computing tensor eigenpairs
- Title not available (Why is that?)
- Title not available (Why is that?)
- A new bound for Pólya's theorem with applications to polynomials positive on polyhedra.
- Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
- Biquadratic Optimization Over Unit Spheres and Semidefinite Programming Relaxations
- Symmetric nonnegative tensors and copositive tensors
- Maxima for Graphs and a New Proof of a Theorem of Turán
- On the complexity of Putinar's Positivstellensatz
- Completely positive reformulations for polynomial optimization
- On the computational complexity of membership problems for the completely positive cone and its dual
- Solution of the truncated complex moment problem for flat data
- Optimality conditions and finite convergence of Lasserre's hierarchy
- Title not available (Why is that?)
- Tensors of nonnegative rank two
- Tensor rank is NP-complete
- Semidefinite relaxations for best rank-1 tensor approximations
- Computing non-negative tensor factorizations
- Positive maps and separable matrices
- Tensor Decomposition for Signal Processing and Machine Learning
- Computing the polyadic decomposition of nonnegative third order tensors
- Positive tensor factorization
- Sum of squares methods for minimizing polynomial forms over spheres and hypersurfaces
- A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
- Convergence rate analysis for the higher order power method in best rank one approximations of tensors
- Uniqueness of Nonnegative Tensor Approximations
- A complete semidefinite algorithm for detecting copositive matrices and tensors
- Efficient Nonnegative Tucker Decompositions: Algorithms and Uniqueness
Cited In (15)
- On best rank one approximation of tensors
- A DCA-Newton method for quartic minimization over the sphere
- Relaxation of the rank-1 tensor approximation using different norms
- On the reduction of multivariate quadratic systems to best rank-1 approximation of three-way tensors
- On Orthogonal Tensors and Best Rank-One Approximation Ratio
- Convergence analysis of an SVD-based algorithm for the best rank-1 tensor approximation
- Certifying the global optimality of quartic minimization over the sphere
- Approximation of high-dimensional rank one tensors
- Subtracting a best rank‐1 approximation from p × p × 2(p≥2) tensors
- Semidefinite relaxations for best rank-1 tensor approximations
- Best Nonspherical Symmetric Low Rank Approximation
- Properties and methods for finding the best rank-one approximation to higher-order tensors
- On the best rank-1 approximation to higher-order symmetric tensors
- On the Uniqueness and Perturbation to the Best Rank-One Approximation of a Tensor
- Rank-1 tensor properties with applications to a class of tensor optimization problems
Uses Software
This page was built for publication: Best nonnegative rank-one approximations of tensors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5203971)
