A nearly optimal algorithm to decompose binary forms

DOI10.1016/J.JSC.2020.06.002zbMATH Open1461.14080arXiv1810.12588OpenAlexW3036808918MaRDI QIDQ1994885FDOQ1994885

Authors: Matías R. Bender, Jean-Charles Faugère, Ludovic Perret, Elias P. Tsigaridas 

Publication date: 18 February 2021

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: Symmetric tensor decomposition is an important problem with applications in several areas for example signal processing, statistics, data analysis and computational neuroscience. It is equivalent to Waring's problem for homogeneous polynomials, that is to write a homogeneous polynomial in n variables of degree D as a sum of D-th powers of linear forms, using the minimal number of summands. This minimal number is called the rank of the polynomial/tensor. We focus on decomposing binary forms, a problem that corresponds to the decomposition of symmetric tensors of dimension 2 and order D. Under this formulation, the problem finds its roots in invariant theory where the decompositions are known as canonical forms. In this context many different algorithms were proposed. We introduce a superfast algorithm that improves the previous approaches with results from structured linear algebra. It achieves a softly linear arithmetic complexity bound. To the best of our knowledge, the previously known algorithms have at least quadratic complexity bounds. Our algorithm computes a symbolic decomposition in $O(M(D)log(D))$ arithmetic operations, where $M(D)$ is the complexity of multiplying two polynomials of degree D. It is deterministic when the decomposition is unique. When the decomposition is not unique, our algorithm is randomized. We present a Monte Carlo version of it and we show how to modify it to a Las Vegas one, within the same complexity. From the symbolic decomposition, we approximate the terms of the decomposition with an error of $$epsilon$$ , in $O(Dlo{g}^2(D)(lo{g}^2(D)+log($epsilon$)))$ arithmetic operations. We use results from Kaltofen and Yagati (1989) to bound the size of the representation of the coefficients involved in the decomposition and we bound the algebraic degree of the problem by min(rank, D -- rank + 1). We show that this bound can be tight. When the input polynomial has integer coefficients, our algorithm performs, up to poly-logarithmic factors, $O_{bit}(Dell+D^4+D^3$ au$)$ bit operations, where ${\displaystyle }$ au${\displaystyle }$ is the maximum bitsize of the coefficients and $2^{--ell}$ is the relative error of the terms in the decomposition.

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

Recommendations

• Semialgebraic sets and real binary forms decompositions
• The Waring rank of binary binomial forms
• On the rank of a binary form
• A superfast randomized algorithm to decompose binary forms
• Binary decompositions and varieties of sums of binaries

zbMATH Keywords

binary forms

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Symbolic computation and algebraic computation (68W30) Computational aspects in algebraic geometry (14Q99) Forms of degree higher than two (11E76) Secant varieties, tensor rank, varieties of sums of powers (14N07)

Cites Work

• The Euclidean distance degree of an algebraic variety
• Power sums, Gorenstein algebras, and determinantal loci. With an appendix `The Gotzmann theorems and the Hilbert scheme' by Anthony Iarrobino and Steven L. Kleiman
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sums of even powers of real linear forms
• On the rank of a binary form
• Algebraic methods for Toeplitz-like matrices and operators
• Numerical methods for roots of polynomials. II
• Title not available (Why is that?)
• Symmetric tensor decomposition
• The algebraic degree of semidefinite programming
• Decomposition of quantics in sums of powers of linear forms
• Monomials as sums of powers: the real binary case
• On the Length of Binary Forms
• The algebraic degree of geometric optimization problems
• Modern computer algebra
• Symmetric Tensors and Symmetric Tensor Rank
• Symmetric tensors: rank, Strassen's conjecture and \(e\)-computability
• The invariant theory of binary forms
• Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding
• Eigenvectors of tensors and algorithms for Waring decomposition
• Some new canonical forms for polynomials
• Computing symmetric rank for symmetric tensors
• Homogeneous polynomial solutions to constant coefficient PDE's
• A superfast randomized algorithm to decompose binary forms
• Typical real ranks of binary forms
• Waring loci and the Strassen conjecture
• Waring's problem for binary forms
• Binary forms with three different relative ranks
• Algebraic Computations of Scaled Padé Fractions
• Interpolation of shifted-lacunary polynomials
• Homotopy techniques for tensor decomposition and perfect identifiability
• Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases
• On computing the canonical form for a binary form of odd degree
• Tensor decomposition and homotopy continuation
• Accelerated approximation of the complex roots and factors of a univariate polynomial
• Nearly optimal computations with structured matrices

Cited In (7)

• Derandomization and absolute reconstruction for sums of powers of linear forms
• Efficient prediction algorithms for binary decomposition techniques
• A linear algebra method to decompose forms whose length is lower than the number of variables into weighted sum of squares
• A superfast randomized algorithm to decompose binary forms
• Semialgebraic sets and real binary forms decompositions
• On computing the canonical form for a binary form of odd degree
• Decomposition Algorithms for Tensors and Polynomials

This page was built for publication: A nearly optimal algorithm to decompose binary forms

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