An efficient truncated nuclear norm constrained matrix completion for image inpainting

Authors: Zheng, J., Qin, M., Yu, H. and Wang, W.

Journal: ACM International Conference Proceeding Series

Pages: 97-106

ISBN: 9781450364010

DOI: 10.1145/3208159.3208164


The matrix completion problem has found many applications in image and graphics fields. Developing fast and exact algorithms still remains challenging. The truncated nuclear norm (TNN), taking advantage of priori target rank information, is known as a better surrogate function to the rank constraint than the traditional nuclear norm. However, the TNN penalized algorithms always converge slowly due to the two-step scheme for avoiding directly updating the noncovex functions. In this paper, we propose a computationally efficient algorithm, Momentum Adaptive and Rank Revealing (MARR), for the TNN regularized matrix completion problem. The distinct advantages are to (1) reduce iterations by introducing non-monotonic constraints, and (2) decrease computational burden by controlling the size of matrix. Moreover, the descent property and convergence of the search are proven. Experiments on image inpainting, including images and range data, show that the proposed algorithm achieves very competitive results visually and numerically compared to several state-of-the-art approaches, while providing substantial reduction of iterations and runtime, thereby more applicable in real-world problems.

Source: Scopus