A Newton-like iteration and algebraic methods for Structured Low-Rank Approximation

par M. Pierre-Jean Spaenlehauer (INRIA Nancy)

jeudi 6 mars 2014, 10:30 → 11:30 Europe/Paris

XR.203 (Bâtiment XLIM)

Given an linear/affine space of matrices E with real entries, a data matrix U in E and a target rank r, the Structured Low-Rank Approximation Problem consists in computing a matrix M in E which is close to U (with respect to the Frobenius norm) and has rank at most r. This problem appears with different flavors in a wide range of applications in Engineering Sciences and symbolic/numeric computations. We propose an SVD-based numerical iterative method which converges locally towards such a matrix M. This iteration combines features of the alternating projections algorithm and of Newton's method, leading to a proven local quadratic rate of convergence under mild tranversality assumptions. We also present experimental results which indicate that, for some range of parameters, this general algorithm is competitive with numerical methods for approximate univariate GCDs and low-rank matrix completion (which are instances of Structured Low-Rank Approximation). In a second part of the talk, we focus on the algebraic structure and on exact methods to compute symbolically the nearest structured low-rank matrix M to a given matrix U in E with rational entries. We propose several ways to recast this problem as a system of polynomial equations in order to solve with Gröbner bases software. The first part of the talk is a joint work with Eric Schost, the second part is a joint work with Giorgio Ottaviani and Bernd Sturmfels.