Efficient Federated Low Rank Matrix Completion

Ahmed Ali Abbasi, Namrata Vaswani
5/10/2024
cs.LGeess.SP

No confident code implementation found for this paper. 1 possible match can be shown below.

Abstract

In this work, we develop and analyze a Gradient Descent (GD) based solution, called Alternating GD and Minimization (AltGDmin), for efficiently solving the low rank matrix completion (LRMC) in a federated setting. LRMC involves recovering an $n \times q$ rank-$r$ matrix $\Xstar$ from a subset of its entries when $r \ll \min(n,q)$. Our theoretical guarantees (iteration and sample complexity bounds) imply that AltGDmin is the most communication-efficient solution in a federated setting, is one of the fastest, and has the second best sample complexity among all iterative solutions to LRMC. In addition, we also prove two important corollaries. (a) We provide a guarantee for AltGDmin for solving the noisy LRMC problem. (b) We show how our lemmas can be used to provide an improved sample complexity guarantee for AltMin, which is the fastest centralized solution.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 1 weaker match is hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time

85% match1 repo232023

In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting

81% match1 repo12024

Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

81% match2023

Near-Optimal Nonconvex Matrix Completion

80% match2026

Disjunctive Branch-And-Bound for Certifiably Optimal Low-Rank Matrix Completion

80% match2023

Matrix Completion from General Deterministic Sampling Patterns

78% match2023

Cite this paper

@article{abbasi2024efficient,
  title  = {Efficient Federated Low Rank Matrix Completion},
  author = {Ahmed Ali Abbasi and Namrata Vaswani},
  year   = {2024},
  eprint = {2405.06569},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2405.06569v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2405.06569.svg)](https://codeofpaper.com/paper/2405.06569)

Discussion