Structured low rank approximation

• Published in: Linear algebra and its applications 2003-06, Vol.366, p.157-172
• Main Authors: Chu, Moody T., Funderlic, Robert E., Plemmons, Robert J.
• Format: Article
• Language: English
• Subjects: Low rank approximation; Optimization techniques; Structured matrix; Toeplitz matrix
• ISSN: 0024-3795; 1873-1856
• DOI: 10.1016/S0024-3795(02)00505-0

This paper concerns the construction of a structured low rank matrix that is nearest to a given matrix. The notion of structured low rank approximation arises in various applications, ranging from signal enhancement to protein folding to computer algebra, where the empirical data collected in a matrix do not maintain either the specified structure or the desirable rank as is expected in the original system. The task to retrieve useful information while maintaining the underlying physical feasibility often necessitates the search for a good structured lower rank approximation of the data matrix. This paper addresses some of the theoretical and numerical issues involved in the problem. Two procedures for constructing the nearest structured low rank matrix are proposed. The procedures are flexible enough that they can be applied to any lower rank, any linear structure, and any matrix norm in the measurement of nearness. The techniques can also be easily implemented by utilizing available optimization packages. The special case of symmetric Toeplitz structure using the Frobenius matrix norm is used to exemplify the ideas throughout the discussion. The concept, rather than the implementation details, is the main emphasis of the paper.