A nearly optimal algorithm to decompose binary forms. (July 2021)

• Record Type: Journal Article
• Authors: Bender, Matías R.; Faugère, Jean-Charles; Perret, Ludovic; Tsigaridas, Elias
• Is Part Of: Journal of symbolic computation. Volume 105(2021)
• Page Start: 71
• Page End: 96
• Publication Date: 2021-07
• Subjects: Decomposition of binary forms -- Tensor decomposition -- Symmetric tensor rank -- Polynomial Waring's problem -- Hankel matrix -- Algebraic degree; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2020.06.002
• Languages: English
• ISSNs: 0747-7171

Abstract

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, that is, symmetric tensors of order D over the vector space K 2 . Under this formulation, the problem finds its roots in invariant theory where the decompositions are related to canonical forms. We introduce a superfast algorithm that exploits 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, it is randomized. We also present a Monte Carlo variant as well as a modification to make it a Las Vegas one. From the symbolic decomposition, we approximate the terms of the decomposition with an error of 2 − ε, in O ( D log 2 ⁡ ( D ) ( log 2 ⁡ ( D ) + log ⁡ ( ε ) ) ) 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 ⁡ ( r a n k, D − r a n k + 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 ˜ B ( D ℓ + D 4 + D 3 τ ) bit operations, where τ is the maximum bitsize of the coefficients and 2 − ℓ is the relative error of the terms in the decomposition.