On the complexity of finding tensor ranks

DOI10.1007/S42967-020-00103-4MaRDI QIDQ2667353zbMATH OpenOpenAlexFDO

Authors Mohsen Aliabadi, S. Friedland

Publication date 24 November 2021

Published in Communications on Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.07151

zbMATH Keywords

Gauss eliminationhomogeneous polynomialNP-hardnesssymmetric tensortensor rank

Mathematics Subject Classification ID

Solving polynomial systems; resultants (13P15) Vector spaces, linear dependence, rank, lineability (15A03) Multilinear algebra, tensor calculus (15A69) Numerical computation of solutions to systems of equations (65H10) Analysis of algorithms and problem complexity (68Q25)

Abstract: The purpose of this note is to give a linear algebra algorithm to find out if a rank of a given tensor over a field $F$ is at most $k$ over the algebraic closure of $F$, where $k$ is a given positive integer. We estimate the arithmetic complexity of our algorithm.

Recommendations

• The complexity of tensor rank
• scientific article; zbMATH DE number 1979698
• Typical tensorial rank
• On the generic and typical ranks of 3-tensors
• Border rank of m n (mn-q) tensors

Cites work

• A counterexample to Comon's conjecture
• A geometric effective Nullstellensatz
• A pure power product version of the Hilbert Nullstellensatz
• Beating brute force for systems of polynomial equations over finite fields
• Bounds for the degrees in the Nullstellensatz
• Comon's conjecture, rank decomposition, and symmetric rank decomposition of symmetric tensors
• Eigenvectors of tensors and algorithms for Waring decomposition
• Fundamental tensor operations for large-scale data analysis using tensor network formats
• Gaussian elimination is not optimal
• Generating polynomials and symmetric tensor decompositions
• scientific article; zbMATH DE number 5968745 (Why is no real title available?)
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• Linear Algebra and Matrices
• Nuclear norm of higher-order tensors
• On the generic and typical ranks of 3-tensors
• Relative bilinear complexity and matrix multiplication.
• Remarks on the symmetric rank of symmetric tensors
• Sharp Effective Nullstellensatz
• Spectral norm of a symmetric tensor and its computation
• Sums of even powers of real linear forms
• Symmetric Tensors and Symmetric Tensor Rank
• Systems of distinct representatives and linear algebra
• Tensor rank is NP-complete
• The complexity of tensor rank

Cited in

(15)

• Explicit tensors
• Tensor rank is NP-complete
• On Tensor-Train Ranks of Tensorized Polynomials
• Lower bounds for polar and tensor ranks
• scientific article; zbMATH DE number 4057703 (Why is no real title available?)
• scientific article; zbMATH DE number 1979698 (Why is no real title available?)
• Tensor rank is hard to approximate
• scientific article; zbMATH DE number 7387190 (Why is no real title available?)
• Polynomial bound for the partition rank vs the analytic rank of tensors
• On the average condition number of tensor rank decompositions
• On semidefinite programming characterizations of the numerical radius and its dual norm
• Rank of a tensor and quantum entanglement
• Notions of tensor rank
• Several remarks on tensor rank computation
• The complexity of tensor rank

This page was built for publication: On the complexity of finding tensor ranks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2667353)