Low Rank Matrix Approximation Theory And Application

Low rank matrix approximation is an important topic in machine learning, nu-merical optimization and theoretical computer science. It has both rigorous theoretical foundations and wide applications in practice. The essence of low rank matrix approx-imation is to exploit low-dimensional structure in high-dimensional space. It intends to find a proper low rank matrix to approximate the original complex matrix. The low rank matrix will preserve most properties of the original matrix, and it can also reduce the redundant information and noise, which will decrease the memory and computational cost. Recently, solving low rank matrix approximation problems by leveraging noncon-vex relaxation has received more and more attentions. Some theoretical analyses and practical experiments show that it can approximate the original problem and capture the nature of the problem better than convex relaxation. However, nonconvex optimization problems are generally complex and can hardly be solved efficiently. In this paper, we use the weighted nuclear norm that is simple, intuitive and flexible as a low rank penal-ty, based on which, we propose a unified nonconvex framework to solve the low rank matrix approximation problem. And we propose an Iterative Shrinkage Threshold-ing and Reweighted Algorithm (ISTRA) to solve the nonconvex problem. In theory, we prove that under certain assumptions the proposed ISTRA algorithm can converge to the critical point that is local optimal solution efficiently with sublinear convergence rate. In practice, matrix completion experiments on synthetic data and real image data demonstrate the accuracy and efficiency of the proposed ISTRA algorithm, which can outperform state-of-the-art methods.