Low Rank Regularization: A review

Abstract

Low Rank Regularization (LRR), in essence, involves introducing a low rank or approximately low rank assumption to target we aim to learn, which has achieved great success in many data analysis tasks. Over the last decade, much progress has been made in theories and applications. Nevertheless, the intersection between these two lines is rare. In order to construct a bridge between practical applications and theoretical studies, in this paper we provide a comprehensive survey for LRR. Specifically, we first review the recent advances in two issues that all LRR models are faced with: (1) rank-norm relaxation, which seeks to find a relaxation to replace the rank minimization problem; (2) model optimization, which seeks to use an efficient optimization algorithm to solve the relaxed LRR models. For the first issue, we provide a detailed summarization for various relaxation functions and conclude that the non-convex relaxations can alleviate the punishment bias problem compared with the convex relaxations. For the second issue, we summarize the representative optimization algorithms used in previous studies, and analyze their advantages and disadvantages. As the main goal of this paper is to promote the application of non-convex relaxations, we conduct extensive experiments to compare different relaxation functions. The experimental results demonstrate that the non-convex relaxations generally provide a large advantage over the convex relaxations. Such a result is inspiring for further improving the performance of existing LRR models.

Keywords: Low rank; Optimization; Regularization.