Low-Rank Matrix Recovery via Efficient Schatten p-Norm Minimization

By Feiping Nie, Heng Huang, Chris H. Q. Ding. AAAI Conference on Artificial Intelligence, 2012

355 citations recorded by the source corpus.

As an emerging machine learning and information retrieval technique, the matrix completion has been successfully applied to solve many scientific applications, such as collaborative prediction in information retrieval, video completion in computer vision, \emph{etc}. The matrix completion is to recover a low-rank matrix with a fraction of its entries arbitrarily corrupted. Instead of solving the popularly used trace norm or nuclear norm based objective, we directly minimize the original formulations of trace norm and rank norm. We propose a novel Schatten $p$-Norm optimization framework that unifies different norm formulations. An efficient algorithm is derived to solve the new objective and followed by the rigorous theoretical proof on the convergence. The previous main solution strategy for this problem requires computing singular value decompositions - a task that requires increasingly cost as matrix sizes and rank increase. Our algorithm has closed form solution in each iteration, hence it converges fast. As a consequence, our algorithm has the capacity of solving large-scale matrix completion problems. Empirical studies on the recommendation system data sets demonstrate the promising performance of our new optimization framework and efficient algorithm.

Subfields: Artificial Intelligence, Computational Mathematics, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/658339c73021674da17354eaaffc3cd326332117

How researchers see this paper

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

In Artificial Intelligence

1. Yi Yang
2. Feiping Nie
3. Heng Huang
4. Lei Zhang
5. Hua Wang
6. Alexander G. Hauptmann
7. Shuicheng Yan
8. Wangmeng Zuo

In Computational Mathematics

1. Lei Zhang
2. Wangmeng Zuo
3. Shuhang Gu
4. Yuan Xie
5. Shuicheng Yan
6. Feiping Nie
7. Chris H. Q. Ding
8. Heng Huang

In Computational Mechanics

1. Wangmeng Zuo
2. Lei Zhang
3. Xiangchu Feng
4. Deyu Meng
5. Shuhang Gu
6. Yuan Xie
7. Zhenming Peng
8. Landan Zhang

Citations in the corpus

• Harnessing Lab Knowledge for Real-World Action Recognition (2014, methodology): “It has been proved in Nie et al. (2012) that for any invertible matrices A and A0, the following inequality holds when 0 < p ≤ 2:”
• 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.”
• Weighted Nuclear Norm Minimization and Its Applications to Low Level Vision (2016, methodology): “For instance, (Nie et al. 2012) and (Mohan and Fazel 2012) used the Schatten-p norm, which is defined as the p norm of the singular values ( ∑ i σ p i ) 1/p, to regularize the rank of the reconstructed matrix.”
• Robust Matrix Completion via Joint Schatten p-Norm and lp-Norm Minimization (2012, background): “When p → 0, the Schatten p-norm ∥X∥pSp will approximate the rank ofX [13].”
• Weighted Schatten $p$ -Norm Minimization for Image Denoising and Background Subtraction (2015, methodology): “Therefore, it has been proposed in [23], [28], [29], and [31] to enforce low rank regularization by using the Schatten p-norm, which is defined as the l p norm of the singular values ( ∑ i σ p i ) 1/p with 0 < p ≤ 1.”
• Approximating the Spectral Sums of Large-scale Matrices using Chebyshev Approximations (2016, methodology): “The Schatten p-norm (Σf (A)2/p for f(x) = xp/2 for p ≥ 1 ) has been applied to recover low-rank matrix [36] and sparse MRI reconstruction [32].”