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).