An Approximate Decomposition of a Multivariate Polynomial Based on Structured Low-Rank Approximation

A multivariate polynomial $f$ is decomposable if $f$ is a composition $f=u\circ h$ , where $u$ is a univariate polynomial of degree greater than one and $h$ is a multivariate polynomial. We consider the problem of computing the nearest decomposable polynomial to a given multivariate polynomial with respect to the 2-norm. By using the relationship between the decomposability of a polynomial and the rank of a structured matrix corresponding to the polynomial, we reduce this problem to the structured low-rank approximation problem. Then we propose algorithms for computing an approximate decomposition of a multivariate polynomial based on the structured low-rank approximation problem.