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

DOI10.1007/S11590-022-01959-6MaRDI QIDQ6164963zbMATH OpenFDO

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)

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

zbMATH Keywords

matrix completionsoft-thresholdingproximal gradient algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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.

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

Cites work

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

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)