Scalable Algorithms for Tractable Schatten Quasi-Norm Minimization

Abstract

The Schatten-p quasi-norm $(0<p<1)$ is usually used to replace the standard nuclear norm in order to approximate the rank function more accurately. However, existing Schatten-p quasi-norm minimization algorithms involve singular value decomposition (SVD) or eigenvalue decomposition (EVD) in each iteration, and thus may become very slow and impractical for large-scale problems. In this paper, we first define two tractable Schatten quasi-norms, i.e., the Frobenius/nuclear hybrid and bi-nuclear quasi-norms, and then prove that they are in essence the Schatten-2/3 and 1/2 quasi-norms, respectively, which lead to the design of very efficient algorithms that only need to update two much smaller factor matrices. We also design two efficient proximal alternating linearized minimization algorithms for solving representative matrix completion problems. Finally, we provide the global convergence and performance guarantees for our algorithms, which have better convergence properties than existing algorithms. Experimental results on synthetic and real-world data show that our algorithms are more accurate than the state-of-the-art methods, and are orders of magnitude faster.

16 pages, 5 figures, Appears in Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), Phoenix, Arizona, USA, pp. 2016--2022, 2016

Cited by in corpus (9)

• Quaternion-based bilinear factor matrix norm minimization for color image inpainting
• Unified Scalable Equivalent Formulations for Schatten Quasi-Norms
• Entropy Penalized Semidefinite Programming
• Tractable and Scalable Schatten Quasi-Norm Approximations for Rank Minimization
• A Unified Convex Surrogate for the Schatten-$p$ Norm
• A Non-monotone Alternating Updating Method for A Class of Matrix Factorization Problems
• Efficient Relaxed Gradient Support Pursuit for Sparsity Constrained Non-convex Optimization
• Remarks on log Calabi--Yau structure of varieties admitting polarized endomorphism
• Low Rank Regularization: A Review