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.

本文针对大规模问题，定义了容易处理的 Frobenius / 核混合和双核范数，通过更新两个较小的因子矩阵，设计了两种代表矩阵完成问题的高效近端交替线性化最小化算法，证明它们优于现有算法，具有更好的收敛性和性能保证。