An alternating direction method for linear-constrained matrix nuclear norm minimization

作者：Xiao Yun Hai^*; Jin Zheng Fen

来源：Numerical Linear Algebra with Applications, 2012, 19(3): 541-554.

DOI：10.1002/nla.783

• nuclear norm minimization
• matrix completion
• singular value thresholding
• augmented Lagrangian function
• alternating direction method
• Barzilai-Borwein method

The aim of the nuclear norm minimization problem is to find a matrix that minimizes the sum of its singular values and satisfies some constraints simultaneously. Such a problem has received more attention largely because it is closely related to the affine rank minimization problem, which appears in many control applications including controller design, realization theory, and model reduction. In this paper, we first propose an exact version alternating direction method for solving the nuclear norm minimization problem with linear equality constraints. At each iteration, the method involves a singular value thresholding and linear matrix equations which are solved exactly. Convergence of the proposed algorithm is followed directly. To broaden the capacity of solving larger problems, we solve approximately the subproblem by an iterative method with the BarzilaiBorwein steplength. Some extensions to the noisy problems and nuclear norm regularized least-square problems are also discussed. Numerical experiments and comparisons with the state-of-the-art method FPCA show that the proposed method is effective and promising.

• 出版日期2012-5
• 单位河南大学