Rank-Restricted Hierarchical Alternating Least Squares Algorithm for Matrix Completion with Applications

The matrix completion problem aims to recover missing entries in a partially observed matrix by approximating it with a low-rank structure. The two common approaches—the singular value thresholding and matrix factorization with alternating least squares—often become prohibitively expensive for large matrices or when rigorous accuracy is demanded. To address these issues, we propose a rank-restricted hierarchical alternating least squares with orthogonality and sparsity constraints, which includes a novel shrinkage function. Specifically, for faster execution speed, truncated factor matrices are updated to restrict the costly shrinkage step as well as boundary-condition heuristics. Experiments on image completion and recommender systems show that the proposed method converges with extremely fast execution speed while achieving comparable or superior reconstruction accuracy relative to state-of-the-art matrix completion methods. For example, in the image completion problem, the proposed algorithm produced outputs approximately 15 times faster on average than the most accurate reference algorithm, while achieving 98% of its accuracy.