  Structured Low-Rank Approximation is a problem arising in a wide range of
applications in Numerical Analysis and Engineering Sciences. Given an input
matrix $M$, the goal is to compute a matrix $M'$ of given rank $r$ in a linear
or affine subspace $E$ of matrices (usually encoding a specific structure) such
that the Frobenius distance $\lVert M-M'\rVert$ is small. We propose a
Newton-like iteration for solving this problem, whose main feature is that it
converges locally quadratically to such a matrix under mild transversality
assumptions between the manifold of matrices of rank $r$ and the linear/affine
subspace $E$. We also show that the distance between the limit of the iteration
and the optimal solution of the problem is quadratic in the distance between
the input matrix and the manifold of rank $r$ matrices in $E$. To illustrate
the applicability of this algorithm, we propose a Maple implementation and give
experimental results for several applicative problems that can be modeled by
Structured Low-Rank Approximation: univariate approximate GCDs (Sylvester
matrices), low-rank Matrix completion (coordinate spaces) and denoising
procedures (Hankel matrices). Experimental results give evidence that this
all-purpose algorithm is competitive with state-of-the-art numerical methods
dedicated to these problems.
