2018/09/14 by Zaiyi Chen, Chen, Zaiyi
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #cs.CV #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1809.05292
arxiv created 2018/09/14 · openalex publication_date 2018/09/14 · arxiv updated 2018/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.