An implementable proximal point algorithmic framework for nuclear norm minimization (Q431025)

The authors study inexact proximal point algorithms in the primal, dual and primal-dual forms for solving the nuclear norm minimization with linear equality and second order cone constraints. Such a problem often arises from the convex relaxation of a rank minimization problem with noisy data, and arises in many fields of engineering and science. In fact, the nuclear norm minimization problem (NNM problem, in short) is to find a matrix with a minimum nuclear norm subject to linear and second-order cone constraints. The authors design efficient implementations and present comprehensive convergence results. The contribution in this paper is three fold. First, a proximal point algorithmic framework is provided for the NNM problem with complete convergence analysis. Connections between the new algorithms and other algorithms that have been studied in the literature recently are established (the SVT algorithm and the Bregman iterative algorithm). Second, the authors introduce checkable stopping criteria that can be efficiently implemented in practice. Third, the new algorithms are often able to obtain a more accurate solution when the practical problem is contaminated with noise. The numerical results show that the proposed algorithms perform favorably in comparison to several recently proposed state-of-the-art algorithms.