A two-phase rank-based algorithm for low-rank matrix completion

DOI10.1007/S11590-022-01959-6arXiv2202.09405MaRDI QIDQ6164963FDOQ6164963

Authors: Tacildo de S. Araújo, Douglas S. Gonçalves, Cristiano Torezzan 

Publication date: 28 July 2023

Published in: Optimization Letters (Search for Journal in Brave)

Abstract: Matrix completion aims to recover an unknown low-rank matrix from a small subset of its entries. In many applications, the rank of the unknown target matrix is known in advance. In this paper, first we revisit a recently proposed rank-based heuristic for "known-rank" matrix completion and establish a condition under which the generated sequence is quasi-Fej'er convergent to the solution set. Then, by including an acceleration mechanism similar to Nesterov's acceleration, we obtain a new heuristic. Even though the convergence of such heuristic cannot be granted in general, it turns out that it can be very useful as a warm-start phase, providing a suitable estimate for the regularization parameter and a good starting-point, to an accelerated Soft-Impute algorithm. Numerical experiments with both synthetic and real data show that the resulting two-phase rank-based algorithm can recover low-rank matrices, with relatively high precision, faster than other well-established matrix completion algorithms.

Full work available at URL: https://arxiv.org/abs/2202.09405

Recommendations

• Accelerated low rank matrix approximate algorithms for matrix completion
• The two-stage iteration algorithms based on the shortest distance for low-rank matrix completion
• Orthogonal rank-one matrix pursuit for low rank matrix completion
• A gradual rank increasing process for matrix completion
• Low-rank approximation algorithms for matrix completion with random sampling

zbMATH Keywords

matrix completionsoft-thresholdingproximal gradient algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Spectral regularization algorithms for learning large incomplete matrices
• A Singular Value Thresholding Algorithm for Matrix Completion
• Exact matrix completion via convex optimization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Fixed point and Bregman iterative methods for matrix rank minimization
• Euclidean distance geometry and applications
• Quasi-Fejérian analysis of some optimization algorithms
• Hybridization of accelerated gradient descent method
• Low-rank matrix recovery via iteratively reweighted least squares minimization
• A class of Fejér convergent algorithms, approximate resolvents and the hybrid proximal-extragradient method
• An accelerated double step size model in unconstrained optimization
• Low rank matrix completion by alternating steepest descent methods
• A novel low-rank matrix completion approach to estimate missing entries in Euclidean distance matrix

Cited In (2)

• Low-Complexity Modeling of Partially Available Second-Order Statistics: Theory and an Efficient Matrix Completion Algorithm
• MC2: a two-phase algorithm for leveraged matrix completion

This page was built for publication: A two-phase rank-based algorithm for low-rank matrix completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6164963)