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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 51 references that are in the map.
- First posted on arXiv 13 Sep 2024.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval](https://mlsanity.com/paper/1803.07726/) (2018)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent](https://mlsanity.com/paper/1605.07051/) (2016)
- [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022)
- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [Matrix Compression via Randomized Low Rank and Low Precision Factorization](https://mlsanity.com/paper/2310.11028/) (2023)
- [Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squareroot](https://mlsanity.com/paper/1507.05854/) (2015)
- [Communication-Efficient Distributed SVD via Local Power Iterations](https://mlsanity.com/paper/2002.08014/) (2020)
- [Convergence of Alternating Gradient Descent for Matrix Factorization](https://mlsanity.com/paper/2305.06927/) (2023)
- [Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis](https://mlsanity.com/paper/1702.08169/) (2017)
- [The Global Geometry of Centralized and Distributed Low-rank Matrix Recovery without Regularization](https://mlsanity.com/paper/2003.10981/) (2020)
- [Dictionary Learning for Massive Matrix Factorization](https://mlsanity.com/paper/1605.00937/) (2016)

## Built on by (most cited first, 2 of 2)

- [DeMuon: A Decentralized Muon for Matrix Optimization over Graphs](https://mlsanity.com/paper/2510.01377/) (2025)
- [Adaptive collaboration for online personalized distributed learning with heterogeneous clients](https://mlsanity.com/paper/2507.06844/) (2025)

## Abstract (arXiv)

We analyze a distributed algorithm to compute a low-rank matrix factorization on N clients, each holding a local dataset Si ∈ ℝni × d, mathematically, we seek to solve min_Ui ∈ ℝni× r, V∈ ℝd × r  frac12 sumi=1N |Si - Ui V^top|2F. Considering a power initialization of V, we rewrite the previous smooth non-convex problem into a smooth strongly-convex problem that we solve using a parallel Nesterov gradient descent potentially requiring a single step of communication at the initialization step. For any client i in 1, dots, N, we obtain a global V in ℝd × r common to all clients and a local variable Ui in ℝni × r. We provide a linear rate of convergence of the excess loss which depends on σmax / σr, where σr is the rth singular value of the concatenation S of the matrices (Si)i=1N. This result improves the rates of convergence given in the literature, which depend on σmax2 / σmin2. We provide an upper bound on the Frobenius-norm error of reconstruction under the power initialization strategy. We complete our analysis with experiments on both synthetic and real data.