Hankel matrix rank minimization with applications to system identification and realization

Fazel Maryam, Ting Kei Pong, Defeng Sun, Paul Tseng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

223 Citations (Scopus)

Abstract

We introduce a flexible optimization framework for nuclear norm minimization of matrices with linear structure, including Hankel, Toeplitz, and moment structures and catalog applications from diverse fields under this framework. We discuss various first-order methods for solving the resulting optimization problem, including alternating direction methods of multipliers, proximal point algorithms, and gradient projection methods. We perform computational experiments to compare these methods on system identification problems and system realization problems. For the system identification problem, the gradient projection method (accelerated by Nesterov's extrapolation techniques) and the proximal point algorithm usually outperform other first-order methods in terms of CPU time on both real and simulated data, for small and large regularization parameters, respectively, while for the system realization problem, the alternating direction method of multipliers, as applied to a certain primal reformulation, usually outperforms other first-order methods in terms of CPU time. We also study the convergence of the proximal alternating direction methods of multipliers used in this paper.
Original languageEnglish
Pages (from-to)946-977
Number of pages32
JournalSIAM Journal on Matrix Analysis and Applications
Volume34
Issue number3
DOIs
Publication statusPublished - 15 Nov 2013
Externally publishedYes

Keywords

  • First-order method
  • Hankel matrix
  • Nuclear norm
  • Rank minimization
  • System identification
  • System realization

ASJC Scopus subject areas

  • Analysis

Cite this