Optimization Online


Hankel Matrix Rank Minimization with Applications to System Identification and Realization

Maryam Fazel (mfazel***at***ee.washington.edu)
Ting Kei Pong (tkpong***at***uw.edu)
Defeng Sun (matsundf***at***nus.edu.sg)
Paul Tseng (tseng***at***math.washington.edu)

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 problem and system realization problem. 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 directions methods of multipliers used in this paper.

Keywords: Rank minimization, nuclear norm, Hankel matrix, first-order method, system identification, system realization

Category 1: Applications -- Science and Engineering

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 08/29/2012
Entry Accepted: 08/29/2012
Entry Last Modified: 01/15/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society