Robust estimation of GCD with sparse coefficients

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 coefficients, the proposed method is shown by simulation to be more robust to noise than its general-purpose counterpart.