Journal
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS
Volume 31, Issue 3, Pages 1235-1256Publisher
SIAM PUBLICATIONS
DOI: 10.1137/090755436
Keywords
semidefinite programming; interior-point methods; nuclear norm approximation; matrix rank minimization; system identification; subspace algorithm
Categories
Funding
- NSF [ECS-0524663, ECCS-0824003]
- Northrop Grumman
Ask authors/readers for more resources
The nuclear norm (sum of singular values) of a matrix is often used in convex heuristics for rank minimization problems in control, signal processing, and statistics. Such heuristics can be viewed as extensions of l(1)-norm minimization techniques for cardinality minimization and sparse signal estimation. In this paper we consider the problem of minimizing the nuclear norm of an affine matrix-valued function. This problem can be formulated as a semidefinite program, but the reformulation requires large auxiliary matrix variables, and is expensive to solve by general-purpose interior-point solvers. We show that problem structure in the semidefinite programming formulation can be exploited to develop more efficient implementations of interior-point methods. In the fast implementation, the cost per iteration is reduced to a quartic function of the problem dimensions and is comparable to the cost of solving the approximation problem in the Frobenius norm. In the second part of the paper, the nuclear norm approximation algorithm is applied to system identification. A variant of a simple subspace algorithm is presented in which low-rank matrix approximations are computed via nuclear norm minimization instead of the singular value decomposition. This has the important advantage of preserving linear matrix structure in the low-rank approximation. The method is shown to perform well on publicly available benchmark data.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available