A Superfast Randomized Algorithm to Decompose Binary Forms

Matías Bender 1 Jean-Charles Faugère 1 Ludovic Perret 1 Elias Tsigaridas 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : Symmetric Tensor Decomposition is a major problem that arises in areas such as signal processing, statistics, data analysis and computational neuroscience. It is equivalent 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 consider the decomposition of binary forms, that corresponds to the decomposition of symmetric tensors of dimension 2 and order D. This problem has its roots in Invariant Theory, where the decom-positions are known as canonical forms. As part of that theory, different algorithms were proposed for the binary forms. In recent years, those algorithms were extended for the general symmetric tensor decomposition problem. We present a new randomized algorithm that enhances the previous approaches with results from structured linear algebra and techniques from linear recurrent sequences. It achieves a softly linear arithmetic complexity bound. To the best of our knowledge, the previously known algorithms have quadratic complexity bounds. We compute a symbolic minimal decomposition in O(M(D) log(D)) arithmetic operations, where M(D) is the complexity of multiplying two polynomials of degree D. We approximate the terms of the decomposition with an error of 2 −ε , in O D log 2 (D) log 2 (D) + log(ε) arithmetic operations. To bound the size of the representation of the coefficients involved in the decomposition, we bound the algebraic degree of the problem by min(rank, D − rank + 1). 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.
Type de document :
Communication dans un congrès
ISSAC '16 - 41st International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, Canada. ACM, pp.79-86, 2016, 〈10.1145/2930889.2930896〉
Liste complète des métadonnées

Littérature citée [35 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01363545
Contributeur : Matías Bender <>
Soumis le : vendredi 9 septembre 2016 - 17:54:30
Dernière modification le : mercredi 21 mars 2018 - 18:58:22
Document(s) archivé(s) le : samedi 10 décembre 2016 - 13:04:22

Fichier

binaryFormDecomposition.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Matías Bender, Jean-Charles Faugère, Ludovic Perret, Elias Tsigaridas. A Superfast Randomized Algorithm to Decompose Binary Forms. ISSAC '16 - 41st International Symposium on Symbolic and Algebraic Computation, Jul 2016, Waterloo, Canada. ACM, pp.79-86, 2016, 〈10.1145/2930889.2930896〉. 〈hal-01363545〉

Partager

Métriques

Consultations de la notice

327

Téléchargements de fichiers

85