Research On Gradient Methods For Matrix Nuclear Norm Minimization Problems

In this thesis,we propose a couple of gradient-type methods for matrix nuclear norm minimization problems:accelerated linear alternating direction method of multipliers and two-step proximal gradient algorithm.We analyze the global convergence of both proposed algorithm and test their numerical performance.In the first Chapter,we introduce the significance of our research on matrix rank minimization problem,including the models of matrix rank minimization problem and some existing effective methods for its solution.We also briefly introduce the iterative scheme of alternating direction method of multipliers and proximal gradient algorithms,and list some important symbols which are used in the thesis.In Chapter two,we propose an accelerated alternating direction method of multipli-ers for solving linear-constrained matrix nuclear norm minimization.After the iteration of Gauss-Seidel,we apply an accelerated proximal gradient algorithm to improve the ef-ficiency of the algorithm.At each iteration,a singular value decomposition is involved.We show that the proposed algorithm converges globally and illustrate the efficiency of the algorithm via a series of numerical experiments.In Chapter three,combining the fixed point continuation algorithm(FPCA)of Ma,Goldfarb&Chen with the idea of the well-known two-step iterative threshold algorithm(TwIST)of Bioucas-Dias&Figueiredo,we develop a two-step proximal gradient algo-rithm which is mainly used for solving matrix completion problem.Under appropriate conditions,we establish the global convergence of the algorithm.Numerical comparisons illustrate the efficiency of the proposed method and the experiments illustrate that the proposed method is competitive with FPCA.In Chapter four,we give a summary of this thesis.List some further research topics.