Robust estimation of GCD with sparse coefficients

Abstract

We propose a two-step algorithm for the problem of estimating the greatest common divisor (GCD) of noise-corrupted polynomials. In the first step, an initial estimate is obtained by L2-norm minimization of a quadratic function. In the second step, a refined estimate is obtained by L1-norm convex optimization which has been proven in compressed sensing techniques to be able to produce robust sparse solutions. The second step is made possible by estimating the coefficients of the quotient polynomials and constructing a linear relationship between the data vector (formed by the polynomials' coefficients) and the target vector (formed by the coefficients of the GCD). For GCDs with sparse coeffic..