  Rank minimization (RM) is a wildly investigated task of finding solutions by
exploiting low-rank structure of parameter matrices. Recently, solving RM
problem by leveraging non-convex relaxations has received significant
attention. It has been demonstrated by some theoretical and experimental work
that non-convex relaxation, e.g. Truncated Nuclear Norm Regularization (TNNR)
and Reweighted Nuclear Norm Regularization (RNNR), can provide a better
approximation of original problems than convex relaxations. However, designing
an efficient algorithm with theoretical guarantee remains a challenging
problem. In this paper, we propose a simple but efficient proximal-type method,
namely Iterative Shrinkage-Thresholding Algorithm(ISTA), with concrete analysis
to solve rank minimization problems with both non-convex weighted and
reweighted nuclear norm as low-rank regularizers. Theoretically, the proposed
method could converge to the critical point under very mild assumptions with
the rate in the order of $O(1/T)$. Moreover, the experimental results on both
synthetic data and real world data sets show that proposed algorithm
outperforms state-of-arts in both efficiency and accuracy.
