Variable projection methods for approximate (greatest) common divisor computations - CICS Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2017

Variable projection methods for approximate (greatest) common divisor computations

Résumé

We consider the problem of finding for a given N-tuple of polynomials (real or complex) the closest N-tuple that has a common divisor of degree at least d. Extended weighted Euclidean seminorm of the coefficients is used as a measure of closeness. Two equivalent representations of the problem are considered: (i) direct parameterization over the common divisors and quotients (image representation), and (ii) Sylvester low-rank approximation (kernel representation). We use the duality between least-squares and least-norm problems to show that (i) and (ii) are closely related to mosaic Hankel low-rank approximation. This allows us to apply to the approximate common divisor problem recent results on complexity and accuracy of computations for mosaic Hankel low-rank approximation. We develop optimization methods based on the variable projection principle both for image and kernel representation. These methods have linear complexity in the degrees of the polynomials for small and large d. We provide a software implementation of the developed methods, which is based on a software package for structured low-rank approximation.

Dates et versions

hal-01226429 , version 1 (09-11-2015)

Identifiants

Citer

Konstantin Usevich, Ivan Markovsky. Variable projection methods for approximate (greatest) common divisor computations. Theoretical Computer Science, 2017, 681, pp.176-198. ⟨10.1016/j.tcs.2017.03.028⟩. ⟨hal-01226429⟩
144 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More