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

From MaRDI portal
scientific article
Language Label Description Also known as
English
An implementable proximal point algorithmic framework for nuclear norm minimization
scientific article

    Statements

    An implementable proximal point algorithmic framework for nuclear norm minimization (English)
    0 references
    0 references
    0 references
    0 references
    26 June 2012
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    nuclear norm minimization
    0 references
    proximal point method
    0 references
    rank minimization
    0 references
    gradient projection method
    0 references
    accelerated proximal gradient method
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references