Efficient Federated Low Rank Matrix Completion

作     者：Abbasi, Ahmed Ali Vaswani, Namrata 

作者机构：Iowa State University Department of Electrical and Computer Engineering United States 

出 版 物：《IEEE Transactions on Information Theory》 (IEEE Trans. Inf. Theory)

年 卷 期：2025年第71卷第7期

页      面：5493-5511页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0701[理学-数学] 

基　　金：NSF 

主　　题：Matrix algebra 

摘      要：In this work, we develop and analyze a novel Gradient Descent (GD) based solution, called Alternating GD and Minimization (AltGDmin), for efficiently solving the low rank matrix completion (LRMC) in a federated setting. Here efficient refers to communication-, computation- and sample- efficiency. LRMC involves recovering an n × q rank-r matrix X* from a subset of its entries when r min(n, q). Our theoretical bounds on the sample complexity and iteration complexity of AltGDmin imply that it is the most communication-efficient solution while also been one of the most computation- and sample- efficient ones. We also extend our guarantee to the noisy LRMC setting. In addition, we show how our lemmas can be used to provide an improved sample complexity guarantee for the Alternating Minimization (AltMin) algorithm for LRMC. AltMin is one of the fastest centralized solutions for LRMC;with AltGDmin having comparable time cost even for the centralized setting. © 1963-2012 IEEE.