Efficient Federated Low Rank Matrix Completion

2024/05/10 by Abbasi, Ahmed Ali, Vaswani, Namrata · 1 citation
#FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Signal Processing (eess.SP) #electronic engineering #information engineering

paper · doi:10.48550/arxiv.2405.06569

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 × q rank-r matrix \Xstar from a subset of its entries when r ≪ 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.

Cited by

• Locally Permuted Low Rank Column-wise Sensing

Related

• Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
• Understanding Alternating Minimization for Matrix Completion
• Low-rank Matrix Completion using Alternating Minimization
• Advancing Matrix Completion by Modeling Extra Structures beyond Low-Rankness
• Fast and Sample-Efficient Federated Low Rank Matrix Recovery from column-wise Linear and Quadratic Projections