  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.
