Rank constrained nuclear norm minimization with application to image denoising

In the low rank matrix approximation problem, the well known nuclear norm minimization (NNM) problem plays a crucial role and attracts significant interests in recent years. In NNM the regularization parameter λ plays a decisive part, λ controls both the rank of the solution and the extent of the thresholding. However, it is hard for a single λ to balance the two issuses, and meanwhile the solving method calls singular value decomposition (SVD), of which the computational complexity is impracticable when the scale of the problem becomes large. This paper presents a rank constrained nuclear norm minimization (RNNM) method, in which the rank and the extent of thresholding are controlled separately by an added parameter k. More importantly, by proving its equivalence with an unconstrained bi-convex optimization problem RNNM can be solved in SVD free manner. In this paper, a SOR (Successive Over Relaxation) algorithm is designed for the equivalent bi-convex problem and its convergence is proved. We show that RNNM has a unique global optimal solution although being non-convex. We explicitly analyse the structure of the solution for the bi-convex problem and show some interesting properties. Finally, we verify the effectiveness of RNNM in image denoising. Experimental results show that the proposed solving method works faster than SVD based method. Thanks to the well balance of rank and thresholding, RNNM achieves superior results than the state-of-the-art methods in image denoising such as BM3D, SAIST in terms of both quantity measure and visual quality.