Nonconvex Truncated Nuclear Norm Minimization Based on Adaptive Bisection Method

The explosive growth in high-dimensional visual data requires effective regularization techniques to utilize the underlying low-dimensional structure. We consider low-rank matrix recovery, and many existing approaches are based on the nuclear norm regularization. Recently, truncated nuclear norm (TNNR) has been proposed to achieve a better approximation to the rank function than that of the traditional nuclear norm. TNNR was defined by the nuclear norm by subtracting the sum of the largest r singular values. However, the estimation of r is not trivial. In addition, the original algorithm based on TNNR only considers the matrix completion cases and requires double loops, which is not quite computationally efficient. Correspondingly, in this paper, we propose the adaptive bisection method to adaptively estimate r, which can efficiently reduce the cost of computation. Moreover, to further accelerate computing, we apply iteratively reweighted nuclear norm to solve the nonconvex TNNR directly, and the convergence can also be guaranteed. Finally, we extend the applications of TNNR from the matrix completion problems to the general low-rank matrix recovery. Extensive experiments validate the superiority of the proposed algorithm over the state-of the-art methods.