Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization

By Yao Hu, Debing Zhang, Jieping Ye, Xuelong Li, Xiaofei He. 2013

810 citations recorded by the source corpus.

Recovering a large matrix from a small subset of its entries is a challenging problem arising in many real applications, such as image inpainting and recommender systems. Many existing approaches formulate this problem as a general low-rank matrix approximation problem. Since the rank operator is nonconvex and discontinuous, most of the recent theoretical studies use the nuclear norm as a convex relaxation. One major limitation of the existing approaches based on nuclear norm minimization is that all the singular values are simultaneously minimized, and thus the rank may not be well approximated in practice. In this paper, we propose to achieve a better approximation to the rank of matrix by truncated nuclear norm, which is given by the nuclear norm subtracted by the sum of the largest few singular values. In addition, we develop a novel matrix completion algorithm by minimizing the Truncated Nuclear Norm. We further develop three efficient iterative procedures, TNNR-ADMM, TNNR-APGL, and TNNR-ADMMAP, to solve the optimization problem. TNNR-ADMM utilizes the alternating direction method of multipliers (ADMM), while TNNR-AGPL applies the accelerated proximal gradient line search method (APGL) for the final optimization. For TNNR-ADMMAP, we make use of an adaptive penalty according to a novel update rule for ADMM to achieve a faster convergence rate. Our empirical study shows encouraging results of the proposed algorithms in comparison to the state-of-the-art matrix completion algorithms on both synthetic and real visual datasets.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Semantic Image Inpainting with Deep Generative Models (2016, methodology): “We compare our method with TV inpainting [1] and LR inpainting [24, 12] on images with small random holes.”
Infrared Small Target Detection via Non-Convex Rank Approximation Minimization Joint l2, 1 Norm (2018, methodology): “The existing single-frame-based detection algorithms mainly fall into three main groups: methods of background-based assumption, methods of target-based assumption, and methods of target and background separating.”
Kronecker-Basis-Representation Based Tensor Sparsity and Its Applications to Tensor Recovery (2018, background): “Various ameliorations have been further proposed for this task [28], [38].”
Multi-Stage Multi-Task Learning with Reduced Rank (2016, methodology): “…show that at each stage of the proposed algorithm, the subproblem reduces to a problem regularized with the truncated trace norm (Zhang et al. 2012; Hu et al. 2013), and we use an alternating optimization method to solve the subproblems in a way similar to (Zhang et al. 2012; Hu et al. 2013).”
Artificial intelligence in recommender systems (2020, background): “A classic scenario in CF is to predict a user’s ratings on unconsumed items from a user-item rating matrix, which is related to the matrix completion problem [17].”
L1−2 minimization for exact and stable seismic attenuation compensation (2018, background): “They include Lp (Chartrand 2007; Foucart & Lai 2009; Lai et al. 2013; Woodworth & Chartrand 2016), log-sum penalty (LSP, Candes et al. 2008), truncated L1 (Wang & Yin 2010; Hu et al. 2013), capped L1 minimization (Zhang 2010b) and minimax concave penalty (Zhang 2010a).”
Semantic Image Inpainting with Perceptual and Contextual Losses (2016, methodology): “Certain subsets of images could also contain special properties, such as being planar [12] or having a low rank structure [11]; reconstruction results can be greatly improved by taking into consideration these prior knowledge.”
LR3M: Robust Low-Light Enhancement via Low-Rank Regularized Retinex Model (2020, background): “Zhang et al. further utilized the truncated nuclear norm [31], [32] to minimize the sum of small singular values.”
Nonconvex Nonsmooth Low Rank Minimization via Iteratively Reweighted Nuclear Norm (2015, methodology): “We follow the experimental settings in [31].”
Generalized Nonconvex Nonsmooth Low-Rank Minimization (2014, methodology): “The alternative updating algorithm in [16] minimizes the truncated nuclear norm by using a special property of this penalty.”