Codes and Expansions (CodEx) Seminar

Gerlind Plonka-Hoch (Universität Göttingen)
Optimal Rank-\(1\) Hankel Approximation of Matrices

We consider the problem of optimal structured low-rank approximation which occurs for example in system identification and signal processing. In this talk we focus on approximation with rank-\(1\) Hankel matrices. It is well-known that (unstructured) low rank approximation of \(N \times M\) matrices can be obtained using the singular value decomposition (SVD), and the Eckhart-Young-Mirsky Theorem shows that this approach gives an optimal solution for the spectral norm and for the Frobenius norm.

However, if the low-rank approximation is assumed to have Hankel structure, SVD cannot longer be used, since it usually destroys the wanted matrix structure. There exist different approaches to tackle this structured low-rank approximation problem. A formulation using a functional leads to a non-convex minimization problem which is for example solved by a local smoothing approach and the Levenberg-Marquardt algorithm (known as structured total least squares approach) or by relaxation methods (including subspace methods or nuclear norm based methods). Practically, the Cadzow algorithm is widely used, which can be viewed as an alternating projection method.In this talk we focus on approximation with rank-\(1\) Hankel matrices. We present efficient algorithms to obtain optimal solutions for the rank-\(1\) approximation problem for the Frobenius norm and the spectral norm. In particular, we show that optimal solutions for these two norms do usually not coincide.

Further, we show that the Cadzow algorithm always converges in this case, but it converges neither to the optimal solution with regard to the Frobenius norm nor the spectral norm. The Cadzow algorithm only gives the optimal solution if the iteration stops after one step, i.e., if the rank-\(1\) approximation obtained from the usual SVD has already Hankel structure.

These results have been obtained jointly with Hanna Knirsch and Markus Petz (University of Göttingen).