版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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
摘 要: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.