Composite Schatten-p norm factorization for efficient matrix completion

Schatten- p norm optimization has emerged as an effective non-convex relaxation for low-rank matrix completion. However, the primary computational bottleneck arises from repeated singular value decomposition (SVD) operations required during optimization, which leads to high computational cost. In this work, we propose a novel factorized reformulation of the Schatten- p norm by decomposing it into combinations of nuclear and Frobenius norms. Specifically, we investigate three distinct decomposition schemes: the sum of two nuclear norms, the sum of two Frobenius norms, and the combination of a nuclear norm and a Frobenius norm. Based on these formulations, we develop an alternating gradient descent algorithm with rigorous convergence guarantees. By avoiding SVD, the proposed method significantly reduces computational complexity. Extensive experiments on synthetic datasets, image inpainting tasks, and recommender systems demonstrate that our approach consistently outperforms several is the state-of-the-art matrix completion methods in terms of both accuracy and computational efficiency.