# Tailed Low-Rank Matrix Factorization for Similarity Matrix Completion

arXiv: https://arxiv.org/abs/2409.19550 · HTML: https://mlsanity.com/paper/2409.19550/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 93 references that are in the map.
- First posted on arXiv 29 Sep 2024.

## Builds on (most cited first, 20 of 20)

- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Text Is All You Need: Learning Language Representations for Sequential Recommendation](https://mlsanity.com/paper/2305.13731/) (2023)
- [Implicit Regularization in Deep Learning May Not Be Explainable by Norms](https://mlsanity.com/paper/2005.06398/) (2020)
- [Fast Matrix Factorization for Online Recommendation with Implicit Feedback](https://mlsanity.com/paper/1708.05024/) (2017)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Generalized Low Rank Models](https://mlsanity.com/paper/1410.0342/) (2014)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013)
- [A globally convergent algorithm for nonconvex optimization based on block coordinate update](https://mlsanity.com/paper/1410.1386/) (2014)
- [Nonconvex Nonsmooth Low-Rank Minimization via Iteratively Reweighted Nuclear Norm](https://mlsanity.com/paper/1510.06895/) (2015)
- [A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation](https://mlsanity.com/paper/1610.05275/) (2016)
- [Low Rank Regularization: A Review](https://mlsanity.com/paper/1808.04521/) (2018)
- [Factor Group-Sparse Regularization for Efficient Low-Rank Matrix Recovery](https://mlsanity.com/paper/1911.05774/) (2019)
- [Large-Scale Low-Rank Matrix Learning with Nonconvex Regularizers](https://mlsanity.com/paper/1708.00146/) (2017)
- [Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form](https://mlsanity.com/paper/1803.00186/) (2018)
- [Generalized Singular Value Thresholding](https://mlsanity.com/paper/1412.2231/) (2014)
- [Matrix Completion with Noisy Entries and Outliers](https://mlsanity.com/paper/1503.00214/) (2015)
- [Unsupervised Matching of Data and Text](https://mlsanity.com/paper/2112.08776/) (2021)
- [Online high rank matrix completion](https://mlsanity.com/paper/2002.08934/) (2020)
- [Dynamic matrix recovery from incomplete observations under an exact low-rank constraint](https://mlsanity.com/paper/1610.09420/) (2016)

## Abstract (arXiv)

Similarity matrix serves as a fundamental tool at the core of numerous downstream machine-learning tasks. However, missing data is inevitable and often results in an inaccurate similarity matrix. To address this issue, Similarity Matrix Completion (SMC) methods have been proposed, but they suffer from high computation complexity due to the Singular Value Decomposition (SVD) operation. To reduce the computation complexity, Matrix Factorization (MF) techniques are more explicit and frequently applied to provide a low-rank solution, but the exact low-rank optimal solution can not be guaranteed since it suffers from a non-convex structure. In this paper, we introduce a novel SMC framework that offers a more reliable and efficient solution. Specifically, beyond simply utilizing the unique Positive Semi-definiteness (PSD) property to guide the completion process, our approach further complements a carefully designed rank-minimization regularizer, aiming to achieve an optimal and low-rank solution. Based on the key insights that the underlying PSD property and Low-Rank property improve the SMC performance, we present two novel, scalable, and effective algorithms, SMCNN and SMCNmF, which investigate the PSD property to guide the estimation process and incorporate nonconvex low-rank regularizer to ensure the low-rank solution. Theoretical analysis ensures better estimation performance and convergence speed. Empirical results on real-world datasets demonstrate the superiority and efficiency of our proposed methods compared to various baseline methods.