First-order methods for nuclear norm minimization and its applications

We consider a nuclear norm minimization problem that can be viewed as convex relaxation of rank minimization problem arising in many fields in engineering and applied science. Though this problem can be reformulated as semidefinite programming (SDP) problem, it is computationally challenging for general SDP solvers due to the size of this problem. In this thesis, we study first-order methods for nuclear norm minimization problem. In particular, we first propose several reformulations for this problem. Then we apply two suitabe first-order methods, namely, fast iterative shrinkage algorithm (FISTA) and nonmonotone gradient method (NGM) for solving these reformulations. Finally, we compare the performance of these approaches on randomly generated instances and report some promising computational results.