A Smooth Approximation Algorithm of Rank-Regularized Optimization Problem and Its Applications

In this paper, we propose a novel smooth approximation algorithm of rank-regularized optimization problem. Rank has been a popular candidate of regularization for image processing problems,especially for images with periodical textures. But the low-rank optimization is difficult to solve, because the rank is nonconvex and can’t be formulated in closed form. The most popular methods is to adopt the nuclear norm as the approximation of rank, but the optimization of nuclear norm is also hard, it’s time expensive as it needs computing the singular value decomposition at each iteration. In this paper, we propose a novel direct regularization method to solve the low-rank optimization. Contrast to the nuclear-norm approximation, a continuous approximation for rank regularization is proposed. The new method proposed in this paper is a ‘direct’ solver to the rank regularization, and it just need computing the singular value decomposition one time, so it’s more efficient. We analyze the choosing criteria of parameters, and propose an adaptive algorithm based on Morozov discrepancy principle. Finally, numerical experiments have been done to show the efficiency of our algorithm and the performance on applications of image denoising.