A quadratically convergent algorithm for structured low-rank approximation (Q285440)

The following problem is considered: Let \({\mathcal M}_{p,q}(\mathbb{R})\) be the space of \(p \times q\) matrices with real entries and the inner product \(\langle M_1,M_2\rangle = \mathrm{trace}(M_1 \cdot M_2^T)\), let \({\mathcal D}_r \subset {\mathcal M}_{p,q}(\mathbb{R})\) be the set of \(p\times q\) matrices with rank \(r\) and let \(E \subset {\mathcal M}_{p,q}(\mathbb{R})\) be an affine subspace of \({\mathcal M}_{p,q}(\mathbb{R})\). Find for a given matrix \(M \in E\) and an \(r \in \mathbb{N}\) a matrix \(M^\prime \in E \cap {\mathcal D}_r\) such that \(\| M - M^\prime \| = \sqrt{\langle M - M^\prime,M - M^\prime \rangle}\) is small. For solving this problem a Newton-like algorithm is proposed. It is shown that the iterates of this algorithm converge quadratically to such a matrix \(M^\prime\). Additionally, it is shown that the norm of the difference between the limit \(M_\infty\) of the iteration and the optimal solution of the problem is bounded by \(\gamma^\prime \mathrm{dist}(M_0,E\cap {\mathcal D}_r)^2\), where \(\gamma^\prime\) is a positive constant, \(\mathrm{dist}(M_0,E \cap {\mathcal D}_r)\) is the distance of the matrix \(M_0\) to the set \(E \cap {\mathcal D}_r\), and \(M_0\) is the initial guess of the iteration. Furthermore, the cost of arithmetical operations of the proposed algorithm is analysed. Finally, some applications of the algorithm, namely approximate greatest common divisor, low-rank matrix completion, and low-rank approximation of Hankel matrices are presented. The convergence behaviour of the Newton-like algorithm is demonstrated and the proposed algorithm is compared with other algorithms known from the literature.