INTERIOR-POINT METHOD FOR NUCLEAR NORMAPPROXIMATION WITH APPLICATION TO SYSTEMIDENTIFICATION

摘要

The nuclear norm (sum of singular values) of a matrix is often used in convexheuristics for rank minimization problems in control, signal processing, and statistics. Such heuristicscan be viewed as extensions of P1-norm minimization techniques for cardinality minimization andsparse signal estimation. In this paper we consider the problem of minimizing the nuclear norm ofan affine matrix-valued function. This problem can be formulated as a semidefinite program, but thereformulation requires large auxiliary matrix variables, and is expensive to solve by general-purposeinterior-point solvers. We show that problem structure in the semidefinite programming formulationcan be exploited to develop more efficient implementations of interior-point methods. In the fastimplementation, the cost per iteration is reduced to a quartic function of the problem dimensions andis comparable to the cost of solving the approximation problem in the Frobenius norm. In the secondpart of the paper, the nuclear norm approximation algorithm is applied to system identification. Avariant of a simple subspace algorithm is presented in which low-rank matrix approximations arecomputed via nuclear norm minimization instead of the singular value decomposition. This hasthe important advantage of preserving linear matrix structure in the low-rank approximation. Themethod is shown to perform well on publicly available benchmark data.