# Efficient Federated Low Rank Matrix Completion

Ahmed Ali Abbasi and Namrata Vaswani The authors are at the Department of
Electrical and Computer Engineering, Iowa State University. Email:
<EMAIL_ADDRESS>A part of this work (only simulation experiments)
appeared in Allerton 2023 [1].

###### 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 ${\bm{X}}^{\star}$ 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.

##  I Introduction

In this work, we develop and analyze a fast and communication-efficient
solution for efficiently solving the low rank matrix completion (LRMC) problem
in a federated setting. LRMC involves recovering/learning a low rank (LR)
matrix from a small number of its observed entries. Our proposed algorithm,
and the sample and iteration complexity guarantees that we prove for it, are
also useful in centralized settings. Federation means that (i) different
subsets of the data are acquired at different distributed nodes; and (ii) all
nodes can only communicate with the central node or “center”. Communication-
efficiency is a key concern with all distributed algorithms, including
federated ones. Privacy of the data is another concern in a federated setting.
In this work, “privacy” means the following: the nodes’ raw data (here
observed matrix entries) cannot be shared with the center; and the algorithm
should be such that the center cannot recover any of the columns of the LR
matrix.

###  I-A Problem Setup and Notation

LRMC involves recovering a rank-$r$ matrix
${\bm{X}}^{\star}\in\mathbb{R}^{n\times q}$, where $r\ll\min(n,q)$, from a
subset of its entries. Entry $j$ of column $k$, denoted
${\bm{X}}^{\star}_{jk}$, is observed, independently of all other observations,
with probability $p$. Let
$\xi_{jk}\stackrel{{\scriptstyle\mathrm{iid}}}{{\thicksim}}\mathrm{Bernoulli}(p)$
for $j\in[n],k\in[q]$. Then, the set of observed entries, denoted by $\Omega$,
is

$\Omega:=\\{(j,k):\xi_{jk}=1\\}$

By setting the unobserved entries to zero, the observed data matrix
$\bm{Y}\in\mathbb{R}^{n\times q}$ can be defined as

$\bm{Y}_{jk}:=\begin{cases}{\bm{X}}^{\star}_{jk}&\text{ if }(j,k)\in\Omega,\\\
0&\text{ otherwise}.\end{cases}\ \ \text{or, equivalently,}\ \
\bm{Y}:={\bm{X}}^{\star}_{\Omega}$ (1)

Here and below, $\bm{M}_{\Omega}$ refers to the matrix $\bm{M}$ with all
entries whose indices are not in the set $\Omega$ are zeroed out; while the
rest of the entries remain unchanged.

####  I-A1 Notation

For any matrix $\bm{M}$, $\bm{m}_{k}$ denotes its $k$-th column while
$\bm{m}^{j}$ denotes its $j$-th row transposed (so it is a column vector).
$(\cdot)^{\intercal}$ denotes the matrix/vector transpose. We use $\bm{I}$ to
denote the identity matrix and $\bm{e}_{k}$ to denote its $k$-th column (this
is a 1-0 vector with 1 at the $k$-th location and zero everywhere else).
$\|\cdot\|$ denotes either the vector $\ell_{2}$ or the induced $\ell_{2}$
norm of a matrix
($\|\bm{M}\|:=\max_{\bm{z}:\|\bm{z}\|=1}\|\bm{M}\bm{z}\|=\sigma_{\max}(\bm{M})$),
while $\|\cdot\|_{F}$ denotes the Frobenius norm of a matrix. We use
$vec(\bm{M})$ to denote a vectorized version of matrix $\bm{M}$; thus
$\|\bm{M}\|_{F}=\|vec(\bm{M})\|$. We use the standard notation
$[q]:=\\{1,2,\dots,q\\}$.

For a tall matrix $\bm{M}$,
$\bm{M}^{\dagger}\triangleq(\bm{M}^{\intercal}\bm{M})^{-1}\bm{M}^{\intercal}$
denotes the Moore-Penrose pseudo-inverse. Also, $\mathrm{QR}(\bm{M})$ maps the
matrix $\bm{M}\in\mathbb{R}^{n\times r}$ to ${\bm{Q}}\in\mathbb{R}^{n\times
r}$ such that $\bm{M}={\bm{Q}}{\bm{R}}$ is the QR decomposition of $\bm{M}$
(columns of ${\bm{Q}}$ are orthornormal). For matrices
${\bm{U}}_{1},{\bm{U}}_{2}$ with orthonormal columns, the two commonly used
measures of subspace distance (SD) between their column spans are
$\mathrm{SD}_{2}({\bm{U}}_{1},{\bm{U}}_{2}):=\|(\bm{I}-{\bm{U}}_{1}{\bm{U}}_{1}^{\intercal}){\bm{U}}_{2}\|$
and
$\mathrm{SD}_{F}({\bm{U}}_{1},{\bm{U}}_{2}):=\|(\bm{I}-{\bm{U}}_{1}{\bm{U}}_{1}^{\intercal}){\bm{U}}_{2}\|_{F}.$
We use the Frobenius norm SD in most of our analysis in this paper because it
allows us to get a better sample complexity guarantee.

We use $\bm{M}=\mathrm{diag}(m_{k},k\in[q])$ to denote a diagonal $q\times q$
matrix with scalar entries $m_{k}$ and
$\bm{M}=\mathrm{blockdiag}(\bm{M}_{k},k\in[q])$ to denote a block-diagonal
matrix with block diagonal entries $\bm{M}_{k}$. We use
$\Omega_{k}:=\\{j\in[n]\mid\xi_{jk}=1\\}$ to denote the set of indices of the
observed entries in column $k$ and we define a diagonal 1-0 matrix
$\bm{S}_{k}\in\mathbb{R}^{n\times n}$ as

$\bm{S}_{k}:=\mathrm{diag}(\xi_{jk},\ j\in[n])$

Thus, $\bm{y}_{k}=\bm{S}_{k}\bm{x}^{\star}_{k}$ for all $k\in[q]$. We reuse
the letters $c,C$ to denote different numerical constants in each use with the
convention that $c<1$ and $C\geq 1$.

Let
${\bm{X}}^{\star}\overset{\mathrm{SVD}}{=}{\bm{U}}^{\star}{}(\bm{\Sigma^{*}}){\bm{V}^{*}}:={\bm{U}}^{\star}{}{\bm{B}^{\star}}$,
where ${\bm{U}}^{\star}{}\in\mathbb{R}^{n\times r}$ and has orthonormal
columns and $\bm{V}^{\star}{}\in\mathbb{R}^{r\times q}$ with orthonormal rows.
We use $\kappa={\sigma_{\max}^{*}}/{\sigma_{\min}^{*}}$ to denote the
condition number of the diagonal $r\times r$ matrix $\bf\Sigma^{*}$. Here
${\sigma_{\max}^{*}},{\sigma_{\min}^{*}}$ to denote its largest, smallest
singular values. Also, we let ${\bm{B}^{\star}}:=\bm{\Sigma^{*}}{\bm{V}^{*}}$
so that ${\bm{X}}^{\star}={\bm{U}}^{\star}{}{\bm{B}^{\star}}$.

####  I-A2 Assumption

As in all past works on LRMC, e.g. [2, 3], we need the following assumption on
the singular vectors of ${\bm{X}}^{\star}$; this is a way to guarantee that
the rows and columns of ${\bm{X}}^{\star}$ are dense (non-sparse). This and
the LR assumption help ensure that one can correctly interpolate (fill in) the
missing entries even with observing only a few entries of each row or column.

######  Assumption 1.1 ($\mu$-incoherence of singular vectors of
${\bm{X}}^{\star}$).

Assume row norm bounds on ${\bm{U}}^{\star}{}$:
$\max_{j\in[n]}\|\bm{u}^{*}{}{}^{j}\|\leq\mu\sqrt{r/n}$, and column norm
bounds on $\bm{V}^{*}$: $\max_{k\in[q]}\|\bm{v}^{*}_{k}\|\leq\mu\sqrt{r/q}$.
Since ${\bm{B}^{\star}}=\bm{\Sigma^{*}}{\bm{V}^{*}}$, this implies that
$\|\bm{b}^{\star}_{k}\|\leq\mu\sqrt{r/q}{\sigma_{\max}^{*}}$.

We should point out that our proof for AltGDmin correctness only uses the
incoherence of ${\bm{U}}^{\star}{}$ and of ${\bm{B}^{\star}}$. This is a
slightly weaker requirement than requiring incoherence of
${\bm{U}}^{\star}{},\bm{V}^{\star}{}$.

####  I-A3 Federation

We assume that there are a total of $\gamma$ nodes, with $\gamma\leq q$. Each
node has access to a different subset of the columns of the observed data
matrix $\bm{Y}$. We use $\bm{S}_{\ell}$ to denote the subset of columns of
$\bm{Y}$ available at node $\ell$. The sets $\bm{S}_{\ell}$ form a partition
of $[q]$, i.e., they are mutually disjoint and
$\cup_{\ell=1}^{\gamma}\bm{S}_{\ell}=[q]$. To keep notation simple, we assume
$q$ is a multiple of $\gamma$ and $|\bm{S}_{\ell}|=q/\gamma$. All nodes can
only communicate with a central node or “center”. In a federated setting, the
two desirable properties are communication-efficiency and “privacy”. In this
work, “privacy” means the following. The nodes’ raw data cannot be shared with
the center and the center should not be able reconstruct the matrix
${\bm{X}}^{\star}$.

Our discussion of complexities assumes $\gamma\ll q$ and treats $\gamma$ as a
numerical constant. Thus order $|\Omega|/\gamma$ is equal to order $|\Omega|$
with $|\Omega|\geq(n+q)r$ (the number of samples needs to be larger than the
number of unknowns in rank $r$ matrix).

###  I-B Related Work

Algorithm | Computation Comp. | Communic. Comp. | Sample Comp.
---|---|---|---
AltGDMin (Priv) (Proposed) | $\kappa^{2}\frac{|\Omega|}{\gamma}r^{2}\log(\frac{1}{\epsilon})$ | $\kappa^{2}nr\log(\frac{1}{\epsilon})$ | $\kappa^{6}\mu^{2}nr^{2}\log n\log(\frac{1}{\epsilon})$
FactGD (Priv) [11, 10] | $\kappa\mu\frac{|\Omega|}{\gamma}r^{2}\log(\frac{1}{\epsilon})$ | $\kappa\mu nr^{2}\log(\frac{1}{\epsilon})$ | $\kappa^{4}\mu^{2}nr^{2}\log n$
AltMin (Priv) [3] | $\frac{|\Omega|}{\gamma}r\log^{2}(\frac{1}{\epsilon})$ | $nr\log^{2}(\frac{1}{\epsilon})$ | $\kappa^{4}\mu^{2}nr^{4.5}\log n\log(\frac{1}{\epsilon})$
AltMin (Not-Priv) [3] | $\frac{|\Omega|}{\gamma}r^{2}\log(\frac{1}{\epsilon})$ | $\frac{|\Omega|}{\gamma}\log(\frac{1}{\epsilon})$ | $\kappa^{4}\mu^{2}nr^{4.5}\log n\log(\frac{1}{\epsilon})$
Smooth-AltMin (Not-Priv) [12] | $\frac{|\Omega|}{\gamma}r^{2}\log n\log(\frac{1}{\epsilon})$ | $\frac{|\Omega|}{\gamma}\log n\log(\frac{1}{\epsilon})$ | $\kappa^{2}\mu^{2}nr^{3}\log n\log(\frac{1}{\epsilon})$
ProjGD (Not-Priv) [13, 7] | $\mu^{4}\frac{|\Omega|}{\gamma}r\log^{2}(\frac{1}{\epsilon})$ | $\mu^{4}\frac{|\Omega|}{\gamma}\log^{2}(\frac{n}{\epsilon})$ | $\mu^{4}nr^{2}\log^{2}n\log^{2}(\frac{1}{\epsilon})$
TABLE I: The table assumes $n\approx q$, $\gamma$ is a numerical constant,
$\max(\log(1/\epsilon),r)=\log(1/\epsilon)$, and $|\Omega|\geq nr$
(necessary). Here $\text{Communic Comp}=T\cdot\max(\text{Communic.(node),
Communic.(center)})$. Similarly for the computation cost. These complexities
for federated versions of the other algorithms are derived in Appendix C.

Starting with the seminal work of [4, 2] which introduced a nuclear norm based
convex relaxation, the LRMC problem has been extensively studied in the last
decade and a half [4, 2, 5, 3, 6, 7, 8, 9, 10, 11]. Two classes of algorithms
feature prominently in this literature - solutions to convex relaxations and
direct iterative algorithms. The former [4, 2] are slow: the required number
of iterations for $\epsilon$ accuracy (iteration complexity) grows as
$1/\sqrt{\epsilon}$ [3]. The first provably accurate iterative solution was
the Alternating Minimization (AltMin) algorithm with a spectral initialization
[3, 5]. AltMin was shown to converge geometrically (iteration complexity order
$\log(1/\epsilon)$) with a sample complexity of
$\kappa^{4}\mu^{2}nr^{4.5}\log(1/\epsilon)$ in [3]. Subsequent work [12]
considered a modified version of AltMin and improved its sample complexity to
order $\kappa^{2}\mu^{2}nr^{2.5}\log(1/\epsilon)$. AltMin factorizes the
unknown LR matrix ${\bm{X}}$ as ${\bm{X}}={\bm{U}}\bm{B}$. After initializing
${\bm{U}}$, it alternately updates $\bm{B}$ and ${\bm{U}}$ using minimization
for one, keeping the other fixed. Later works proposed two gradient descent
(GD) based algorithms - Projected GD (ProjGD) [13, 7] and Factorized GD
(FactGD) [11, 10] \- that reduced the sample complexity dependence on $r$ to
$r^{2}$. ProjGD involves GD, followed by projection onto the space of rank $r$
matrices (this is done by singular value decomposition (SVD)) after each GD
iteration. FactGD factorizes the unknown LR matrix ${\bm{X}}$ as
${\bm{X}}={\bm{U}}\bm{B}$, where ${\bm{U}},\bm{B}$ have $r$ columns and rows
respectively, and updates both by GD as follows. After initialization, at each
iteration, it updates ${\bm{U}}$ and $\bm{B}$ by one GD step for the cost
function
$f({\bm{U}},\bm{B})+c_{1}\|{\bm{U}}^{\intercal}{\bm{U}}-\bm{B}\bm{B}^{\intercal}\|_{F}^{2}$,
followed by projecting each of them onto the set of matrices with incoherent
rows and columns respectively. Denote the former (incoherent rows) set by
${\mathcal{U}}$. Initialization involves SVD on $\bm{Y}$ followed by a similar
projection onto ${\mathcal{U}}$. The second term of the FactGD cost function
is a norm balancing term that ensures the norm of ${\bm{U}}$ does not keep
increasing with iterations while that of $\bm{B}$ decreases (or vice versa).
The best ProjGD guarantee needs a sample complexity of
$\mu^{4}nr^{2}\log^{2}n\log^{2}1/\epsilon$ while FactGD reduces this even
further to $\kappa^{4}\mu^{2}nr^{2}\log^{2}n$. ProjGD converges geometrically
with a constant GD step size, while FactGD needs the GD step size to be of
order $1/r$. Consequently, its iteration complexity is worse than that of
ProjGD or AltMin by a factor of $r$. However, in terms of per-iteration time
cost, ProjGD is significantly slower. Consequently, overall in terms of total
cost, it is slower. Numerically, it is much slower than all other methods,
because each ProjGD iteration involves a rank $r$ SVD step (constants per
iteration are much larger); see Fig 1b,1d of [1]. Some of this discussion
treats $\kappa,\mu$ as numerical constants.

To our best knowledge, there is no existing work on provably accurate
federated LRMC. Federation requires a communication-efficient and private
solution, with “private” as defined above.

In tangentially related work [14, 15], distributed-computing solutions to LRMC
are studied. These do not consider the federated setting, instead these assume
that all data is observed centrally and then is distributed to different nodes
to parallelize the computation; and these develop an approximate solution to
the convex relaxation which is known to be very slow. Fully decentralized LRMC
has been studied in [16, 17, 18]. These methods are much slower than GD. Other
tangentially related works include [19, 20, 21], all these consider
differential privacy or attack resilience.

The Alternating GD and Minimization (AltGDmin) algorithm was introduced in our
past work [22, 23] as a fast solution to the LR column-wise compressive
sensing (LRCS) problem. LRCS involves recovering ${\bm{X}}^{\star}$ from
$\bm{y}_{k}:=\bm{A}_{k}\bm{x}^{\star}_{k}$ when $\bm{A}_{k}$’s are $m\times n$
i.i.d. random Gaussian matrices (each entry of each $\bm{A}_{k}$ is i.i.d.
standard Gaussian), and the right singular vectors of ${\bm{X}}^{\star}$
satisfy the incoherence assumption. The overall idea of AltGDmin is as follows
[22]. Suppose the goal is to solve $\min_{{\bm{{Z}}}}f({\bm{{Z}}})$. We split
the unknown variable ${\bm{{Z}}}$ into two parts,
${\bm{{Z}}}=\\{{\bm{{Z}}}_{a},{\bm{{Z}}}_{b}\\}$. After initializing
${\bm{{Z}}}_{a}$, we alternatively update ${\bm{{Z}}}_{b},{\bm{{Z}}}_{a}$
using minimization for ${\bm{{Z}}}_{b}$ (keeping ${\bm{{Z}}}_{a}$ fixed at its
previous value) and GD for ${\bm{{Z}}}_{a}$ (keeping ${\bm{{Z}}}_{b}$ fixed at
its previous value). We choose the split-up so that ${\bm{{Z}}}_{b}$ is the
set of variables for which the minimization can be “decoupled”, i.e., subsets
of ${\bm{{Z}}}_{b}$ are functions of only a subsets of the data matrix
$\bm{Y}$. AltGDmin is an efficient solution only for problems where this is
possible to do. As will be clear later, this is what helps ensure both the
communication, and computation, efficiency.

A small part of this work – only the algorithm and simulation experiments –
appeared in Allerton 2023 [1]. Some of the time and communication complexity
discussion provided there was incorrect.

###  I-C Contributions and Novelty

We develop and analyze the AltGDmin algorithm for solving the LRMC problem.
The design of AltGDmin is motivated by a federated setting. To our best
knowledge, our work provides the first theoretical guarantees for solving LRMC
in a federated setting; see Theorem 2.1. The sample and iteration complexity
bounds that we prove are applicable in centralized settings as well. In
addition, we also prove two important corollaries. (a) We provide a guarantee
for AltGDmin for solving the noisy LRMC problem. (b) We also show how our
lemmas can be used to provide an improved sample complexity guarantee for
AltMin which is the fastest centralized solution for LRMC.

Using our results we can argue that, in a federated setting, AltGDmin is the
most communication-efficient solution. It is also one of the two fastest
private solutions and has the second smallest sample complexity. Our new
corollary for AltMin (and smooth AltMin) proves that it also has the same
sample complexity as that of AltGDmin. This discussion treats $\kappa,\mu$ and
$\gamma$ (number of nodes) as numerical constants. We discuss these points in
more detail in Sec. III and in Table I.

####  I-C1 Proof Novelty

While AltGDmin has been studied for solving the LRCS problem, there are some
important differences between the two problems that necessitate new analysis
approaches. LRMC samples are row and column-wise local, while LRCS samples are
global for each column. Because of this, LRMC requires assuming left and right
singular vectors’ incoherence and proving the same for each new iterate of
${\bm{U}}$ and $\bm{B}$. LRCS needed this only for $\bm{B}$. We need a new
approach to show the incoherence of ${\bm{U}}$ at each iteration since the
update of ${\bm{U}}$ in AltGDmin is different from that in all existing
solutions to LRMC. FactGD for LRMC [11] projects ${\bm{U}}$ (and $\bm{B}$)
onto the space of row (column) incoherent matrices after each GD step; this
automatically ensures incoherence after each update. AltMin [3] updates
${\bm{U}}$ by solving an LS problem (and not by GD), so the incoherence proof
there is different too. ProjGD [7] implemented projected GD for ${\bm{X}}$
itself (does not factorize it). There are other important proof differences
too. We explain these in Sec. III-B.

###  I-D Organization

We develop the AltGDmin algorithm and state and explain our main theoretical
guarantee, Theorem 2.1, for it next in Sec. II. We provide a detailed
comparison of this guarantee with those from existing works in Sec. III. This
section also summarizes the novel proof ideas and gives a proof outline.
Theorem 2.1 is proved in Sec.IV. The lemmas used in this proof are proved in
Sec. V. The corollary for noisy LRMC is provided in Sec. VI. We use our lemmas
to prove an improved guarantee for AltMin and Smooth AltMin in Sec. VII.
Numerical experiments that demonstrate our theoretical claims are described in
Sec. VIII. We conclude in Sec. IX.

##  II Alternating GD and Minimization (AltGDMin) Algorithm and Guarantees

###  II-A AltGDmin Algorithm

The goal is to minimize the following squared loss cost function

$\min_{\begin{subarray}{c}\check{\bm{B}},\,\check{\bm{U}}\colon\check{\bm{U}}^{\intercal}\check{\bm{U}}=\bm{I}\end{subarray}}f(\check{\bm{U}},\check{\bm{B}}),\
f(\check{\bm{U}},\check{\bm{B}}):=\|(\bm{Y}-\check{\bm{U}}\check{\bm{B}})_{\Omega}\|_{F}^{2}$
(2)

We impose the orthornormal columns constraint on $\check{\bm{U}}$ as one way
to ensure that the norm of ${\bm{U}}$ does not keep increasing or decreasing
continuously with algorithm iterations, while that of $\bm{B}$ decreases or
increases.

AltGDmin proceeds as follows. We initialize ${\bm{U}}$ as explained below;
this approach is adapted from that in FactGD [11]. After the initialization,
different from AltMin [3], which used alternating exact minimization for both
${\bm{U}}$ and $\bm{B}$, and different from FactGD [11], which used GD for
both ${\bm{U}}$ and $\bm{B}$, AltGDmin alternates between exact minimization
over $\bm{B}$ and a single GD step for ${\bm{U}}$. The GD step is followed by
an orthonormalization (QR) step. The above simple changes help ensure that the
AltGDmin iteration complexity is better than that of FactGD and comparable to
that of AltMin. The use of exact minimization for one of the variables, along
with not using the projection onto incoherent matrices step (replacing it by
QR), helps ensure that AltGDmin provably converges with a nearly constant step
size. Because of this, the AltGDmin iteration complexity is better than that
of FactGD by a factor of $r$.

####  II-A1 Initialization

As in most previous work [3, 11], the first step of our initialization is to
compute the top $r$ singular vectors of $\bm{Y}$; denote the matrix formed by
these singular vectors by ${\bm{U}}^{(00)}$. This is followed by a step to
make ${\bm{U}}^{(00)}$ incoherent. We borrow this step from [11]. It involves
projecting ${\bm{U}}^{(00)}$ onto the space of row incoherent matrices,

${{\mathcal{U}}}:=\\{\check{\bm{U}}:\|{\check{\bm{u}}}^{j}\|\leq\mu\sqrt{r/n}\\}$

i.e., computing
$\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})=\min_{\check{\bm{U}}\in{\mathcal{U}}}\|\check{\bm{U}}-{\bm{U}}^{(00)}\|_{F}$.
It is easy to see that this projection can be obtained in closed form as
follows:

$[\Pi_{{\mathcal{U}}}(\bm{M})]^{j}=\bm{m}^{j}\cdot\min\left(1,\frac{\mu\sqrt{r/n}}{\|\bm{m}^{j}\|}\right),\
\text{ for all }j\in[n]$

In words, if a row of $\bm{M}$ has $\ell_{2}$ norm that is more than the
threshold $\mu\sqrt{r/n}$, then one renormalizes the row so that its norm
equals the threshold. If the norm is less than this threshold, then we do not
change it. Clearly this is an order $nr$ time operation. The last step is
computing a QR decomposition of $\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})$. This
needs time of order $nr^{2}$.

####  II-A2 AltGDmin iterations

We update $\bm{B}$ and ${\bm{U}}$ as follows for a total of $T$ iterations.
The minimization over $\bm{B}$ is a decoupled least squares (LS) problem since
$f(\check{\bm{U}},\check{\bm{B}})$ decouples as
$f(\check{\bm{U}},\check{\bm{B}})=\sum_{k\in[q]}\|\bm{y}-\bm{S}_{k}\check{\bm{U}}\check{\bm{b}}_{k}\|^{2}$.
We update $\bm{b}_{k}$ as

$\displaystyle\bm{b}_{k}$
$\displaystyle=\operatorname*{\mathrm{argmin}}_{\check{\bm{b}}}\|\bm{y}-\bm{S}_{k}{\bm{U}}\check{\bm{b}}\|^{2}=(\bm{S}_{k}{\bm{U}})^{\dagger}\bm{y}_{k},\
\text{ for all }k\in[q]$

Let ${\bm{U}}_{k}:=\bm{S}_{k}{\bm{U}}$, then
$\bm{b}_{k}:={\bm{U}}_{k}^{\dagger}\bm{y}_{k}$. Recall that
$\bm{M}^{\dagger}:=(\bm{M}^{\intercal}\bm{M})^{-1}\bm{M}^{\intercal}$. We
emphasise here that we write things as above for notational ease in both
explaining the idea and the proof. The time complexity for computing
$\bm{b}_{k}$ depends only on the sub-matrix of ${\bm{U}}_{k}$ with nonzero
rows. This is of size $|\Omega_{k}|\times r$. The time cost of computing
$\bm{b}_{k}$ is thus order $|\Omega_{k}|r^{2}$ for a given $k$. Hence, the
total cost for all nodes is $\sum_{k}|\Omega_{k}|r^{2}=|\Omega|r^{2}$.

We update ${\bm{U}}$ by one GD step followed by orthnormalization using QR,
i.e.,

$\displaystyle\tilde{\bm{U}}^{+}={\bm{U}}-\eta\nabla_{\bm{U}}f({\bm{U}},\bm{B})),\text{
and }{\bm{U}}^{+}=\mathrm{QR}(\tilde{\bm{U}}^{+})$

The gradient is

$\nabla_{\bm{U}}f({\bm{U}},\bm{B})=2(({\bm{U}}\bm{B})_{\Omega}-\bm{Y})\bm{B}^{\intercal}=2\sum_{k=1}^{q}(\bm{S}_{k}{\bm{U}}\bm{b}_{k}-\bm{y}_{k})\bm{b}_{k}^{\intercal}$

For the gradient computation, the time cost is
$\sum_{k}|\Omega_{k}|r=|\Omega|r$. The QR step needs time of order $nr^{2}$.

We summarize the complete algorithm in Algorithm 1. Sample splitting (line 1)
is assumed, as is common in most structured data recovery literature, e.g.,
[3, 12, 13, 7]. In fact, as we discuss in Sec. III, sample-splitting is
assumed for obtaining provable guarantees for all iterative solutions for LRMC
(and those for LRCS) in which one or both of the alternating steps is a
minimization step.

####  II-A3 Federated AltGDmin

In a federated setting, at each algorithm iteration, $t$, each node
$\ell=1,2,\dots,\gamma$ performs two operations i) updating $\bm{b}_{k}$ by
the LS solution, for all $k\in\bm{S}_{\ell}$; and ii) computation of the
partial gradient
$\sum_{k\in\bm{S}_{\ell}}[\nabla_{{\bm{U}}}f({\bm{U}},\bm{B})]_{k}=\sum_{k\in\bm{S}_{\ell}}({\bm{U}}_{k}\bm{b}_{k}-\bm{y})_{\Omega_{k}}\bm{b}_{k}^{\intercal}$.
Only the $n\times r$ partial gradient needs to be sent to the center. The
center sums the received partial gradients, implements the GD step, and
computes the QR decomposition, and broadcasts the updated ${\bm{U}}^{+}$ to
all the nodes. This is used by the nodes in the next iteration. The
communication cost from nodes to center is equal to the number of nonzero
entries in $\nabla_{{\bm{U}}}f({\bm{U}},\bm{B})$; this is
$r\cdot\max(n,\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|)=r\cdot\min(n,(|\Omega|/\gamma))=nr$
since we assume $\gamma$ is a numerical constant and $|\Omega|\geq(n+q)r$ is a
necessary lower bound for any approach to work. The center to nodes
communication cost is also $nr$. The computation cost is as explained above
with $|\Omega|$ replaced by $|\Omega|/\gamma$.

The initialization can be federated using the power method applied to
$\bm{Y}\bm{Y}^{\intercal}$. This costs order
$\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|r$ per power method iteration. The
upstream (node to center) per-node communication cost is
$\min(n,\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|)r=nr$ and the downstream cost is
also $nr$. The power method converges linearly and thus, for $\epsilon_{svd}$
accuracy, $\log(1/\epsilon_{svd})$ iterations are required. We prove that we
need $\epsilon_{svd}=c/\kappa^{2}$.

Details of this federation as well as detailed time and communication cost
discussion are provided in Appendix C and in [1].

Algorithm 1 AltGDMin

1:partial observations $\bm{Y}$, rank $r$, step size $\eta$, and number of
iterations $T$

2:Partition $\bm{Y}$ into $2T+1$ subsets
$\bm{Y}_{\Omega^{(0)}},\cdots,\bm{Y}_{\Omega^{(2T)}}$

3:${\bm{U}}^{(00)}\leftarrow$ top $r$ left-singular vectors of
$\bm{Y}_{\Omega^{(0)}}$

4:$\bm{M}^{(0)}\leftarrow\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})$

5:${\bm{U}}^{(0)}\leftarrow\mathrm{QR}(\bm{M}^{(0)}$

6:for $t\in 1\cdots T$ do

7:
$\bm{b}_{k}^{(t)}\leftarrow({\bm{U}}_{k}^{(t-1)})^{\dagger}\bm{y}_{\Omega_{k}^{(t)}}\,\text{
for all }\,k\in[q]$

8:
$\tilde{\bm{U}}^{(t)}\leftarrow{\bm{U}}^{(t-1)}-\eta({\bm{U}}^{(t-1)}\bm{B}^{(t)}-\bm{Y})_{\Omega^{(T+t)}}\bm{B}^{(t)}{}^{\intercal}$

9: ${\bm{U}}^{(t)}\leftarrow\mathrm{QR}(\tilde{\bm{U}}^{(t)})$ , i.e.
$\tilde{\bm{U}}^{(t)}\overset{\mathrm{QR}}{=}{\bm{U}}^{(t)}{\bm{R}}{(t)}$

10:Return ${\bm{U}},\bm{B}$

###  II-B AltGDmin Guarantee

We can prove the following for AltGDmin. Our theorem statements and proofs
assume $n\leq q$ for simplicity. Recall from above that the per-iteration per-
node computation and communication complexities of AltGDmin are
$\max(nr^{2},(|\Omega|/\gamma)r^{2})$ and
$\max(nr,\min(n,(|\Omega|/\gamma))r)=nr$. Here per-node takes the maximum of
the node or center complexities. We use this and the iteration complexity
(expression for $T$) derived in the result below to provide an expression for
its total per-node computation and communication complexities.

Let $p_{tot}:=2Tp$. Our proof of Theorem 2.1 given next obtains a lower bound
on the required $p$ in each algorithm iteration.

######  Theorem 2.1.

Pick an $\epsilon<1$. Assume that Assumption 1.1 holds and that, entries of
${\bm{X}}^{\star}$ are observed independently with probability $p_{tot}$
satisfying $nqp_{tot}>C\kappa^{6}\mu^{2}qr^{2}\log q\log({1}/{\epsilon})$. Set
$\eta=0.5/(p{\sigma_{\max}^{*2}})$ and $T=C\kappa^{2}\log(1/\epsilon)$. Then,
with probability (w.p.) at least $1-4T/n^{3}$,

$\mathrm{SD}_{F}({\bm{U}}^{(T)},{\bm{U}}^{\star}{})\leq\epsilon\text{ and
}\|{\bm{X}}^{(T)}-{\bm{X}}^{\star}\|_{F}\leq\epsilon\|{\bm{X}}^{\star}\|.$ (3)

(recall that ${\bm{X}}^{(T)}={\bm{U}}^{(T)}\bm{B}^{(T)}$).

The total per-node computation complexity of federated AltGDmin is
$C\kappa^{2}\log(1/\epsilon)\cdot\max(n,|\Omega|/\gamma)r^{2}$ and its total
per-node communication complexity is $C\kappa^{2}\log(1/\epsilon)\cdot nr$.

The proof is given in Sec. IV and V. Before this, we discuss this result and
the novel ideas used in our proof in Sec. III.

Observe that $nq\cdot p_{tot}=\mathbb{E}[|\Omega|]$, i.e., it is the expected
value of the sample complexity. We often just use the phrase “sample
complexity” when referring to it in our writing. Treating $\kappa,\mu$ as
numerical constants, the above result says that as long as we observe order
$nr^{2}\log q\log(1/\epsilon)$ matrix entries, and we set the GD step size,
$\eta$, and the total number of iterations, $T$, as stated, then with high
probability (whp), we can fill in the rest of the entries accurately: the
normalized Frobenius norm of the error in this estimation is at most
$\epsilon$. Also, we can estimate the column span of ${\bm{X}}^{\star}$ with
$\epsilon$ accuracy. The number of iterations needed is order
$\log(1/\epsilon)$. We can achieve any $\epsilon$ accuracy as long as we
increase the sample and iteration complexity accordingly.

######  Remark 2.2.

We state Theorem 2.1 for one value of the step size $\eta$ because this makes
some of our proof arguments notationally less messy. However, our proof will
go through for any step size $\eta\leq 0.5/(p{\sigma_{\max}^{*}}^{2})$. We can
actually show the following: let $\eta=c_{\eta}/(p{\sigma_{\max}^{*}}^{2})$
for a $c_{\eta}\leq 0.5$. Then, if at each iteration, $nq\cdot
p>C\kappa^{6}\mu^{2}qr^{2}\log q$, then with probability (w.p.) at least
$1-4/n^{3}$,

$\mathrm{SD}_{F}({\bm{U}}^{+},{\bm{U}}^{\star}{})\leq(1-\frac{cc_{\eta}}{\kappa^{2}})\mathrm{SD}_{F}({\bm{U}},{\bm{U}}^{\star}{})$

##  III Discussion and Proof Main Ideas/Novelty

###  III-A Discussion

The average (expected value of) the required sample complexity is $nqp$. For
this discussion, we assume $n\approx q$, $\kappa\approx\mu$,
$\max(\log(1/\epsilon),r)=\log(1/\epsilon)$. Our guarantee given in Theorem
2.1 shows that the AltGDmin sample complexity is $\kappa^{6}\mu^{2}nr^{2}\log
n\log(1/\epsilon)$. This is worse than that of FactGD by a factor of
$\kappa^{2}\log(1/\epsilon)$. However, the iteration complexity of AltGDmin is
$T=\kappa^{2}\log(1/\epsilon)$ while that of FactGD is $T=\kappa\mu
r\log(1/\epsilon)$. Assuming $\kappa\approx\mu$, this means the AltGDmin
iteration complexity is better by a factor of $r$. This is also demonstrated
numerically in Sec. VIII. Per iteration, both have the same communication
cost, while the FactGD computation cost is lower than that of AltGDmin by a
factor of $r$. Consequently, the total AltGDmin communication cost is lower
than that of FactGD by a factor of $r$, while the total computation costs are
similar. We provide a summary in Table I.

The ProjGD sample complexity is worse than that of AltGDmin by a factor of
$\log n\log(1/\epsilon)$. Moreover, the ProjGD communication cost per
iteration is much higher than that of AltGDmin and FactGD. The same is true
for its computation cost making it one of the slowest and most communication
inefficient.

The original sample complexity of AltMin and Smooth AltMin is much higher than
that of AltGDmin or FactGD (see Table I). However, the corollary that we prove
for AltMin later in Sec VII shows that the AltMin sample complexity is
$\kappa^{4}\mu^{2}nr^{2}\log n\log(1/\epsilon)$ and its iteration complexity
is $\log(1/\epsilon)$.

In summary, when compared with all other methods, AltGDmin has the lowest
total communication cost. It also has one of the lowest total computation
costs and the second lowest sample cost. Moreover as we argue in detail in [1]
(Appendix C), AltGDmin is private and requires just one data exchange per
algorithm iteration. Federated FactGD can be made private with two data
exchanges per algorithm iteration. AltMin can be made private by solving the
LS problem needed to update ${\bm{U}}$ using GD rather than the closed form
solution. This requires order $\log(1/\epsilon)$ extra data exchanges per main
algorithm iteration. AltMin-Private is much slower both in numerical
experiments and using theoretical complexities; see Table I and Sec. VIII.

The reason that AltGDmin needs a factor of $\log(1/\epsilon)$ in its sample
complexity is because its proof uses sample-splitting. To our best knowledge,
all guarantees for all solutions for LRMC or LRCS that factor ${\bm{X}}$ as
${\bm{X}}={\bm{U}}\bm{B}$, and in which one (or both) of the two alternating
steps is a minimization step, use sample-splitting [3, 12, 24, 25, 22, 23].
Some of this cited work provides guarantees for LR phase retrieval which is a
phaseless measurements’ generalization of LRCS; and hence any LRPR solution
automatically solves LRCS. All three problems involve recovery from non-global
measurements (no scalar measurement depends on the entire ${\bm{X}}^{\star}$).
For such problems, properties such as restricted isometry property cannot be
proved.

The reason that AltGDmin iteration and sample complexity need an extra factor
of $\kappa^{2}$ is due to the orthonormalization step (QR step) when updating
${\bm{U}}$. For any algorithm that updates one or both of ${\bm{U}},\bm{B}$ by
GD, such a step is one way to prevent the norm of the estimate ${\bm{U}}$ from
increasing/decreasing over iterations (while that of $\bm{B}$
decreases/increases). The other way to ensure this is to add a norm balancing
term in the cost function for the GD step for ${\bm{U}}$, as done in FactGD.
However this would then also require a row norm clipping step for ${\bm{U}}$
at each iteration, like in FactGD. Use of these two steps to replace the QR
step can possibly help improve its dependence on $\kappa$. But it will also
mean that we cannot borrow the overall proof approach developed for AltGDmin
for LRCS in [23] that allows us to get a guarantee with a (nearly) constant
step size, consequently, a (nearly) best iteration complexity of
$\kappa^{2}\log(1/\epsilon)$.

###  III-B Proof Novelty

  1. 1.

The most important difference between LRCS and LRMC is that the LRMC proofs
require incoherence of each iterate of ${\bm{U}}$ and of $\bm{B}$. When
analyzing AltGDmin for LRCS in [22, 23], this was needed only for $\bm{B}$
because LRCS measurements are column-wise global (matrix $\bm{A}_{k}$ is dense
and so each entry of $\bm{y}_{k}$ depends on the entire column
$\bm{x}^{\star}_{k}$). Our proof of incoherence of each updated ${\bm{U}}$
needs a different approach than that used in all past work on LRMC as well
because our algorithm is different. (i) ProjGD [7] does not use a factorized
representation for ${\bm{X}}$ and hence the gradient w.r.t. ${\bm{U}}$ does
not exist for it. (ii) We do not update ${\bm{U}}$ by LS and hence we cannot
use the approach used for AltMin or Smooth AltMin [3, 12]. (iii) FactGD [11]
uses row norm clipping to ensure incoherence at each algorithm iteration,
while AltGDmin does not use this (except for initialization). The details of
our approach are explained below in the proof outlines, and in Lemma 4.6 (and
proof) and its use in proving Theorem 2.1.

As noted earlier, not using row norm clipping at each iteration is one reason
why we can borrow the overall proof technique used for LRCS [23] in order to
prove a correctness guarantee with a constant GD step size. The other reason
is that we use minimization for updating $\bm{B}$ (and not GD).

  2. 2.

Unlike LRCS, LRMC measurements are both row-wise and column-wise local.
Consequently, it is not possible to get a tight column-wise bound (bound on
$\|\bm{b}_{k}-{\bm{U}}^{\intercal}\bm{x}^{\star}_{k}\|$, and hence on
$\|\bm{x}_{k}-\bm{x}^{\star}_{k}\|$, for each $k$) under the desired sample
complexity. We can only bound
$\|\bm{B}-{\bm{U}}^{\intercal}{\bm{X}}^{\star}\|_{F}$ and
$\|{\bm{X}}-{\bm{X}}^{\star}\|_{F}$. This has implications on how we bound the
gradient norm (both the gradient expected value and its deviation from it).
This is one reason why the use of $\mathrm{SD}_{F}$ (instead of
$\mathrm{SD}_{2}$) in our bounding helps prove a better guarantee.

  3. 3.

We need to use the matrix Bernstein inequality [26] for bounding all of terms,
instead of the concentration bounds used in [23] (sub-Gausian Hoeffding or
sub-exponential Bernstein inequality followed by an epsilon-net argument).

  4. 4.

Our initialization guarantee is better than that of AltMin and Smooth Altmin
[3, 12] by a factor of $r^{3}$ and $r$ respectively, and comparable to that of
FactGD. The reason for this is that we adapt the row norm clipping idea of
[11] for our initialization step. This approach is better than the entry-wise
clipping used in [3]. Row norm clipping can be analyzed in terms of
$\mathrm{SD}_{F}({\bm{U}}^{(0)},{\bm{U}}^{\star}{})$ and this is the other
reason we use $\mathrm{SD}_{F}$ in our proofs (see Sec. III-D).

  5. 5.

All analysis of AltGDmin for LRCS has been for the noise-free case. In this
work, we also provide an extension of our result to the more practical noisy
case. Our proof explains a general strategy for doing this for any iterative
algorithm.

  6. 6.

Lastly, we also show how our lemmas can be used to improve the sample
complexity dependence of AltMin and Smoothed AltMin on $r$ from $r^{4.5}$ and
$r^{3}$ respectively to $r^{2}$.

###  III-C Proof outline of Theorem 2.1

Let ${\bm{U}}={\bm{U}}^{(t-1)}$,
$\bm{G}:={\bm{U}}^{\intercal}{\bm{X}}^{\star}$ and
${\bm{U}}^{+}={\bm{U}}^{(t)}$.

To prove Theorem 2.1, (i) we obtain a bound on
$\delta^{(t)}:=\mathrm{SD}_{F}({\bm{U}}^{+},{\bm{U}}^{\star}{})$ in terms of
$\delta^{(t-1)}=\mathrm{SD}_{F}({\bm{U}},{\bm{U}}^{\star}{})$ that can be used
to show exponential error decay, whp, under the desired sample complexity.
(ii) This bound requires the initialization error $\delta^{(0)}$ to be small
enough. Hence we also need to analyze the initialization step to show that
this is true whp. Initialization is analyzed in Lemma 4.1 (proof outline given
below). The overall idea for (i) is borrowed from [23] but there are
differences because we need each new ${\bm{U}}$ to be incoherent. We use
induction. The induction step assumes a certain bound on $\delta^{(t-1)}$ and
on the row norms of ${\bm{U}}$ and proves the same for its updated version,
${\bm{U}}^{+}$. To do this, we first use the induction assumption (which
implies $\kappa^{2}\mu$ row-incoherence of ${\bm{U}}$) and the fact that
$\mathbb{E}[\nabla_{\bm{U}}f({\bm{U}},\bm{B})]=p({\bm{X}}-{\bm{X}}^{\star})\bm{B}^{\intercal}$
to get a deterministic bound on $\delta^{(t)}$. Next, we get high probability
bounds on the terms of this bound using matrix Bernstein and appropriate
linear algebra. These are obtained in the lemmas given in Sec. IV-B. The last
step is to use the induction assumption and Lemma 4.6 to bound the row norms
of ${\bm{U}}^{+}$.

Finally, we simplify the bounds in order to show that, whp, $\delta^{(t)}$
decays exponentially with $t$ as long as $\eta$ is at most
$0.5/(p{\sigma_{\max}^{*}}^{2})$ and $\delta^{(0)}\leq c/\kappa^{2}$. The
proof is in Sec. IV-C and it relies on the six lemmas stated in Sec. IV-B.

###  III-D Proof outlines of the lemmas used to prove Theorem 2.1

Initialization Lemma 4.1 uses the following ideas, many of which are borrowed
from initialization step analysis of FactGD [11] (with filling in the missing
details from there). (i) Using the results of [27] (Lemma 3.21, Theorem 3.22),
we can bound $\mathrm{SD}_{F}({\bm{U}}^{(00)},{\bm{U}}^{\star}{})$. (ii) The
row norm clipping step can be interpreted as projecting its input onto a
convex set, ${\mathcal{U}}:=\\{{\bm{U}}:\|\bm{u}^{j}\|\leq\mu\sqrt{r/n}\\}$,
with the projection being in Frobenius norm. Projection onto convex sets is
non-expansive, i.e.,
$\|\Pi_{{\mathcal{U}}}({\bm{U}}_{1})-\Pi_{{\mathcal{U}}}({\bm{U}}_{2})\|_{F}\leq\|{\bm{U}}_{1}-{\bm{U}}_{2}\|_{F}$
[28, eq (9),(10)],[11]. Also,
$\Pi_{\mathcal{U}}({\bm{U}}^{\star}{}{\bm{Q}})={\bm{U}}^{\star}{}{\bm{Q}}$ for
any $r\times r$ unitary matrix ${\bm{Q}}$ (since ${\bm{U}}^{\star}{}$ as well
as ${\bm{U}}^{\star}{}$ times any unitary matrix belong to ${\mathcal{U}}$).
(iii) Let ${\bm{Q}}_{*,00}:=\operatorname*{\mathrm{argmin}}_{{\bm{Q}}\
unitary}\|{\bm{U}}^{(00)}-{\bm{U}}^{\star}{}Q\|_{F}$. By Lemmas 2.5 and 2.6 of
[27],
$\mathrm{SD}_{F}({\bm{U}}^{(00)},{\bm{U}}^{\star}{})\approx\|{\bm{U}}^{(00)}-{\bm{U}}^{\star}{}{\bm{Q}}_{*,00}\|_{F}$
(upper and lower bounded by RHS with a factor of $\sqrt{2}$ for upper bound).
(iv) The above ideas help bound
$\|\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})-{\bm{U}}^{\star}{}{\bm{Q}}_{*,00}\|_{F}$.
In the last step, we use this bound and
$\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})\overset{\mathrm{QR}}{=}{\bm{U}}^{(0)}{\bm{R}}^{(0)}$
to bound $\mathrm{SD}_{F}({\bm{U}}^{(0)},{\bm{U}}^{\star}{})$. The proof is in
Sec. V-A.

Lemma 4.2 uses incoherence of ${\bm{U}}$ and $\delta^{(t-1)}$ to bound
$\|\bm{B}-\bm{G}\|_{F}$ where $\bm{G}={\bm{U}}^{\intercal}{\bm{X}}^{\star}$.
This is proved by writing $vec(\bm{B}-\bm{G})={\bm{F}}^{-1}vec({\bm{D}})$,
where ${\bm{F}}\in\mathbb{R}^{nr\times nr}$ and
${\bm{D}}\in\mathbb{R}^{r\times q}$ are defined below in Sec. IV-A, bounding
$\|{\bm{F}}^{-1}\|$ and $\|{\bm{D}}\|$ by the matrix Bernstein inequality, and
using
$\|\bm{B}-\bm{G}\|_{F}=\|vec(\bm{B}-\bm{G})\|\leq\|{\bm{F}}^{-1}\|\cdot\|vec({\bm{D}})\|=\|{\bm{F}}^{-1}\|\cdot\|{\bm{D}}\|_{F}\leq\|{\bm{F}}^{-1}\|\cdot\sqrt{r}\|{\bm{D}}\|$.
The bound on $\|{\bm{F}}^{-1}\|$ is borrowed from [3], while the rest of our
bounding is different and simpler than the approach used in [3]. We use matrix
Bernstein which provides a much simpler proof and the resulting bound holds
with a smaller sample complexity (better dependence on $r$). The proof is in
Sec. V-B. Lemma 4.3 uses the $\|\bm{B}-\bm{G}\|_{F}$ bound to bound
$\|{\bm{X}}-{\bm{X}}\|_{F}$, and the minimum and maximums singular values of
$\bm{B}$. The proof idea is similar to that in [22]. We provide the proof in
Sec. V-C anyway since it is very short.

Lemma 4.4 uses incoherence of ${\bm{U}}$ to show incoherence of $\bm{B}$. It
follows by writing
$\bm{b}_{k}=({\bm{U}}_{k}^{\intercal}{\bm{U}}_{k})^{-1}({\bm{U}}_{k}^{\intercal}{\bm{U}}^{\star}{}_{k})\bm{b}^{\star}_{k}$,
using the fact that
$\mathbb{E}[{\bm{U}}_{k}^{\intercal}{\bm{U}}_{k}]=p{\bm{U}}^{\intercal}{\bm{U}}=p\bm{I}$,
$\mathbb{E}[{\bm{U}}_{k}^{\intercal}{\bm{U}}^{\star}{}_{k}]=p{\bm{U}}^{\intercal}{\bm{U}}^{\star}{}$,
$\|{\bm{U}}^{\intercal}{\bm{U}}^{\star}{}\|\leq 1$, and using matrix Bernstein
to bound deviations of both matrices from their expected values. This proof is
also much simpler than the one given in [3] and the result needs a smaller
sample complexity (better dependence on $r$). The proof is in Sec. V-D.

Lemma 4.5 uses the $\bm{B}-\bm{G}$ bound and its implications,
$\delta^{(t-1)}<c/\kappa^{2}$, and incoherence of ${\bm{U}}$ and of $\bm{B}$
to bound the gradient norm. It relies on the following ideas.
$\mathbb{E}[\mathrm{GradU}]=p({\bm{X}}-{\bm{X}}^{\star})\bm{B}^{\intercal}$.
This holds since the expectation is taken with respect to an independent set
of samples at each iteration (possible because of sample splitting). We bound
the deviation from the expected value using matrix Bernstein inequality and
the assumed bounds in the lemma assumptions. The proof is in Sec. V-E.

Lemma 4.6 uses incoherence of $\bm{B}$ to show incoherence of ${\bm{U}}$. (i)
We first bound the deviation of the $j$-th row of $\mathrm{GradU}$, denoted
$\mathrm{GradU}^{j}$, from its expected value in terms of
$\max(\|\bm{u}^{j}\|,\|\bm{u}^{*}{}^{j}\|)$. To get a high probability bound
of this form, we use matrix Bernstein inequality and the fact that, for
showing incoherence, we do not need the bound to contain $\delta^{(t-1)}$.
Hence, we can use a seemingly loose bound of the form
$|\bm{x}_{jk}-\bm{x}^{\star}_{jk}|\leq
2\max(|\bm{x}_{jk}|,|\bm{x}^{\star}_{jk}|)\leq
2.2\mu\sqrt{r/q}{\sigma_{\max}^{*}}\cdot\max(\|\bm{u}^{j}\|,\|\bm{u}^{*}{}^{j}\|)$.
This bound is, in fact, tighter than a bound that contains $\delta^{(t-1)}$
for the initial iterations when $\delta^{(t-1)}$ is allowed to be larger than
order $\sqrt{r/q}$. (ii) Next we use
$\tilde{\bm{u}}^{j^{(t+1)}}={\bm{u}^{j}}^{(t)}-\eta\mathrm{Grad}{\bm{u}^{j}}\pm\mathbb{E}[\mathrm{Grad}{\bm{u}^{j}}]$,
$\mathbb{E}[\mathrm{GradU}^{j}]=p(\bm{u}^{j}{}^{\intercal}\bm{B}\bm{B}^{\intercal}-\bm{u}^{*}{}^{j}{}^{\intercal}{\bm{B}^{\star}}\bm{B}^{\intercal})$,
and an upper bound on the GD step size $\eta$ to show the second part of this
lemma:
$\|{\bm{u}^{j}}^{+}\|\leq(1-c/\kappa^{2})\|{\bm{u}^{j}}\|+2\|{\bm{u}^{*}{}{}^{j}}\|$.
The proof is provided in Sec. V-F.

##  IV Proving Theorem 2.1

###  IV-A Definitions and Expressions

Let ${\bm{U}}\equiv{\bm{U}}^{(t-1)}$, $\bm{B}\equiv\bm{B}^{(t)}$, and
${\bm{X}}\equiv{\bm{X}}^{(t)}={\bm{U}}^{(t-1)}\bm{B}^{(t)}$. Also let
${\bm{U}}^{+}\equiv{\bm{U}}^{(t)}$, $\bm{B}^{+}\equiv\bm{B}^{(t+1)}$. Let
$\bm{G}:={\bm{U}}^{\intercal}{\bm{X}}^{\star}$ and
$\bm{P}_{*,\perp}:=\bm{I}-{\bm{U}}^{\star}{}{\bm{U}}^{\star}{}^{\intercal}$.
Finally, Let

$\delta^{(t)}:=\mathrm{SD}_{F}({\bm{U}}^{(t)},{\bm{U}}^{*})=\|\bm{P}_{*,\perp}{\bm{U}}^{+}\|_{F}$

Thus, $\delta^{(t-1)}=\mathrm{SD}_{F}({\bm{U}},{\bm{U}}^{\star}{})$,
$\delta^{(t)}=\mathrm{SD}_{F}({\bm{U}}^{+},{\bm{U}}^{\star}{})=\|\bm{P}_{*,\perp}{\bm{U}}^{+}\|_{F}$,
and $\bm{P}_{*,\perp}{\bm{X}}^{\star}=\bm{0}$.

Let $\mu_{u}:=20\kappa^{2}\mu$. All our proofs use $c,C$ to denote different
numerical constants in each use. The numerical values in our intermediate
steps are often loose bounds to make the analysis simpler.

Recall that ${\bm{U}}_{k}:=\bm{S}_{k}{\bm{U}}$ where
$\bm{S}_{k}=\mathrm{diag}(\xi_{jk},j\in[n])$. Similarly, let
${\bm{U}}^{\star}{}_{k}:=\bm{S}_{k}{\bm{U}}^{\star}{}$. Thus

$\bm{S}_{k}^{\intercal}\bm{S}_{k}=\bm{S}_{k}\bm{S}_{k}=\bm{S}_{k},$
${\bm{U}}_{k}=\bm{S}_{k}{\bm{U}}=\sum_{j=1}^{n}\xi_{jk}\bm{e}_{j}\bm{u}^{j}{}^{\intercal},\
{\bm{U}}^{\star}{}_{k}=\sum_{j=1}^{n}\xi_{jk}\bm{e}_{j}\bm{u}^{*}{}^{j}{}^{\intercal},$

and consequently,

${\bm{U}}_{k}^{\intercal}{\bm{U}}^{\star}{}_{k}={\bm{U}}^{\intercal}\bm{S}_{k}{\bm{U}}^{\star}{}=\sum_{j=1}^{n}\xi_{jk}\bm{u}^{j}\bm{u}^{*}{}^{j}{}^{\intercal}$

Using this,

$\bm{b}_{k}={\bm{U}}_{k}^{\dagger}\bm{y}_{k}={\bm{U}}_{k}^{\dagger}\bm{S}_{k}\bm{x}^{\star}_{k}=({\bm{U}}_{k}^{\intercal}{\bm{U}}_{k})^{-1}{\bm{U}}_{k}^{\intercal}{\bm{U}}^{\star}{}_{k}\bm{b}^{\star}_{k}=({\bm{U}}^{\intercal}\bm{S}_{k}{\bm{U}})^{-1}{\bm{U}}^{\intercal}\bm{S}_{k}{\bm{U}}^{\star}{}\bm{b}^{\star}_{k}$

Thus,
$\bm{b}_{k}-\bm{g}_{k}=\bm{b}_{k}-{\bm{U}}^{\intercal}{\bm{U}}^{\star}{}\bm{b}^{\star}_{k}$
simplifies to

$\bm{b}_{k}-\bm{g}_{k}=({\bm{U}}^{\intercal}\bm{S}_{k}{\bm{U}})^{-1}[{\bm{U}}^{\intercal}\bm{S}_{k}{\bm{U}}^{\star}{}\bm{b}^{\star}_{k}-({\bm{U}}^{\intercal}\bm{S}_{k}{\bm{U}}){\bm{U}}^{\intercal}{\bm{U}}^{\star}{}\bm{b}^{\star}_{k}]=(\
\underbrace{{\bm{U}}^{\intercal}\bm{S}_{k}{\bm{U}}}_{{\bm{F}}_{k}}\
)^{-1}\underbrace{{\bm{U}}^{\intercal}\bm{S}_{k}[\bm{I}-{\bm{U}}{\bm{U}}^{\intercal}]{\bm{U}}^{\star}{}\bm{b}^{\star}_{k}}_{\bm{d}_{k}}$
(4)

with

$\bm{d}_{k}:={\bm{U}}^{\intercal}\bm{S}_{k}[\bm{I}-{\bm{U}}{\bm{U}}^{\intercal}]{\bm{U}}^{\star}{}\bm{b}^{\star}_{k},\
{\bm{F}}_{k}:={\bm{U}}^{\intercal}\bm{S}_{k}{\bm{U}}$

Thus, letting ${\bm{F}}:=\mathrm{blockdiag}({\bm{F}}_{k},k\in[q])$,

$vec(\bm{B}-\bm{G})={\bm{F}}^{-1}vec({\bm{D}}),\text{ where
}{\bm{D}}:=[\bm{d}_{1},\bm{d}_{2},\dots\bm{d}_{q}]=\sum_{k}\sum_{j}\xi_{jk}\bm{u}^{j}{[[\bm{I}-{\bm{U}}{\bm{U}}^{\intercal}]{\bm{U}}^{\star}{}]^{j}}^{\intercal}\bm{b}^{\star}_{k}\bm{e}_{k}^{\intercal}$

In the above ${\bm{F}}\in\mathbb{R}^{rq\times rq}$ and
${\bm{D}}\in\mathbb{R}^{r\times q}$. Observe that

$\mathbb{E}[\bm{S}_{k}]=p\bm{I},\ \mathbb{E}[{\bm{D}}]=\bm{0}$

Finally,

$\mathrm{GradU}:=\nabla_{{\bm{U}}}f({\bm{U}},\bm{B})=2({\bm{X}}_{\Omega}-\bm{Y})\bm{B}^{\intercal}=2\sum_{k=1}^{q}\bm{S}_{k}(\bm{x}_{k}-\bm{x}^{\star}_{k})\bm{b}_{k}^{\intercal}=2\sum_{k=1}^{q}\sum_{j=1}^{n}\xi_{jk}\bm{e}_{j}(\bm{x}_{jk}-\bm{x}^{\star}_{jk})\bm{b}_{k}^{\intercal}$
(5)

where ${\bm{X}}={\bm{U}}\bm{B}$,
${\bm{X}}^{\star}={\bm{U}}^{\star}{}{\bm{B}^{\star}}$,
$\bm{x}_{jk}=\bm{u}^{j}{}^{\intercal}\bm{b}_{k}$ and
$\bm{x}^{\star}_{jk}=\bm{u}^{*}{}^{j}{}^{\intercal}\bm{b}^{\star}_{k}$. Also,

$\mathrm{GradU}^{j}:=\bm{e}_{j}^{\intercal}\nabla_{{\bm{U}}}f({\bm{U}},\bm{B})=2\sum_{k=1}^{q}\xi_{jk}(\bm{x}_{jk}-\bm{x}^{\star}_{jk})\bm{b}_{k}^{\intercal},$

Observe that

$\mathbb{E}[\mathrm{GradU}]=p({\bm{X}}-{\bm{X}}^{\star})\bm{B}^{\intercal}\text{
and
}\mathbb{E}[\mathrm{GradU}^{j}]=p\bm{e}_{j}^{\intercal}({\bm{X}}-{\bm{X}}^{\star})\bm{B}^{\intercal}$

###  IV-B Lemmas for proving Theorem 2.1

All lemmas below assume Assumption 1.1 (singular vectors’ incoherence) holds.
Also, everywhere $\epsilon<1$.

######  Lemma 4.1 (Initialization).

Pick a $\delta\leq 0.2$. Assume $p\geq C{\kappa^{2}r^{2}\mu\log
q}/{(n\delta^{2})}$. Then, w.p. at least $1-n^{-10}$.

  1. 1.

$\mathrm{SD}_{F}({\bm{U}}^{(0)},{\bm{U}}^{*})\leq\delta$.

  2. 2.

${\bm{U}}^{(0)}$ is $1.5\mu$ row-incoherent, i.e., $\|\bm{u}^{j}{}^{(0)}\|\leq
1.5\mu\sqrt{r/n}$ for all $j\in[n]$.

######  Lemma 4.2 (LS step analysis: error bound for $\bm{B}$).

Assume $\|{\bm{u}^{j}}\|\leq\mu_{u}\sqrt{r/n}$. Then, w.p. at least
$1-\exp(\log q-c\frac{\epsilon^{2}pn}{r^{2}\mu_{u}^{2}})$,

$\|\bm{B}-\bm{G}\|_{F}\leq\epsilon\delta^{(t-1)}{\sigma_{\max}^{*}}$

######  Lemma 4.3 (Implications of error bound for $\bm{B}$).

Assume $\|\bm{B}-\bm{G}\|_{F}\leq\delta^{(t-1)}{\sigma_{\max}^{*}}$. Then,

  1. 1.

$\|{\bm{X}}-{\bm{X}}^{\star}\|_{F}\leq 2\delta^{(t-1)}{\sigma_{\max}^{*}}$.

  2. 2.

$\sigma_{\max}(\bm{B})\leq(1+\delta^{(t-1)}){\sigma_{\max}^{*}}$ and
$\sigma_{\min}(\bm{B})\geq\sqrt{1-\delta^{(t-1)}{}^{2}}\sigma_{\min}^{*}-\delta^{(t-1)}{\sigma_{\max}^{*}}$.

  3. 3.

Thus, if $\delta^{(t-1)}\leq c/\kappa$, then $\sigma_{\min}(\bm{B})\geq
0.9{\sigma_{\min}^{*}}$ and $\sigma_{\max}(\bm{B})\leq
1.1{\sigma_{\max}^{*}}$.

######  Lemma 4.4 (Incoherence of $\bm{B}$).

Assume that $\|{\bm{u}^{j}}\|\leq\mu_{u}\sqrt{r/n}$. Then, w.p. greater than
$1-\exp(\log q-c\frac{np}{\mu_{u}^{2}r})$,

$\|\bm{b}_{k}\|\leq 1.1{\sigma_{\max}^{*}}\mu\sqrt{{r}/{q}}\ \text{ for all
}k\in[q].$

######  Lemma 4.5 (Gradient expression and bounds).

Assume that $\|\bm{B}-\bm{G}\|_{F}\leq\delta^{(t-1)}{\sigma_{\max}^{*}}$ with
$\delta^{(t-1)}\leq c/\kappa$, $\|{\bm{u}^{j}}\|\leq\mu_{u}\sqrt{r/n}$,
$\|\bm{b}_{k}\|\leq{\sigma_{\max}^{*}}\mu\sqrt{r/q}$. Then,

  1. 1.

$\|\mathbb{E}[\mathrm{GradU}]\|_{F}\leq
2.5p\delta^{(t-1)}{\sigma_{\max}^{*2}}$.

  2. 2.

$\|\mathrm{GradU}-\mathbb{E}[\mathrm{GradU}]\|_{F}\leq\epsilon
p\delta^{(t-1)}{\sigma_{\min}^{*2}}$, w.p. at least $1-\exp(\log
q-c\frac{\epsilon^{2}pn}{\max(\kappa^{4}\mu^{2},\kappa^{2}\mu_{u}\mu)r^{2}})$

######  Lemma 4.6 (Incoherence of ${\bm{U}}$).

Assume that $\|\bm{b}_{k}\|\leq 1.1{\sigma_{\max}^{*}}\mu\sqrt{r/q}$. Then,
w.p. greater than $1-\exp(\log q-c\epsilon^{2}pn/\kappa^{4}\mu^{2}r^{2})$

  1. 1.

$\|\mathrm{Grad}{\bm{u}^{j}}-\mathbb{E}[\mathrm{Grad}{\bm{u}^{j}}]\|\leq\epsilon
p\max(\|{\bm{u}^{j}}\|,\|{\bm{u}^{*}{}^{j}}\|){\sigma_{\min}^{*2}}$

  2. 2.

Further, if $\|\bm{B}-\bm{G}\|_{F}\leq\delta^{(t-1)}{\sigma_{\max}^{*}}$ with
$\delta^{(t-1)}<c/\kappa$, and GD step size $\eta\leq
0.5/(p{\sigma_{\max}^{*}}^{2})$, then

$\|{\bm{u}^{j}}^{+}\|\leq(1-0.15/\kappa^{2})\|{\bm{u}^{j}}\|+2\|{\bm{u}^{*}{}{}^{j}}\|.$

###### Proof.

All these lemmas are proved in Sec V. ∎

###  IV-C Proof of Theorem 2.1

We prove the following result, Claim 4.7, using an induction argument and the
lemmas from Sec. IV-B. Theorem 2.1 follows from the first claim of this result
along with using the following:

  * •

To ensure $\delta^{(T)}\leq\epsilon$, we need
$(1-c/\kappa^{2})^{T}\cdot(c/\kappa^{2})\leq\epsilon$ or that
$T=C\kappa^{2}\log(1/\epsilon)$.

  * •

Since we use sample splitting, the total number of samples needed for all $T$
iterations is $2T\cdot np\geq C\kappa^{4}\mu^{2}r^{2}\log
q\cdot\kappa^{2}\log(1/\epsilon)$. If all samples are generated first and then
subsets used across different iterations (as specified in our stepwise
algorithm, Algorithm 1), we need to assume that an entry is observed w.p.
$p_{tot}=2T\cdot p$ and $np_{tot}\geq C\kappa^{4}\mu^{2}r^{2}\log
q\cdot\kappa^{2}\log(1/\epsilon)$.

######  Claim 4.7.

Assume everything stated in Theorem 2.1 and $np\geq
C\kappa^{4}\mu^{2}r^{2}\log q$. For all times $\tau\geq 0$, the following hold
w.p. at least $1-\tau/n^{3}$: (i)
$\delta^{(\tau)}\leq(1-c/\kappa^{2})^{\tau}\cdot(c/\kappa^{2})$; and (ii)
$\|{\bm{u}^{j}}^{(\tau)}\|\leq(1-\frac{0.15}{\kappa^{2}})^{\tau}1.5\mu\sqrt{r/n}+[1+(1-\frac{0.15}{\kappa^{2}})+\dots+(1-\frac{0.15}{\kappa^{2}})^{\tau-1}]2\|{\bm{u}^{*}{}{}^{j}}\|$

Base case: Lemma 4.1 shows that $\delta^{(0)}\leq\delta=0.1/\kappa^{2}$ and
$\|{\bm{u}^{j}}^{(0)}\|\leq 1.5\mu\sqrt{r/n}$. This proves (i) and (ii) for
$\tau=0$.

Induction assumption: Assume that the claim holds for $\tau=t-1$.

Induction step: Consider $\tau=t$. Recall from Algorithm that
$\tilde{\bm{U}}^{+}={\bm{U}}-\eta\mathrm{GradU}$, and
${\bm{U}}^{+}=\tilde{\bm{U}}^{+}{\bm{R}}^{+}{}^{-1}$ where
$\tilde{\bm{U}}^{+}\overset{\mathrm{QR}}{=}{\bm{U}}^{+}{\bm{R}}^{+}$. Recall
from Sec. IV-A that $\bm{P}_{*,\perp}{\bm{X}}^{\star}=\bm{0}$,
$\mathbb{E}[\mathrm{GradU}]=p({\bm{U}}\bm{B}-{\bm{X}}^{\star})\bm{B}^{\intercal}$,
$\|\bm{P}_{*,\perp}{\bm{U}}\|_{F}=\delta^{(t-1)}$. Also, using Weyl’s
inequality,
$\sigma_{\min}({\bm{R}}^{+})=\sigma_{\min}(\tilde{\bm{U}}^{+})\geq\sigma_{\min}({\bm{U}})-\eta||\mathrm{GradU}||=1-\eta||\mathrm{GradU}||$.
Using these,

$\displaystyle\delta^{(t)}$
$\displaystyle=\mathrm{SD}_{F}({\bm{U}}^{+},{\bm{U}}^{\star}{})=\|\bm{P}_{*,\perp}{\bm{U}}^{+}\|_{F}$
$\displaystyle\leq\|\bm{P}_{*,\perp}\tilde{\bm{U}}^{+}\|_{F}\cdot\|({\bm{R}}^{+})^{-1}\|=\|\bm{P}_{*,\perp}\tilde{\bm{U}}^{+}\|_{F}/\sigma_{\min}(\tilde{\bm{U}}^{+})$
$\displaystyle\leq\frac{\|\bm{P}_{*,\perp}({\bm{U}}-\eta\mathbb{E}[\mathrm{GradU}]+\eta\mathbb{E}[\mathrm{GradU}]-\eta\mathrm{GradU})\|_{F}}{(1-\eta\|\mathrm{GradU}\|)}$
$\displaystyle\leq\frac{\|\bm{P}_{*,\perp}({\bm{U}}-\eta
p({\bm{U}}\bm{B}-{\bm{X}}^{\star})\bm{B}^{\intercal})\|_{F}+\eta\|\mathbb{E}[\mathrm{GradU}]-\mathrm{GradU})\|_{F}}{(1-\eta\|\mathbb{E}[\mathrm{GradU}]\|-\eta\|\mathbb{E}[\mathrm{GradU}]-\mathrm{GradU}\|)}$
$\displaystyle\leq\frac{\delta^{(t-1)}\cdot\|\bm{I}-\eta
p\bm{B}\bm{B}^{\intercal}\|+\eta\|\mathbb{E}[\mathrm{GradU}]-\mathrm{GradU})\|_{F}}{(1-\eta\|\mathbb{E}[\mathrm{GradU}]\|-\eta\|\mathbb{E}[\mathrm{GradU}]-\mathrm{GradU}\|)}$
(6)

By the induction assumption,
$\delta^{(t-1)}\leq(1-c/\kappa^{2})^{t-1}\cdot(c/\kappa^{2})\leq(c/\kappa^{2})$
and

$\displaystyle\|\bm{u}^{j}\|=\|{\bm{u}^{j}}^{(t-1)}\|$
$\displaystyle\leq(1-\frac{0.15}{\kappa^{2}})^{t-1}\|{\bm{u}^{j}}^{(0)}\|+[1+(1-\frac{0.15}{\kappa^{2}})+\dots+(1-\frac{0.15}{\kappa^{2}})^{t-2}]2\|{\bm{u}^{*}{}{}^{j}}\|$
$\displaystyle\leq\|{\bm{u}^{j}}^{(0)}\|+\frac{\kappa^{2}}{0.15}2\|{\bm{u}^{*}{}{}^{j}}\|\leq(1.5\mu+14\kappa^{2}\mu)\sqrt{r/n}\leq\mu_{u}\sqrt{r/n}$
(7)

The last inequality above used the infinite geometric series bound. This shows
that ${\bm{U}}$ is $\mu_{u}$-row-incoherent.

Using (7) and $\delta^{(t-1)}\leq(c/\kappa^{2})$ , Lemmas 4.2 and 4.4 hold,
i.e. the bound on $\|\bm{B}-\bm{G}\|_{F}$ and $\|\bm{b}_{k}\|$ holds. This
then implies that all claims of Lemma 4.3 hold too. This then implies that
Lemmas 4.5 and 4.6 hold. All the lemmas hold with probability at least
$1-1/n^{3}$ if $p$ is such that all the probabilities stated in all the lemmas
are lower bounded by $1-0.1/n^{3}$. Using $\mu_{u}=8\kappa^{2}\mu$, clearly,
this is true if

$np\geq C\kappa^{4}\mu^{2}r^{2}\log q$

By Lemmas 4.2 and 4.3, $\sigma_{\min}(\bm{B})\geq 0.9{\sigma_{\min}^{*}}$ and
$\|\bm{B}\|\leq 1.1{\sigma_{\max}^{*}}$. Using these, if $\eta\leq
0.5/(p{\sigma_{\max}^{*2}})$, then $\bm{I}-\eta p\bm{B}\bm{B}^{\intercal}$ is
positive semi-definite (psd) and hence $\|\bm{I}-\eta
p\bm{B}\bm{B}^{\intercal}\|=\lambda_{\max}(\bm{I}-\eta
p\bm{B}\bm{B}^{\intercal})\leq 1-0.8\eta p{\sigma_{\min}^{*2}}$. Using Lemma
4.4, $\bm{B}$ is $1.1\mu$-column-incoherent. Using Lemma 4.5,
$\|\mathbb{E}[\mathrm{GradU}]\|\leq 2.5p\delta^{(t-1)}{\sigma_{\max}^{*2}}$
and $\|\mathrm{GradU}-\mathbb{E}[\mathrm{GradU}]\|_{F}\leq\epsilon
p\delta^{(t-1)}{\sigma_{\min}^{*2}}$. Substituting these into (6) with
$\epsilon=0.01$,

$\displaystyle\delta^{(t)}$
$\displaystyle\leq\frac{\delta^{(t-1)}\big{(}1-0.8\eta
p{\sigma_{\min}^{*2}}+0.01\eta
p{\sigma_{\min}^{*2}}\big{)}}{1-\delta^{(t-1)}\big{(}2.55\eta
p{\sigma_{\max}^{*2}}\big{)}}.$ $\displaystyle\leq\delta^{(t-1)}(1-0.79\eta
p{\sigma_{\min}^{*2}})(1+2\delta^{(t-1)}(2.55\eta p{\sigma_{\max}^{*2}}))$
$\displaystyle\leq\delta^{(t-1)}(1-(0.79-\delta^{(t-1)}5.1\kappa^{2})\eta
p{\sigma_{\min}^{*2}})\leq\delta^{(t-1)}(1-\eta
p{\sigma_{\min}^{*2}}(0.79-0.051))\leq\delta^{(t-1)}(1-0.3\eta
p{\sigma_{\min}^{*2}})$

In the above, for the denominator term we used $1/(1-x)\leq 1+2x$ for $x<0.5$
and $\delta^{(t-1)}\leq 0.01/\kappa^{2}$. Setting
$\eta=0.5/(p{\sigma_{\max}^{*2}})$ in the final expression given above, we can
conclude that

$\delta^{(t)}\leq(1-0.15/\kappa^{2})\delta^{(t-1)}\leq(1-0.15/\kappa^{2})^{t}\cdot(0.1/\kappa^{2}).$

Thus claim (i) holds for $\tau=t$. Next we prove claim (ii) for $\tau=t$. By
Lemma 4.6 and the induction assumption,

$\displaystyle\|{\bm{u}^{j}}^{(t)}\|$
$\displaystyle=\|{\bm{u}^{j}}^{+}\|\leq(1-0.15/\kappa^{2})\|{\bm{u}^{j}}\|+2\|{\bm{u}^{*}{}{}^{j}}\|$
$\displaystyle\leq(1-0.15/\kappa^{2})^{t}1.5\mu\sqrt{r/n}+(1-0.15/\kappa^{2})[1+(1-\frac{0.15}{\kappa^{2}})+\dots+(1-\frac{0.15}{\kappa^{2}})^{t-2}]2\|{\bm{u}^{*}{}{}^{j}}\|+2\|{\bm{u}^{*}{}{}^{j}}\|$
$\displaystyle=(1-0.15/\kappa^{2})^{t}1.5\mu\sqrt{r/n}+[1+(1-\frac{0.15}{\kappa^{2}})+\dots+(1-\frac{0.15}{\kappa^{2}})^{t-1}]2\|{\bm{u}^{*}{}{}^{j}}\|$

##  V Proofs of the Lemmas

###  V-A Proof of Lemma 4.1

By Lemmas 2.5 and 2.6 of [27], for two $n\times r$ matrices with orthonormal
columns, ${\bm{U}}_{1},{\bm{U}}_{2}$,

$\displaystyle\mathrm{SD}_{F}({\bm{U}}_{1},{\bm{U}}_{2})\leq\min_{{\bm{Q}}\
unitary}\|{\bm{U}}_{1}-{\bm{U}}_{2}{\bm{Q}}\|_{F}\leq\sqrt{2}\mathrm{SD}_{F}({\bm{U}}_{1},{\bm{U}}_{2})$
(8)

and a similar bound holds for $\mathrm{SD}_{2}$ as well. We use this fact
frequently below.

Recall from the Algorithm that
$\bm{Y}\overset{\mathrm{SVD}}{=}{\bm{U}}^{(00)}\Sigma^{(00)}\bm{V}^{(00)}$,
and
$\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})\overset{\mathrm{QR}}{=}{\bm{U}}^{(0)}{\bm{R}}^{(0)}$.
By Theorem 3.22 of [27] along with using (8) and
$\mathrm{SD}_{2}({\bm{U}}_{1},{\bm{U}}_{2})\leq\sqrt{r}\mathrm{SD}_{F}({\bm{U}}_{1},{\bm{U}}_{2})$,
we have: with probability at least $1-Cq^{-10}$,

$\mathrm{SD}_{F}({\bm{U}}^{(00)},{\bm{U}}^{\star}{})\leq
C\sqrt{\frac{\kappa^{2}\mu r^{2}\log q}{np}}$

Let ${\bm{Q}}_{*,00}=\arg\min_{{\bm{Q}}\
unitary}\|{\bm{U}}^{(00)}-{\bm{U}}^{\star}{}{\bm{Q}}\|_{F}$. By (8),

$\|{\bm{U}}^{(00)}-{\bm{U}}^{\star}{}{\bm{Q}}_{*,00}\|_{F}\leq\sqrt{2}\mathrm{SD}_{F}({\bm{U}}^{(00)},{\bm{U}}^{\star}{})$

Next we use the above two bounds and the fact that ${\mathcal{U}}$ is a convex
set111To see that ${\mathcal{U}}$ is a convex set, let matrices
$\bm{M}_{1},\bm{M}_{2}\in{\mathcal{U}}$. Let $\bm{m}_{1}^{j}$ and
$\bm{m}_{2}^{j}$ denote the rows of $\bm{M}_{1}$ and $\bm{M}_{2}$,
respectively. For any $0<\theta<1$,
$\|\theta\bm{m}_{1}^{j}+(1-\theta)\bm{m}_{2}^{j}\|\leq\theta\|\bm{m}_{1}^{j}\|+(1-\theta)\|\bm{m}_{2}^{j}\|\leq\theta\mu\sqrt{r/n}+(1-\theta)\mu\sqrt{r/n}=\mu\sqrt{r/n}.$
to bound
$\|\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})-{\bm{U}}^{\star}{}{\bm{Q}}_{*,00}\|_{F}$
as follows.

$\displaystyle\|\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})-{\bm{U}}^{\star}{}{\bm{Q}}_{*,00}\|_{F}=\|\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})-\Pi_{{\mathcal{U}}}({\bm{U}}^{\star}{}{\bm{Q}}_{*,00})\|_{F}\leq\|{\bm{U}}^{(00)}-{\bm{U}}^{\star}{}{\bm{Q}}_{*,00}\|_{F}\leq\sqrt{2}\mathrm{SD}_{F}({\bm{U}}^{(00)},{\bm{U}}^{\star}{})\leq
C\sqrt{\frac{\kappa^{2}\mu r^{2}\log q}{np}}$

with probability at least $1-Cq^{-10}$. The first equality above uses the fact
that, for any unitary ${\bm{Q}}$, ${\bm{U}}^{\star}{}{\bm{Q}}$ belongs to
${\mathcal{U}}$. This is a direct consequence of our incoherence assumption
Assumption 1.1. The second one uses the facts that projection onto
${\mathcal{U}}$, which is a convex set, is non-expansive [28, eq. (9),(10)],
[29, eq. (1.5)]). The projection
$\Pi_{{\mathcal{U}}}(\bm{M}):=\min_{{\bm{U}}\in{\mathcal{U}}}\|{\bm{U}}-\bm{M}\|_{F}$
is non-expansive means that
$\|\Pi_{{\mathcal{U}}}(\bm{M})-\Pi_{{\mathcal{U}}}(\bm{M}_{2})\|_{F}\leq\|\bm{M}-\bm{M}_{2}\|_{F}$.

Finally, we use the above to bound
$\mathrm{SD}_{F}({\bm{U}}^{(0)},{\bm{U}}^{\star}{})=\|\bm{P}_{*,\perp}{\bm{U}}^{(0)}\|_{F}=\|\bm{P}_{*,\perp}\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)}){\bm{R}}^{(0)}{}^{-1}\|_{F}$.
Using $\bm{P}_{*,\perp}{\bm{U}}^{\star}{}{\bm{Q}}_{*,00}=\bm{0}$, and
$x/(1-x)<1.5x$ for any $0\leq x\leq 0.3$, we have: if
$C\sqrt{\frac{\kappa^{2}\mu r^{2}\log q}{np}}<0.3$, then

$\displaystyle\mathrm{SD}_{F}({\bm{U}}^{(0)},{\bm{U}}^{\star}{})=\|\bm{P}_{*,\perp}{\bm{U}}^{(0)}\|_{F}$
$\displaystyle\leq\|\bm{P}_{*,\perp}\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})\|_{F}\|{\bm{R}}^{(0)}{}^{-1}\|$
$\displaystyle\leq\frac{\|\bm{P}_{*,\perp}{\bm{U}}^{\star}{}{\bm{Q}}_{*,00}\|_{F}+\|\bm{P}_{*,\perp}(\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})-{\bm{U}}^{\star}{}{\bm{Q}}_{*,00})\|_{F}}{\sigma_{\min}(\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})}$
$\displaystyle\leq\frac{\|\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})-{\bm{U}}^{\star}{}{\bm{Q}}_{*,00}\|_{F}}{1-\|\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})-{\bm{U}}^{\star}{}{\bm{Q}}_{*,00}\|_{F}}\leq\frac{C\sqrt{\frac{\kappa^{2}\mu
r^{2}\log q}{np}}}{1-C\sqrt{\frac{\kappa^{2}\mu r^{2}\log q}{np}}}\leq
1.5C\sqrt{\frac{\kappa^{2}\mu r^{2}\log q}{np}}$

The denominator bound follows by Weyl’s inequality,
$\sigma_{\min}({\bm{U}}^{\star}{}{\bm{Q}}_{*,00})=1$, and $x/(1-x)<1.5x$ for
$0<x<0.3$. Thus, for a $\delta<0.3$, w.p. at least $1-q^{-10}$,
$\mathrm{SD}_{F}({\bm{U}}^{(0)},{\bm{U}}^{\star}{})\leq\delta$ if $p\geq
C\kappa^{2}\mu r^{2}\log q/n\delta^{2}$.

####  V-A1 Proof of $\mu$-incoherence

We have
$\bm{u}^{j}{}^{(0)}=(\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)}))^{j}{\bm{R}}^{(0)}{}^{-1}$.
Thus, using the denominator bound from above,

$\|\bm{u}^{j}{}^{(0)}\|\leq\|(\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)}))^{j}\|\|{\bm{R}}^{(0)}{}^{-1}\|=\frac{\|(\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)}))^{j}\|}{\sigma_{\min}(\Pi_{{\mathcal{U}}}({\bm{U}}^{(00)})}\leq\frac{\mu\sqrt{r/n}}{1-C\sqrt{\frac{\kappa^{2}\mu
r^{2}\log q}{np}}}$

Our assumed bound on $p$ implies that the denominator is at least $1-\delta$
for a $\delta<0.3$. This then implies the above is upper bounded by
$1.5\mu\sqrt{r/n}$.

###  V-B Proof of Lemma 4.2

Let $\delta=\delta^{(t-1)}$. Recall from Sec. IV-A that
$vec(\bm{B}-G)={\bm{F}}^{-1}vec({\bm{D}})$ with ${\bm{F}},{\bm{D}}$ defined
there. Here ${\bm{F}}\in\mathbb{R}^{rq\times rq}$ and
${\bm{D}}\in\mathbb{R}^{r\times q}$. Thus,

$\|\bm{B}-\bm{G}\|_{F}=\|vec(\bm{B}-\bm{G})\|=\|{\bm{F}}^{-1}vec({\bm{D}})\|\leq\|{\bm{F}}^{-1}\|\cdot\|vec({\bm{D}})\|=\|{\bm{F}}^{-1}\|\cdot\|{\bm{D}}\|_{F}\leq\|{\bm{F}}^{-1}\|\cdot\sqrt{r}\|{\bm{D}}\|,$
(9)

By the matrix-Bernstein inequality,
$\|{\bm{U}}_{k}^{\intercal}{\bm{U}}_{k}-p\bm{I}\|\leq\epsilon
p,\,\,\,\text{w.p. greater than {$1-\exp(\log
2r-c\frac{\epsilon^{2}pn}{\mu_{u}^{2}r})$.}}$ Applying the union bound over
all $q$ diagonal blocks, and using the fact that
$\sigma_{\min}({\bm{F}})=\min_{k}\sigma_{\min}({\bm{U}}_{k}^{\intercal}{\bm{U}}_{k}))$
(since ${\bm{F}}$ is block diagonal),

$\|{\bm{F}}^{-1}\|\leq\frac{1}{(1-\epsilon)p},\,\,\,\text{ w.p. greater than
$1-\exp(\log q+\log 2r-c\frac{\epsilon^{2}pn}{\mu_{u}^{2}r})$.}$ (10)

(the above also follows by Lemma C.7 of [3]).

Using the above bound and the bound on $\|{\bm{D}}\|$ that we derive below

$\|\bm{B}-\bm{G}\|_{F}\leq\sqrt{r}\|{\bm{F}}^{-1}\|\|{\bm{D}}\|\leq
2\epsilon\sqrt{r}\delta{\sigma_{\max}^{*}},\,\,\,\text{w.p. greater than
$1-\exp(\log q-\frac{\epsilon^{2}pn}{r\mu_{u}^{2}})$}.$ (11)

Let $\epsilon=\epsilon_{1}/2\sqrt{r}$. Then,

$\|\bm{B}-\bm{G}\|_{F}\leq\|{\bm{F}}^{-1}\|\cdot\sqrt{r}\|{\bm{D}}\|\leq\epsilon_{1}\delta{\sigma_{\max}^{*}},\,\,\,\text{w.p.
greater than $1-\exp(\log q-\frac{\epsilon^{2}pn}{r^{2}\mu_{u}^{2}})$}.$ (12)

####  V-B1 $\|D\|$ bound

Let

$\bm{M}:=[(\bm{I}-{\bm{U}}{\bm{U}}^{\intercal}){\bm{U}}^{\star}{}]$

Recall from Sec. IV-A that

${\bm{D}}=\sum_{k}\bm{d}_{k}\bm{e}_{k}^{\intercal}={\bm{U}}^{\intercal}\bm{S}_{k}\bm{M}\bm{b}^{\star}_{k}\bm{e}_{k}^{\intercal}=\sum_{k}\sum_{j}\underbrace{\xi_{jk}\bm{u}^{j}\bm{M}^{j}{}^{\intercal}\bm{b}^{\star}_{k}\bm{e}_{k}^{\intercal}}_{{\bm{{Z}}}_{jk}}\text{
and }\mathbb{E}[{\bm{D}}]=\bm{0}$ (13)

We bound $\|{\bm{D}}\|=\|{\bm{D}}-\mathbb{E}[{\bm{D}}]\|$ using matrix
Bernstein inequality. Using $n\leq q$,

$\displaystyle
L=\max_{jk}\|\xi_{jk}\bm{u}_{j}\bm{M}^{j}{}^{\intercal}\bm{b}^{\star}_{k}\bm{e}_{k}^{\intercal}\|\leq\max_{jk}\|\bm{M}^{j}\|\|\bm{u}_{j}\|\|\bm{b}^{\star}_{k}\|\leq\delta{\sigma_{\max}^{*}}\mu\mu_{u}{r}/{n}$

where we used $\|\bm{M}^{j}\|\leq\|\bm{M}\|\leq\delta$. Also, using
$\mathbb{E}[\xi_{jk}]=\mathbb{E}[\xi_{jk}^{2}]=p$,

$\displaystyle\sigma_{1}^{2}$
$\displaystyle=\|\mathbb{E}[\sum_{jk}{\bm{{Z}}}_{jk}^{\intercal}{\bm{{Z}}}_{jk}]\|=p\|\sum_{jk}(\bm{M}^{j}{}^{\intercal}\bm{b}^{\star}_{k})^{2}\|\bm{u}_{j}\|^{2}\bm{e}_{k}\bm{e}_{k}^{\intercal}\|$
$\displaystyle\leq p\mu_{u}^{2}\frac{r}{n}\|\bm{M}\bm{B}^{*}\|_{F}^{2}\leq
2p\mu_{u}^{2}\frac{r}{n}\|\bm{M}\|_{F}^{2}\|\bm{B}^{*}\|^{2}\leq
2p\mu_{u}^{2}\frac{r}{n}\delta^{2}{\sigma_{\max}^{*2}}.$

and, proceeding in a very similar fashion,

$\displaystyle\sigma_{2}^{2}$
$\displaystyle=\|\mathbb{E}[\sum_{jk}{\bm{{Z}}}_{jk}{\bm{{Z}}}_{jk}^{\intercal}]\|=p\|\sum_{jk}(\bm{M}^{j}{}^{\intercal}\bm{b}^{\star}_{k})^{2}\bm{u}_{j}\bm{u}_{j}^{\intercal}\|$
$\displaystyle\leq p\mu_{u}^{2}\frac{r}{n}\|\bm{M}\bm{B}^{*}\|_{F}^{2}\leq
2p\mu_{u}^{2}\frac{r}{n}\|\bm{M}\|_{F}^{2}\|\bm{B}^{*}\|^{2}\leq
2p\mu_{u}^{2}\frac{r}{n}\delta^{2}{\sigma_{\max}^{*2}}.$

Thus, $\sigma^{2}=\max(\sigma_{1}^{2},\sigma_{2}^{2})=\sigma_{2}^{2}$, for
$r<q$. Setting $t=\epsilon p\text{{$\delta$}}{\sigma_{\max}^{*}}$, we have

$\frac{t}{L}=\frac{\epsilon
pn}{r\mu\mu_{u}},\,\,\,\frac{t^{2}}{\sigma^{2}}=\frac{\epsilon^{2}pn}{2r\mu_{u}^{2}}.$
(14)

Thus, by the Matrix-Bernstein inequality, and using $\mu\leq\mu_{u}$,

$\|{\bm{D}}\|=\|{\bm{D}}-\mathbb{E}[{\bm{D}}]\|\leq\epsilon
p\text{{$\delta$}}{\sigma_{\max}^{*}},\text{w.p. greater than }1-\exp(\log
q-c\frac{\epsilon^{2}pn}{r\mu_{u}^{2}}).$ (15)

###  V-C Proof of Lemma 4.3

Let $\delta=\delta^{(t-1)}$. Writing
${\bm{X}}^{\star}={\bm{U}}\bm{G}+(\bm{I}-{\bm{U}}{\bm{U}}^{\intercal}){\bm{X}}^{\star}$,
and ${\bm{X}}={\bm{U}}\bm{B}$, we have
$\|{\bm{X}}^{\star}-{\bm{X}}\|_{F}\leq\|\bm{B}-\bm{G}\|_{F}+\|(\bm{I}-{\bm{U}}{\bm{U}}^{\intercal}){\bm{U}}^{*}\bm{B}^{*}\|_{F}\leq\|\bm{B}-\bm{G}\|_{F}+\|(\bm{I}-{\bm{U}}{\bm{U}}^{\intercal}){\bm{U}}^{*}\|_{F}\|\bm{B}^{*}\|\leq
c\delta{\sigma_{\max}^{*}}+\delta{\sigma_{\max}^{*}}.$ For ii), using the
bound on $\|\bm{B}-\bm{G}\|_{F}$,
$\|\bm{B}\|=\|\bm{B}-\bm{G}+\bm{G}\|\leq\|\bm{B}-\bm{G}\|+\|\bm{G}\|\leq\delta{\sigma_{\max}^{*}}+{\sigma_{\max}^{*}}.$
For iii),
$\sigma_{\min}(\bm{B})\geq\sigma_{\min}(\bm{G})-\sigma_{\max}(\bm{B}-\bm{G})\geq\sqrt{1-\delta^{2}}{\sigma_{\min}^{*}}-\delta\sqrt{r}{\sigma_{\max}^{*}}$.
Here we used
$\sigma_{\min}(\bm{G})=\sigma_{\min}({\bm{U}}^{\intercal}{\bm{U}}^{\star}{}{\bm{B}^{\star}})\geq\sigma_{\min}({\bm{U}}^{\intercal}{\bm{U}}^{*}){\sigma_{\min}^{*}}\geq\sqrt{1-\delta^{2}}{\sigma_{\min}^{*}}.$

###  V-D Proof of Lemma 4.4

Since
$\bm{b}_{k}=({\bm{U}}_{k}^{\intercal}{\bm{U}}_{k})^{-1}{\bm{U}}_{k}^{\intercal}{\bm{U}}^{\star}{}_{k}\bm{b}^{\star}_{k}$,

$\|\bm{b}_{k}\|\leq\|({\bm{U}}_{k}^{\intercal}{\bm{U}}_{k})^{-1}\|\cdot\|{\bm{U}}_{k}^{\intercal}{\bm{U}}^{\star}{}_{k}\|\cdot\|\bm{b}^{\star}_{k}\|$

By Lemma C.6 of [3]:

$\|({\bm{U}}_{k}^{\intercal}{\bm{U}}_{k})^{-1}\|\leq\frac{1}{(1-\epsilon)p}\
\text{ w.p. at least }1-\exp(\log r-\epsilon^{2}pn/\mu_{u}^{2}r)$ (16)

To bound $\|{\bm{U}}_{k}^{\intercal}{\bm{U}}^{\star}{}_{k}\|$, first note that

$\mathbb{E}[{\bm{U}}_{k}^{\intercal}{\bm{U}}^{\star}{}_{k}]=p{\bm{U}}^{\intercal}{\bm{U}}^{\star}{}.$

Next we bound
$\|{\bm{U}}_{k}^{\intercal}{\bm{U}}^{\star}{}_{k}-p{\bm{U}}^{\intercal}{\bm{U}}^{\star}{}\|$
using matrix Bernstein inequality. Recall the expression for
${\bm{U}}_{k}^{\intercal}{\bm{U}}^{\star}{}_{k}$ from Sec. IV-A. Let
${\bm{{Z}}}_{j}=(\xi_{jk}-p){\bm{u}^{j}}{\bm{u}^{*}{}^{j}}{}^{\intercal}$. As
done in earlier proofs, we can show that

$L=\max_{j}\|{\bm{{Z}}}_{j}\|\leq\mu\mu_{u}\sqrt{r/n},\ \text{ and}$
$\sigma^{2}=\max(\|\sum_{j}\mathbb{E}[{\bm{{Z}}}_{j}{\bm{{Z}}}_{j}^{\intercal}]\|,\|\sum_{j}\mathbb{E}[{\bm{{Z}}}_{j}^{\intercal}{\bm{{Z}}}_{j}]\|)\leq
2p\mu_{u}^{2}\frac{r}{n}.$

For this, we used the fact that $\mathbb{E}[(\xi_{jk}-p)^{2}]=2p(1-p)\leq 2p$,
$\|\sum_{j}\|\bm{u}^{*}{}_{j}\|^{2}\bm{u}_{j}\bm{u}_{j}^{\intercal}\|\leq\mu^{2}(r/n)\|{\bm{U}}\|=\mu^{2}(r/n)$
and
$\|\sum_{j}\|\bm{u}^{j}\|^{2}\bm{u}^{*}{}_{j}\bm{u}^{*}{}_{j}{}^{\intercal}\|\leq\mu_{u}^{2}(r/n)\|{\bm{U}}^{\star}{}\|=\mu_{u}^{2}(r/n)$
and $\mu\leq\mu_{u}$.

Thus, by matrix Bernstein,
$\|{\bm{U}}_{k}^{\intercal}{\bm{U}}^{\star}{}_{k}-p{\bm{U}}^{\intercal}{\bm{U}}^{*}\|\leq\epsilon
p$ w.p. at least $1-\exp(\log r-\epsilon^{2}pn/\mu_{u}^{2}r)$. Hence, with
this probability,

$\|{\bm{U}}_{k}^{\intercal}{\bm{U}}^{\star}{}_{k}\|\leq\|{\bm{U}}_{k}^{\intercal}{\bm{U}}^{\star}{}_{k}-{\bm{U}}^{\intercal}{\bm{U}}^{\star}{}\|+p\|{\bm{U}}^{\intercal}{\bm{U}}^{\star}{}\|\leq\epsilon
p+p=(1+\epsilon)p.$ (17)

Thus, letting $\epsilon=0.1$, w.p. at least $1-\exp(\log r-cpn/\mu_{u}^{2}r)$,
$\|\bm{b}_{k}\|\leq 1.1\|\bm{b}^{\star}_{k}\|\leq
1.1\mu\sqrt{r/q}{\sigma_{\max}^{*}}.$ Here we obtained a bound on
$||\bm{b}_{k}||$ for a given $k$. By union bound, the above bound holds for
all $k\in[q]$ w.p. at least $1-q\exp(\log r-cpn/\mu_{u}^{2}r)=1-\exp(\log
q+\log r-cpn/\mu_{u}^{2}r)$.

###  V-E Proof of Lemma 4.5

Let $\delta=\delta^{(t-1)}$. Recall that
$\mathrm{GradU}=\sum_{jk}\xi_{jk}\bm{e}_{j}(\bm{x}_{jk}-\bm{x}^{*}_{jk})\bm{b}_{k}^{\intercal}.$
Using the lemma assumption,
$\|\bm{B}-\bm{G}\|_{F}\leq\delta{\sigma_{\max}^{*}}$. Using this and Lemma
4.3, $\|{\bm{X}}-{\bm{X}}^{\star}\|_{F}\leq 2\delta{\sigma_{\max}^{*}}$,
$\|\bm{B}\|\leq 1.1{\sigma_{\max}^{*}}$, We use these bounds in the proof
below.

Observe that

$\mathbb{E}[\mathrm{GradU}]=p({\bm{X}}-{\bm{X}}^{\star})\bm{B}^{\intercal},$

Thus, using the assumed $\bm{B}-\bm{G}$ bound,

$\|\mathbb{E}[\mathrm{GradU}]\|_{F}\leq
p\|{\bm{X}}-{\bm{X}}^{\star}\|_{F}\|\bm{B}\|\leq
2.2p\delta{\sigma_{\max}^{*2}}$

Next we bound the deviation using matrix Bernstein inequality. Writing
${\bm{X}}={\bm{U}}\bm{B}$,
${\bm{X}}^{\star}={\bm{U}}\bm{G}+(\bm{I}-{\bm{U}}{\bm{U}}^{\intercal}){\bm{X}}^{\star}$,
and using $n\leq q$

$\displaystyle\max_{jk}|\bm{x}_{jk}-\bm{x}^{*}_{jk}|$
$\displaystyle=|\bm{e}_{j}^{\intercal}({\bm{X}}-{\bm{X}}^{\star})\bm{e}_{k}|$
$\displaystyle\leq\|\bm{e}_{j}^{\intercal}{\bm{U}}\|\|\bm{B}-\bm{G}\|+\|(\bm{I}-{\bm{U}}{\bm{U}}^{\intercal}){\bm{U}}^{\star}{}\|\|{\bm{B}^{\star}}\bm{e}_{k}\|$
$\displaystyle\leq\mu_{u}\sqrt{r/n}\delta{\sigma_{\max}^{*}}+\mu\sqrt{r/q}\delta{\sigma_{\max}^{*}}\leq
2\mu_{u}\sqrt{r/n}\delta{\sigma_{\max}^{*}}$

Using this,

$L=\max_{jk}\|(\bm{x}_{jk}-\bm{x}^{\star}_{jk})\bm{b}_{k}^{\intercal}\|\leq\max_{jk}\|(\bm{x}_{jk}-\bm{x}^{\star}_{jk})\|\max_{k}\|\bm{b}_{k}\|\leq
2\mu_{u}\sqrt{r/n}\delta{\sigma_{\max}^{*}}\cdot\mu\sqrt{r/q}{\sigma_{\max}^{*}}\leq
2\mu_{u}\mu(r/n)\delta{\sigma_{\max}^{*2}},$

To bound
$\sigma_{1}^{2}=\|\sum_{jk}\mathbb{E}[{\bm{{Z}}}_{jk}{\bm{{Z}}}_{jk}^{\intercal}]\|$
and
$\sigma_{2}^{2}=\|\sum_{jk}\mathbb{E}[{\bm{{Z}}}_{jk}^{\intercal}{\bm{{Z}}}_{jk}]\|$,
where
${\bm{{Z}}}_{jk}=\xi_{jk}\bm{e}_{j}(\bm{x}_{jk}-\bm{x}^{*}_{jk})\bm{b}_{k}^{\intercal}$,
using $\mathbb{E}[(\xi_{jk}-p)^{2}]=2p(1-p)\leq 2p$ we have

$\displaystyle\sigma_{1}^{2}=2p\|\sum_{jk}(\bm{x}_{jk}-\bm{x}^{\star}_{jk})^{2}\bm{e}_{j}\bm{b}_{k}^{\intercal}\bm{b}_{k}\bm{e}_{j}^{\intercal}\|\leq
2p\|\bm{b}_{k}\|^{2}\|{\bm{X}}-{\bm{X}}^{\star}\|_{F}^{2}\leq
2p\mu^{2}(r/q){\sigma_{\max}^{*2}}\cdot(\delta{\sigma_{\max}^{*}})^{2}=2p\mu^{2}(r/q)\delta^{2}\sigma^{*4}_{\max}.$
$\displaystyle\sigma_{2}^{2}=2p\|\sum_{jk}(\bm{x}_{jk}-\bm{x}^{\star}_{jk})^{2}\bm{e}_{j}^{\intercal}\bm{e}_{j}\bm{b}_{k}\bm{b}_{k}^{\intercal}\|\leq
2p\|\bm{b}_{k}\|^{2}\|{\bm{X}}-{\bm{X}}^{\star}\|_{F}^{2}=\sigma_{1}^{2}.$

Setting $t=\epsilon p\delta{\sigma_{\min}^{*2}}$, we have

$\frac{t^{2}}{\sigma^{2}}=c\frac{\epsilon^{2}p^{2}\delta^{2}{\sigma_{\min}^{*}}{}^{4}}{p\mu^{2}(r/q)\delta^{2}{\sigma_{\max}^{*4}}}=\frac{\epsilon^{2}pq}{\kappa^{4}\mu^{2}r},\
\ \frac{t}{L}=c\frac{\epsilon
p\delta{\sigma_{\min}^{*2}}}{\mu_{u}\mu(r/n)\delta{\sigma_{\max}^{*2}}}=\frac{\epsilon
pn}{\kappa^{2}\mu_{u}\mu r}.$

Thus,

$\min\left(\frac{t^{2}}{\sigma^{2}},\frac{t}{L}\right)=c\frac{\epsilon^{2}pn}{\max(\kappa^{4}\mu^{2},\kappa^{2}\mu_{u}\mu)r}$

and so, by matrix Bernstein, w.p. at least $1-\exp(\log
q-c\frac{\epsilon^{2}pn}{\max(\kappa^{4}\mu^{2},\kappa^{2}\mu_{u}\mu)r})$,
$\|\mathrm{GradU}-\mathbb{E}[\mathrm{GradU}]\|\leq\epsilon
p\delta{\sigma_{\min}^{*2}}.$

By setting $\epsilon=\epsilon_{1}/\sqrt{r}$,
$\|\mathrm{GradU}-\mathbb{E}[\mathrm{GradU}]\|_{F}\leq\sqrt{r}\|\mathrm{GradU}-\mathbb{E}[\mathrm{GradU}]\|\leq\epsilon_{1}p\delta{\sigma_{\min}^{*2}}$
w.p. at least $1-\exp(\log
q-\frac{\epsilon_{1}^{2}pn}{\max(\kappa^{4}\mu^{2},\kappa^{2}\mu_{u}\mu)r^{2}})$.

###  V-F Proof of Lemma 4.6

Let $\delta=\delta^{(t-1)}$. This is used only for proving the second part.

Recall from Sec. IV-A that

$\mathrm{Grad}{\bm{u}^{j}}=\sum_{k}\xi_{jk}(\bm{x}_{jk}-\bm{x}^{\star}_{jk})\bm{b}_{k}^{\intercal},$

To apply matrix Bernstein, we need to bound
$\sigma_{1}^{2}\equiv\|\mathbb{E}[\sum_{k}\xi_{jk}^{2}(\bm{x}_{jk}-\bm{x}^{*}_{jk})^{2}\bm{b}_{k}^{\intercal}\bm{b}_{k}]\|$,
$\sigma_{2}^{2}\equiv\|\mathbb{E}[\sum_{k}\xi_{jk}^{2}(\bm{x}_{jk}-\bm{x}^{*}_{jk})^{2}\bm{b}_{k}\bm{b}_{k}^{\intercal}]\|$,
and $L=\max_{k}\|(\bm{x}_{jk}-\bm{x}^{\star}_{jk})\bm{b}_{k}\|$. Using

$|\bm{x}_{jk}-\bm{x}^{\star}_{jk}|\leq
2\max(|\bm{x}_{jk}|,|\bm{x}^{\star}_{jk}|)\leq
2\max(\|{\bm{u}^{j}}\|\|\bm{b}_{k}\|,\|{\bm{u}^{*}{}{}^{j}}\|\|\bm{b}^{\star}_{k}\|)\leq
2\max(\|{\bm{u}^{j}}\|,\|{\bm{u}^{*}{}{}^{j}}\|)\max(\|\bm{b}_{k}\|,\|\bm{b}^{\star}_{k}\|).$

and $\max(\|\bm{b}^{\star}_{k}\|,\|\bm{b}_{k}\|)\leq
1.1\mu\sqrt{r/q}{\sigma_{\max}^{*}}$,

$\displaystyle
L\leq\max_{k}|\bm{x}_{jk}-\bm{x}^{\star}_{jk}|\max_{k}\|\bm{b}_{k}\|$
$\displaystyle\leq
2\max(\|{\bm{u}^{j}}\|,\|{\bm{u}^{*}{}{}^{j}}\|)\max_{k}\max(\|\bm{b}_{k}\|,\|\bm{b}^{\star}_{k}\|)\max_{k}\|\bm{b}_{k}\|$
$\displaystyle\leq
2\max(\|{\bm{u}^{j}}\|,\|{\bm{u}^{*}{}{}^{j}}\|)\mu^{2}(r/q){\sigma_{\max}^{*2}}.$
(18)

We use the above seemingly loose bound because we do not need $\delta^{(t-1)}$
in this bound. Instead we need to the bound to be of the form
$\max(\|\bm{u}^{j}\|,\|\bm{u}^{*}{}_{j}\|)$ times a factor of
$\sqrt{r/q}{\sigma_{\max}^{*}}$

The variance
$\sigma_{1}^{2}=\|\mathbb{E}[\sum_{k}\xi_{jk}(\bm{x}_{jk}-\bm{x}^{*}_{jk})^{2}\bm{b}_{k}^{\intercal}\bm{b}_{k}]\|$
can be bounded using similar ideas as follows.

$\displaystyle\sigma_{1}^{2}=\|\sum_{k}p(\bm{x}_{jk}-\bm{x}^{\star}_{jk})^{2}\bm{b}_{k}^{\intercal}\bm{b}_{k}\|$
$\displaystyle\leq
2p{\max(\|{\bm{u}^{j}}\|_{2},\|\bm{u}^{*}{}^{j}\|_{2})}^{2}\max_{k}(\|\bm{b}_{k}\|,\|\bm{b}^{*}_{k}\|)^{2}\sum_{k}\|\bm{b}_{k}\|_{2}^{2}$
$\displaystyle\leq
2p\max{(\|{\bm{u}^{j}}\|_{2},\|\bm{u}^{*}{}^{j}\|_{2})}^{2}\mu^{2}(r^{2}/q){\sigma_{\max}^{*4}}.$
(19)

Similarly, $\sigma_{2}^{2}\leq
2p\max{(\|{\bm{u}^{j}}\|_{2},\|\bm{u}^{*}{}^{j}\|_{2})}^{2}\mu^{2}(r^{2}/q){\sigma_{\max}^{*4}}.$
By the matrix Bernstein inequality with $t=\epsilon
p\max(\|{\bm{u}^{j}}\|,\|{\bm{u}^{*j}}\|){\sigma_{\min}^{*2}}$, and noting
that $\sigma^{2}=\max(\sigma_{1}^{2},\sigma_{2}^{2})=\sigma_{1}^{2}$, we have
w.p. at least $1-\exp(\log q-\epsilon^{2}pn/\mu^{2}\kappa^{4}r^{2})$,

$\|\mathbb{E}[\mathrm{Grad}{\bm{u}^{j}}]-\mathrm{Grad}{\bm{u}^{j}}\|\leq\epsilon
p\max(\|{\bm{u}^{j}}\|,\|{\bm{u}^{*}{}{}^{j}}\|){\sigma_{\min}^{*2}}.$ (20)

This completes the proof for the first part of the lemma.

####  V-F1 Proof of second part

In line 7 of Algorithm 1, adding/subtracting
$\mathbb{E}[\mathrm{Grad}{\bm{u}^{j}}]=p(\bm{u}^{j}{}\bm{B}\bm{B}^{\intercal}-{\bm{u}^{*}{}{}^{j}}{\bm{B}^{\star}}\bm{B}^{\intercal})$,

$\tilde{\bm{u}}^{j}{}^{+}=\bm{u}^{j}{}-\eta\mathrm{Grad}{\bm{u}^{j}}=\bm{u}^{j}{}(\bm{I}-\eta
p\bm{B}\bm{B}^{\intercal})+\eta
p{\bm{u}^{*}{}{}^{j}}{\bm{B}^{\star}}\bm{B}^{\intercal}+\eta(\mathbb{E}[\mathrm{Grad}{\bm{u}^{j}}]-\mathrm{Grad}{\bm{u}^{j}}),$
(21)

Since we assumed $\delta\leq c/\kappa$, by Lemma 4.3,
$\sigma_{\min}(\bm{B})\geq 0.9{\sigma_{\min}^{*}}$ and
$\sigma_{\max}(\bm{B})\leq 1.1{\sigma_{\max}^{*}}$. Thus, if
$\eta<0.5/p{\sigma_{\max}^{*2}}$ then, $\bm{I}-\eta p\bm{B}\bm{B}^{\intercal}$
is positive semi-definite (psd) and so $\|\bm{I}-\eta
p\bm{B}\bm{B}^{\intercal}\|=\lambda_{\max}(\bm{I}-\eta
p\bm{B}\bm{B}^{\intercal})=1-\eta p\sigma_{\min}^{2}(\bm{B})\leq 1-0.9\eta
p{\sigma_{\min}^{*}}^{2}$.

Thus, using the above bound on
$\|\mathbb{E}[\mathrm{Grad}{\bm{u}^{j}}]-\mathrm{Grad}{\bm{u}^{j}}\|$, if
$\eta<0.5/p{\sigma_{\max}^{*2}}$,

$\displaystyle\|\tilde{\bm{u}}^{j}{}^{+}\|$
$\displaystyle\leq\|{\bm{u}^{j}{}}\|(1-0.9\eta p{\sigma_{\min}^{*2}})+\eta
p\|{\bm{u}^{*}{}{}^{j}}\|{\sigma_{\max}^{*2}}+\epsilon\eta
p{\sigma_{\min}^{*2}}\max(\|{\bm{u}^{j}{}}\|,\|{\bm{u}^{*j}}\|)$
$\displaystyle\leq(1-(0.9-\epsilon)\eta
p{\sigma_{\min}^{*2}})\max(\|{\bm{u}^{j}{}}\|,\|{\bm{u}^{*j}}\|)+\eta
p{\sigma_{\max}^{*2}}\|{\bm{u}^{*}{}{}^{j}}\|,$ (22)

w.p. at least $1-\exp(\log q-\epsilon^{2}pn/\mu^{2}\kappa^{4}r^{2})$. We bound
$\|\bm{u}^{j(t+1)}\|\leq\|({\bm{R}}^{+})^{-1}\|\cdot\|\tilde{\bm{u}}^{j(t+1)}\|$,
where $\tilde{\bm{U}}^{+}\overset{\text{QR}}{=}{\bm{U}}^{+}{\bm{R}}^{+}$ next.
Using Lemma 4.5,

$\|({\bm{R}}^{+})^{-1}\|=\frac{1}{\sigma_{\min}({\bm{U}}-\eta\|\mathrm{GradU}\|)}\leq\frac{1}{1-\eta
2.1p\delta{\sigma_{\max}^{*2}}}\leq\frac{1}{1-0.25\eta
p{\sigma_{\max}^{*2}}}\leq 1+0.5\eta p{\sigma_{\max}^{*2}}.$ (23)

w.p. given in Lemma 4.5. Thus, using (22) and (23) in
$\|{\bm{u}^{j}}^{+}\|\leq\|({\bm{R}}^{+})^{-1}\|\cdot\|\tilde{\bm{u}}^{j(t+1)}\|$,

$\displaystyle\|\bm{u}^{j}{}^{+}\|$ $\displaystyle\leq(1+0.5\eta
p{\sigma_{\max}^{*2}})(1-(0.9-\epsilon)\eta
p{\sigma_{\min}^{*2}})\max(\|{\bm{u}^{j}{}}\|\|{\bm{u}^{*j}}\|)+(1+0.5\eta
p{\sigma_{\min}^{*2}})\eta p{\sigma_{\max}^{*2}}\|{\bm{u}^{*}{}{}^{j}}\|$
$\displaystyle\leq(1-(0.4-\epsilon)\eta
p{\sigma_{\min}^{*2}})\max(\|{\bm{u}^{j}{}}\|,\|{\bm{u}^{*j}}\|)+(1+0.5\eta
p{\sigma_{\max}^{*2}})\eta p{\sigma_{\max}^{*2}}\|{\bm{u}^{*}{}{}^{j}}\|$
$\displaystyle\leq(1-(0.4-\epsilon)\eta
p{\sigma_{\min}^{*2}})\max(\|{\bm{u}^{j}{}}\|,\|{\bm{u}^{*j}}\|)+(1+0.25/\kappa^{2})0.5\|{\bm{u}^{*}{}{}^{j}}\|$
$\displaystyle\leq(1-\frac{0.15}{\kappa^{2}})\max(\|{\bm{u}^{j}{}}\|,\|{\bm{u}^{*j}}\|)+0.7\|{\bm{u}^{*}{}{}^{j}}\|$

where the last bound follows by setting $\eta=0.5/p{\sigma_{\max}^{*2}}$ and
setting $\epsilon=0.1$ in (20). Thus, we have shown that if
$\eta=0.5/p{\sigma_{\max}^{*2}}$, and if $\delta\leq c/\kappa^{2}$, with
probability exceeding $1-4/n^{3}$,

$\displaystyle\|{\bm{u}^{j}}^{+}\|$
$\displaystyle\leq(1-\frac{0.15}{\kappa^{2}})\max(\|{\bm{u}^{j}{}}\|,\|\bm{u}^{*}{}{}^{j}\|)+0.7\|{\bm{u}^{*}{}{}^{j}}\|$
$\displaystyle\leq(1-\frac{0.15}{\kappa^{2}})\|\bm{u}^{j}{}\|+2\|\bm{u}^{*}{}{}^{j}\|.$

##  VI Guarantee for Noisy LRMC

Consider the noisy LRMC problem defined as follows. We observe

$\bm{Y}:={\bm{X}}^{\star}_{\Omega}+{\bm{W}}_{\Omega}$

We do not make any assumption on the noise ${\bm{W}}$ (deterministic
${\bm{W}}$). Unlike the standard Gaussian assumption, this assumption is
weaker: it allows the noise entries to be anything, all entries could be
positive too for example.

We can show the following by borrowing the overall proof approach for
modifying a noise-free case guarantee for an iterative algorithm from past
works [30, 25] (the latter used a similar approach for analyzing the AltMin
algorithm for LR phase retrieval).

######  Corollary 6.1.

Let

$\epsilon_{noise}:=\max_{jk}\frac{\lvert w_{jk}\rvert}{\lvert
x^{*}_{jk}\rvert}$

In the setting of Theorem 2.1, if
$\epsilon_{noise}\leq\frac{c}{\sqrt{r}\kappa^{3}},$ then, by setting
$T=C\kappa^{2}\log(1/\epsilon_{noise})$, we can guarantee that

$\mathrm{SD}_{F}({\bm{U}}^{(T)},{\bm{U}}^{\star}{})\leq\kappa^{2}\sqrt{r}\epsilon_{noise}$

$\ \text{ and }\
\|{\bm{X}}^{(T)}-{\bm{X}}^{\star}\|_{F}\leq\mathrm{SD}_{F}({\bm{U}}^{(T)},{\bm{U}}^{\star}{}){\sigma_{\max}^{*}}.$
In general, for any $\epsilon$, by setting $T=C\kappa^{2}\log(1/\epsilon)$, we
can ensure that

$\mathrm{SD}_{F}({\bm{U}}^{(T)},{\bm{U}}^{\star}{})\leq\max(\epsilon,\kappa^{2}\sqrt{r}\epsilon_{noise})$

and
$\|{\bm{X}}-{\bm{X}}^{\star}\|_{F}\leq\mathrm{SD}_{F}({\bm{U}}^{(T)},{\bm{U}}^{\star}{}){\sigma_{\max}^{*}}$.

###### Proof.

Corollary 6.1 extends our noise-free case proof to the noisy case using the
following simple ideas. First we assume that the noise level is small enough
so that accurate initialization is possible; this requires noise level,
$\epsilon_{noise}\sqrt{r}$, to be of order $c\delta^{(0)}{\sigma_{\min}^{*}}$
for our required value of $\delta^{(0)}=c/\kappa^{2}$. This helps ensure that
the initialization error is bounded by $\delta^{(0)}$.

Next, at each iteration, we attempt to bound terms and prove incoherence for
the updated ${\bm{U}},\bm{B}$, in order to guarantee error decay similar to
the noise-free case. For this, we need the noise level to be such that (i) the
error in recovering ${\bm{B}^{\star}}$ is of the same order as in the noise-
free case; and (ii) the same is true for the bounds on the gradient norm. Both
of these are ensured if $\epsilon_{noise}\kappa^{2}\sqrt{r}\leq
c\delta^{(t-1)}$ for a $c<1$, e.g., $c=0.1$. Details are given in Appendix A.
∎

##  VII Improved Guarantees for AltMin and Smooth-AltMin

Using the same lemmas used to prove the AltGDmin guarantee, we are also able
to improve the guarantee for AltMin and Smooth-AltMin [12], as long as both
are initialized as given in Algorithm 1: the initial estimate of ${\bm{U}}$ is
clipped using row-wise clipping. We borrow this clipping idea from [11].

###  VII-A Improving the result for AltMin

######  Corollary 7.1 (Improved AltMin [3] Guarantee).

Consider the AltMin algorithm initialized using our initialization (lines 2-4)
of Algorithm 1. Assume that Assumption 1.1 holds and that, at each iteration
$t$, entries of ${\bm{X}}^{\star}$ are observed independently with probability
$p$ satisfying

$np>C\kappa^{4}\mu^{2}r^{2}\log q.$ (24)

Then, w.p. at least $1-3/n^{3}$, the iterates ${\bm{U}}^{(t)}$ of AltMin [3]
satisfy $\mathrm{SD}_{F}({\bm{U}}^{(t+1)},{\bm{U}}^{\star}{})\leq
0.25\mathrm{SD}_{F}({\bm{U}}^{(t)},{\bm{U}}^{*}).$

Consequently, if $p_{tot}>\frac{C\kappa^{4}\mu^{2}r^{2}\log
q}{n}\log({1}/{\epsilon})$, then, after $T=C\log(1/\epsilon)$ iterations,
$\mathrm{SD}_{F}({\bm{U}}^{(T)},{\bm{U}}^{\star}{})\leq\epsilon$.

We prove this in Appendix B. The proof is an easy corollary of Lemmas 4.1,
4.2, 4.3 and 4.4. Comparing (24) to Theorem 2.5 of [3], we observe that the
sample complexity for AltMinComplete has reduced in $r$ from $r^{4.5}\log r$
to $r^{2}$.

###  VII-B Improved Guarantee for Smooth AltMin [12]

We will reduce the overall sample complexity by decreasing $p_{init}$ to
$O(r^{2})$ below. Formally,

######  Corollary 7.2.

Let $r,\epsilon>0$. Let ${\bm{X}}^{\star}$ be a symmetric $n\times n$ matrix.
Then, for $T=O(\log(n/\epsilon))$, the output of SAltLS satisfies
$\mathrm{SD}_{F}({\bm{U}},{\bm{U}}^{*})\leq\epsilon$ with probability $9/10$,
provided that sampling probability $p\geq p_{init}+p_{LS}$, where

$p_{\mathrm{init}}\geq C{\kappa^{2}r^{2}\mu\log n}/{n},\quad
p_{\mathrm{LS}}\geq C{\mu^{2}\kappa^{2}r^{2}\log(n/\epsilon)\log^{2}n}/{n}.$
(25)

This is a direct corollary of Theorem 6.1 of [12] combined with our
initialization lemma, Lemma 4.1.

##  VIII Simulation Results

(a) Federated, $r=10$.

(b) Error against iterations, $r=10$.

(c) Federated, $r=20$.

(d) Error against iterations, $r=20$.

Figure 1: Figures (a),(c) compare federated implementations of AltGDmin
(proposed), FactGD and AltMin. The results match what our theory (sufficient
conditions) predicts. AltGDmin is the fastest due to its lowest communication-
efficiency and due to all three having comparable computation cost. Figures
(b), (d) compare iteration complexity numerically. The results match theory
once again. Two versions of AltMin are compared: AltMin (Fed/Not-Prvt) uses
exact LS solution for updating both $\bm{B}$ and ${\bm{U}}$. AltMin (Fed/Prvt)
uses multiple gradient descent iterations to solve the LS problem for updating
${\bm{U}}$. In (a), we also compare FactGD with three choices of step size.
See experiments’ description for details.

####  VIII-1 Experimental Setup

We plot averaged subspace distance at the iteration $t$ against the average
time taken until iteration $t$, with the averages being computed over 100
Monte Carlo runs. The averaging is over the observed entries which are
generated uniformly at random. The matrix
${\bm{X}}^{\star}={\bm{U}}^{\star}{}{\bm{B}^{\star}}$ was generated once: we
let ${\bm{U}}^{\star}{}$ be an orthonormalized $n\times r$ random Gaussian
matrix and ${\bm{B}^{\star}}$ an $r\times q$ random Gaussian matrix. We used
the ‘parfor’ loop in MATLAB to distribute the computation across 10 workers,
with each worker being an individual core of a multi-core CPU (13-th Gen.
Intel Core i7 with 32GB RAM and 16 cores). To compute the left-singular
vectors needed for the initialization of federated algorithms, we used the
federated power method and performed 15 power iterations. Also, for both
AltMin and AltGDMin, we do not sample-split, i.e., we run each iteration of
the algorithms on all observed entries.

####  VIII-2 Step-size and other parameters

For FactGD (Centralized), we used the code provided by the authors of that
work [11]. The step size was set $\eta_{\text{FactGD}}=pc/\lVert\bm{Y}\rVert$,
as also done in the authors’ own implementation of their algorithm. Setting
$c=0.75$ showed the fastest convergence for our simulations (see Fig. 1(a)).
For AltMin (Fed./NotPrvt.) and AltMin(Fed./Prvt.), we wrote our own MATLAB
implementation; the latter uses GD to solve the LS problem for updating
${\bm{U}}$. We set the number of GD iterations for solving each LS problem to
10 with step size $\eta=p/\|\bm{Y}\|^{2}$, which showed the fastest
convergence. Note that the ${\bm{U}}$-update least-squares problem is convex,
and the chosen step-size is an upper bound on the Lipschitz constant of the
expected gradient of the objective function at $t=0$ [31]. AltGDMin is also
implemented with step-size $\eta=p/\|\bm{Y}\|^{2}$, which approximates the
step size choice suggested by Theorem 2.1, since
$||\mathbb{E}[\bm{Y}]||^{2}=p^{2}{\sigma_{\max}^{*2}}$. AltMin and AltGDMin
were both initialized by lines 2-4 of Algorithm 1. The incoherence parameter
$\mu$ was estimated as
$\hat{\mu}=\operatorname*{\mathrm{argmin}}_{\mu}\rVert\bm{u}^{(0)j}\rVert\leq\mu\sqrt{r/n}\,\text{
for all }j\in[n]$.

####  VIII-3 Observations

Federated algorithms are faster than their centralized counterparts, except
AltMin (Fed. Prvt.). The proposed algorithm AltGDMin (Fed.) is faster than all
benchmark methods, especially at the higher value of $r=20$. Specifically,
AltGDMin (Fed.) converges to ${\bm{U}}^{\star}{}$ in approximately 12 seconds,
compared to nearly 20 seconds for the second fastest AltMin (Fed. NotPrvt.).
We interpret/explain these observations and the benchmark methods below.

####  VIII-4 AltGDMin

AltGDMin (Fed.) has faster convergence because of low communication complexity
and low time complexity at the center. The upstream communication complexity,
$\min(\sum_{k\in\bm{S}_{\ell}}\nabla_{{\bm{U}}}f({\bm{U}},\bm{b}_{k}),nr)=nr$,
is low because the nodes sum the column-wise gradients

####  VIII-5 FactGD

$\nabla_{{\bm{U}}}f=\nabla_{{\bm{X}}}\bm{B}^{\intercal}\in\mathbb{R}^{n\times
r}$ and $\bm{B}\bm{B}^{\intercal}\in\mathbb{R}^{r\times r}$ are computed at
the nodes and transmitted upstream. The total upstream communication cost is
$nr+r^{2}$, higher than the $nr$ communication cost of AltGDMin. $\bm{B}$ is
updated locally (GD iteration and normalizing) at the nodes but this requires
two data exchanges with the center. This is because the gradient of $\bm{B}$,
$(\bm{B}\bm{B}^{\intercal}-{\bm{U}}^{\intercal}{\bm{U}})\bm{B}$, with respect
to the norm balancing term,
$\lVert{\bm{U}}^{\intercal}{\bm{U}}-\bm{B}\bm{B}^{\intercal}\rVert_{F}^{2}$,
cannot be computed at the nodes. The nodes compute and transmit
$\sum_{k\in\mathcal{S}_{\ell}}\bm{b}_{k}\bm{b}_{k}^{\intercal}$, which are
summed at the center to form $\bm{B}\bm{B}^{\intercal}$, and transmitted back
to the nodes. The center also computes and transmits
${\bm{U}}^{\intercal}{\bm{U}}$. Then, at the nodes, the partial gradient
$(\bm{B}\bm{B}^{\intercal}-{\bm{U}}^{\intercal}{\bm{U}})\sum_{k\in\mathcal{S}_{\ell}}\bm{b}_{k}\bm{b}_{k}^{\intercal}$
is computed, followed by column-normalizing. The federated and centralized
implementations of FactGD do not use ‘for’ loops at all, either at the nodes
or at the center. But, FactGD is slower than AltMin and AltGDMin because of
its higher communication complexity, $O(nr+r^{2})$ and 2 data exchanges,
compared to 1 data exchange and $O(nr)$, $O(qr)$ communication complexity for
AltGDMin and AltMin (Fed.NotPrvt.), respectively.

####  VIII-6 AltMin

AltMin (Fed./NotPrvt.) is slower than AltGDMin (Fed.) because the $n$
${\bm{U}}$-update LS problems are solved sequentially at the center with
complexity $\lvert\Omega\rvert r^{2}$, compared to the $nr^{2}$ complexity of
computing the QR decomposition for AltGDMin. Also, AltMin (Fed./NotPrvt.) is
not private because the nodes communicate the updated $\bm{b}_{k}^{(t+1)}$ to
the center. For AltMin(Fed./Prvt.), the ${\bm{U}}$-update LS problems are
solved by multiple gradient descent iterations at the node. While private, the
GD version of AltMin is slow because of the communication overhead of
transmitting/receiving the gradients several times ($\log(1/\epsilon)$ times
for $\epsilon$-accuracy) in each iteration. AltMin (Cntrl.) is slower than
federated methods because both ${\bm{U}}$, $\bm{B}$ LS problems are solved
sequentially by the closed form solution at the center, but it is still the
fastest centralized algorithm overall, possibly because of $\log(1/\epsilon)$
iteration complexity, which is lower than that of other methods.

##  IX Conclusions

In this work we developed and analyzed the Alternating GD and Minimization
(AltGDmin) algorithm for solving the low rank matrix completion (LRMC)
problem. The design of AltGDmin is motivated by a federated setting. Using our
results (sample and iteration complexity bounds) we argued that, in a
federated setting, AltGDmin is the most communication-efficient solution. It
is also one of the two fastest private solutions and has the second smallest
sample complexity. In addition, we were able to use our lemmas to prove an
improved sample complexity guarantee for AltMin, which is the fastest
centralized solution for LRMC.

##  Appendix A Proof of the Corollary 6.1 (noisy LRMC)

We can prove the following by directly modifying the noise-free case proof.

######  Claim A.1.

Let the observed matrix $\bm{Y}={\bm{X}}^{*}_{\Omega}+{\bm{W}}_{\Omega}$ be
corrupted by additive noise ${\bm{W}}$ such that
$\lvert{\bm{W}}_{jk}\rvert\leq\epsilon_{noise}\lvert{\bm{X}}^{*}_{jk}\rvert$.
Assuming also that $p\geq C\kappa^{6}r^{2}\mu\log q\log(1/\epsilon)/n$ and
$\epsilon_{noise}\leq 1/(\sqrt{r}\kappa^{3})$, then, after
$T=\kappa^{2}\log(1/\epsilon_{noise})$ iterations,
$\mathrm{SD}_{F}({\bm{U}}^{(T)},{\bm{U}}^{*})\leq\kappa^{2}\epsilon_{noise}\sqrt{r}$.

###  A-A Proof

Restricting $\epsilon_{noise}\leq 1/(\sqrt{r}\kappa^{3})$ (as done in the
statement of Theorem A.1) ensures that the initialization bound in Lemma 4.1
differs only by a constant factor (see Lemma A.2).

With noise ${\bm{W}}_{\Omega}$, the Least-Squares update (4) changes to

$\bm{b}_{k}-\bm{g}_{k}={\bm{F}}_{k}^{-1}(\bm{d}_{k}+{\bm{U}}_{k}^{\intercal}\bm{w}_{k}),\text{
for all }k\in[q],$

where $\bm{w}_{k}$ is the $k$-th column of ${\bm{W}}_{\Omega}$. Consequently,
the bound in (9) changes to
$\|\bm{B}-\bm{G}\|_{F}\leq\|{\bm{F}}^{-1}\|(\|{\bm{D}}\|_{F}+\lVert{\bm{W}}_{\bm{B}}\rVert_{F})$,
where ${\bm{W}}_{B}=\sum_{k}{\bm{U}}_{k}^{\top}\bm{w}_{k}\bm{e}_{k}^{\top}$.
In Lemma A.3, we bound $\lVert{\bm{W}}_{\bm{B}}\rVert_{F}\leq
2\sqrt{r}\epsilon_{noise}p{\sigma_{\max}^{*}}$, ensuring that
$\|\bm{B}-\bm{G}\|_{F}\leq\max(\delta^{(t-1)},2\sqrt{r}\epsilon_{noise}){\sigma_{\max}^{*}}$.
Assuming $2\sqrt{r}\epsilon_{noise}\leq\delta^{(t-1)}$, Lemmas 4.2 and 4.3
continue to hold. Because $\lVert{\bm{U}}_{k}^{\intercal}\bm{w}_{k}\rVert\leq
2\epsilon_{noise}p\lVert\bm{b}_{k}^{*}\rVert_{2}$ (Lemma A.3),
$\lVert({\bm{U}}_{k}^{\intercal}{\bm{U}}_{k})^{-1}{\bm{U}}_{k}^{\intercal}\bm{w}_{k}\rVert_{2}\leq
2\epsilon_{noise}\lVert\bm{b}^{*}_{k}\rVert_{2}$, which, together with
$\lVert\bm{b}_{k}\rVert_{2}\leq 1.1{\sigma_{\max}^{*}}\mu\sqrt{r/q}$ (Lemma
4.4), bounds the noisy least-squares update
$\lVert\tilde{\bm{b}}_{k}\rVert_{2}\leq(1.1+2\epsilon_{noise})\mu{\sigma_{\max}^{*}}\sqrt{r/q}$,
thereby proving $\mu$-incoherence in the noisy setting.

With noise, the gradient is
$\stackrel{{\scriptstyle\sim}}{{\smash{\mathrm{GradU}}\rule{0.0pt}{4.34857pt}}}=\mathrm{GradU}-{\bm{W}}_{{\bm{U}}}$,
where ${\bm{W}}_{\bm{U}}={\bm{W}}_{\Omega}\bm{B}^{\intercal}$. We bound
$\lVert{\bm{W}}_{{\bm{U}}}\rVert_{F}\leq
2\epsilon_{noise}\sqrt{r}p{\sigma_{\max}^{*2}}$ in Lemma A.3, and assume
$\epsilon_{noise}\leq\delta^{(t-1)}/\sqrt{r}$ so that the bound in Lemma 4.5
continues to hold. To prove row-incoherence in the noisy setting, the proof of
Lemma 4.6 needs to be only slightly modified. (20) still applies and (21) has
the additional row-vector term $\eta p\bm{w}^{j}\bm{B}^{*\intercal}$, which
can be bounded
$\lVert\bm{w}^{j}\bm{B}^{*\intercal}\rVert_{2}\leq\lVert\bm{w}^{j}\rVert_{2}\lVert\bm{B}^{*}\rVert\leq\epsilon_{noise}\lVert\bm{x}^{*j}\rVert_{2}{\sigma_{\max}^{*}}\leq\epsilon_{noise}\lVert\bm{u}^{*j}\rVert{\sigma_{\max}^{*2}}$.
This term contributes $\epsilon_{noise}\lVert\bm{u}^{*j}\rVert$in the final
bound, that is,
$\lVert\tilde{\bm{u}}^{+j}\rVert_{2}\leq(1-0.15/\kappa^{2})\lVert\bm{u}^{j}\rVert_{2}+2\lVert\bm{u}^{*j}\rVert_{2}+\epsilon_{noise}\lVert\bm{u}^{*j}\rVert$,
which ensures $\kappa^{2}\mu$ incoherence for the noisy gradient update
$\tilde{\bm{u}}^{+j}$, since $\epsilon_{noise}\leq 1$.

The proof details are the same as those for proving Theorem 2.1 given earlier
in Sec. IV-C.

###  A-B Noisy case lemmas

Our assumption
$\lvert{\bm{W}}_{jk}\rvert\leq\epsilon_{noise}\lvert{\bm{X}}^{*}_{jk}\rvert$
also implies that

$\max\big{(}\frac{\lVert\bm{w}_{k}\rVert}{\lVert\bm{x}^{*}_{k}\rVert},\frac{\lVert\bm{w}^{j}\rVert}{\lVert\bm{x}^{*j}\rVert}\big{)}\leq\epsilon_{noise},\text{
and
}|{\bm{W}}_{jk}|\leq\epsilon_{noise}\mu^{2}\sqrt{r/q}\sqrt{r/n}{\sigma_{\max}^{*}}$
(26)

This fact is used in proving both lemmas below.

######  Lemma A.2.

Let the observed matrix $\bm{Y}={\bm{X}}^{*}_{\Omega}+{\bm{W}}_{\Omega}$ be
corrupted by additive noise ${\bm{W}}$ such that
$\lvert{\bm{W}}_{jk}\rvert\leq\epsilon_{noise}\lvert{\bm{X}}^{*}_{jk}\rvert$.
Assuming also that $p\geq C\kappa^{6}r^{2}\mu\log q/n$ and
$\epsilon_{noise}\leq 1/\sqrt{r}\kappa^{3}$, then,
$\mathrm{SD}_{F}({\bm{U}}^{(00)},{\bm{U}}^{*})\leq c/\kappa^{2}$, where
${\bm{U}}^{(00)}\in\mathbb{R}^{n\times r}$ are the left-singular vectors of
$\bm{Y}$.

###### Proof.

By Wedin’s sin theta theorem (Frob norm version),

$\mathrm{SD}_{F}({\bm{U}}^{(00)},{\bm{U}}^{\star}{})\leq
C\frac{\|\bm{Y}-p{\bm{X}}^{\star}\|_{F}}{{\sigma_{\min}^{*}}}\leq
C\frac{\|{\bm{X}}^{\star}_{\Omega}-p{\bm{X}}^{\star}\|_{F}+\|{\bm{W}}_{\Omega}\|_{F}}{p{\sigma_{\min}^{*}}}\leq
C\sqrt{\frac{\kappa^{2}\mu r^{2}\log
n}{p}}+\frac{\|{\bm{W}}_{\Omega}\|_{F}}{p{\sigma_{\min}^{*}}},$ (27)

where we have used Lemma 3.21 of [32], with $p\geq C\kappa^{6}r^{2}\mu\log
q/n$, to bound
$(\lVert{\bm{X}}_{\Omega}^{*}-p{\bm{X}}^{*}\rVert_{F}/p{\sigma_{\min}^{*}})\leq
c/\kappa^{2}$. By using matrix-Bernstein inequality, we can show that
$\|{\bm{W}}_{\Omega}\|_{F}\leq 2\epsilon_{noise}\sqrt{r}p{\sigma_{\max}^{*}}$
whp. By the assumed upper bound on $\epsilon_{noise}$, we can then argue that
$\mathrm{SD}_{F}({\bm{U}}^{(00)},{\bm{U}}^{*})\leq c/\kappa^{2}$. The rest of
the proof is exactly the same as in the noiseless case (Lemma 4.1). ∎

######  Lemma A.3.

Assume that the observed matrix
$\bm{Y}={\bm{X}}^{*}_{\Omega}+{\bm{W}}_{\Omega}$ is corrupted by additive
noise ${\bm{W}}$ such that
$\lvert{\bm{W}}_{jk}\rvert\leq\epsilon_{noise}\lvert{\bm{X}}^{*}_{jk}\rvert$.
Assuming also $\lVert\bm{u}^{j}\rVert\leq\mu_{\bm{u}}\sqrt{r/n}$, where
$\mu_{u}=\kappa^{2}\mu$,
$\lVert\bm{b}_{k}\rVert\leq{\sigma_{\max}^{*}}\mu\sqrt{r/q}$ and
$\sigma_{\max}(\bm{B})\leq C{\sigma_{\max}^{*}}$. For $\epsilon_{noise}\leq
1/(\sqrt{r}\kappa^{3})$,

  1. 1.

$\lVert{\bm{W}}_{B}-\mathbb{E}[{\bm{W}}_{\bm{B}}]\rVert_{F}\leq\epsilon_{noise}\sqrt{r}p{\sigma_{\max}^{*}}$,
w.p. greater than $1-\exp(\log 2q-np/(\mu_{\bm{u}}^{2}r^{2}))$

  2. 2.

$\lVert{\bm{W}}_{\bm{B}}\rVert_{F}\leq
2\sqrt{r}\epsilon_{noise}p{\sigma_{\max}^{*}}$, w.p. same as 1).

  3. 3.

$\lVert{\bm{U}}_{k}^{\intercal}\bm{w}_{k}\rVert_{2}\leq
2\epsilon_{noise}p\lVert\bm{b}^{*}_{k}\rVert_{2}$, w.p. same as 1)

  4. 4.

$\lVert{\bm{W}}_{{\bm{U}}}-\mathbb{E}[{\bm{W}}_{\bm{U}}]\rVert_{F}\leq\epsilon_{noise}\sqrt{r}p{\sigma_{\max}^{*2}}$,
w.p. greater than $1-\exp(\log 2q-np/(\mu^{2}r^{2}))$

  5. 5.

$\lVert{\bm{W}}_{\bm{U}}\rVert_{F}\leq
2\epsilon_{noise}\sqrt{r}p{\sigma_{\max}^{*2}}$, w.p. same as 4).

###### Proof.

All terms are bounded using (26) and the matrix Bernstein inequality. ∎

##  Appendix B Proof of Corollary 7.1 (Improved guarantee for AltMin for LRMC)

In section 4.2 of [3], it is shown that the least-squares updates for
${\bm{U}}\in\mathbb{R}^{n\times r}$ and $\bm{B}\in\mathbb{R}^{r\times q}$ are
equivalent to the following QR-based updates:

$\displaystyle\bm{B}^{(t)}$
$\displaystyle=\operatorname*{\mathrm{argmin}}_{\bm{B}}\lVert\bm{Y}-{\bm{U}}^{(t)}\bm{B}\rVert_{F}^{2},\,\,\,\bm{B}^{(t)\intercal}\overset{\mathrm{QR}}{=}\bm{V}^{(t)}{\bm{R}}_{\bm{B}}$
(28) $\displaystyle\widetilde{\bm{U}}^{(t+1)}$
$\displaystyle=\operatorname*{\mathrm{argmin}}_{\widetilde{\bm{U}}}\lVert\bm{Y}^{\intercal}-\bm{B}^{(t)}\widetilde{\bm{U}}\rVert_{F}^{2},\,\,\,\widetilde{\bm{U}}^{(t+1)^{\intercal}}\overset{\mathrm{QR}}{=}{\bm{U}}^{(t+1)}{\bm{R}}_{\bm{U}}.$
(29)

####  B-1 $\mathbf{B}$-update (28) /
$\mathrm{SD}_{F}(\mathbf{V}^{(t)},\mathbf{V}^{*})$ Bound

Note that the $\bm{B}$-update in (28) is exactly the same as the
$\bm{B}$-update for AltGDMin. Therefore, we use Lemma 4.2 to bound
$\mathrm{SD}_{F}(\bm{V}^{(t)},\bm{V}^{*})$. Let
$\bm{P}_{*,\perp}\coloneq\mathbf{I}-\bm{V}^{*}\bm{V}^{*\intercal}$. Then,

$\displaystyle\mathrm{SD}_{F}(\bm{V}^{(t)},\bm{V}^{*})$
$\displaystyle=\lVert\bm{P}_{*,\perp}\bm{V}^{(t)}\rVert_{F}=\lVert\bm{P}_{*,\perp}\bm{B}^{\intercal}{\bm{R}}_{B}^{-1}\rVert_{F}\leq\lVert\bm{P}_{*,\perp}\bm{B}^{\intercal}\rVert_{F}\lVert{\bm{R}}_{B}^{-1}\rVert\leq{\lVert(\bm{B}-\bm{G})^{\intercal}\rVert_{F}}/{\sigma_{\min}(\bm{B})},$
(30)

where
$\bm{P}_{*,\perp}\bm{B}^{\intercal}=\bm{P}_{*,\perp}(\bm{G}^{\intercal}+(\bm{B}-\bm{G})^{\intercal})=\bm{P}_{*,\perp}(\bm{B}-\bm{G})^{\intercal}$,
because $\bm{G}^{\intercal}={\bm{X}}^{*\intercal}{\bm{U}}^{\intercal}$ and the
column-span of ${\bm{X}}^{*\intercal}$ is orthogonal to the span of
$\bm{P}_{*,\perp}$. By Lemma 4.2,
$\lVert\bm{B}-\bm{G}\rVert_{F}\leq{\sigma_{\min}^{*}}\delta^{(t-1)}/4$. By
Lemma 4.3, assuming $\delta^{(t-1)}\leq 1/(4\kappa)$,
$\sigma_{\min}(\bm{B})\geq{\sigma_{\min}^{*}}/2$. Substituting these bounds in
(30) and recalling that
$\delta^{(t-1)}\coloneq\mathrm{SD}_{F}({\bm{U}}^{(t)},{\bm{U}}^{*})$, w.p.
greater than $1-\exp(\log q-pn/(r^{2}\mu^{2}\kappa^{4}))$,

$\mathrm{SD}_{F}(\bm{V}^{(t)},\bm{V}^{*})\leq\frac{1}{2}\mathrm{SD}_{F}({\bm{U}}^{(t)},{\bm{U}}^{*}).$
(31)

####  B-2 Incoherence of $\mathbf{V}^{(t)}$

Recall that
$\widetilde{\bm{B}}^{\intercal}\overset{\mathrm{QR}}{=}\bm{V}{\bm{R}}$. Then,
the $k$-th row,
$\lVert\bm{v}^{k}\rVert_{2}\leq{\lVert\bm{b}_{k}\rVert_{2}}/{{\sigma_{\min}^{*}}(\bm{B})}\leq
C\kappa\mu\sqrt{r/q}$, where the last inequality follows from Lemmas 4.3 and
4.4. Thus, $\bm{V}$ is $\kappa\mu$-incoherent.

####  B-3 $\mathbf{U}$-Update (29) /
$\mathrm{SD}_{F}(\mathbf{U^{(t+1)}},\mathbf{U}^{*})$ Bound and Incoherence of
$\mathbf{U}^{(t+1)}$

The two AltMin steps are symmetric, so arguments analogous to the above help
show that

$\mathrm{SD}_{F}({\bm{U}}^{(t+1)},{\bm{U}}^{*})\leq\frac{1}{2}\mathrm{SD}_{F}(\bm{V}^{(t)},{\bm{U}}^{*}).$
(32)

Combining (31) and $\eqref{eq:altMinUBnd}$, we have
$\mathrm{SD}_{F}({\bm{U}}^{(t+1)},{\bm{U}}^{*})\leq\mathrm{SD}_{F}({\bm{U}}^{(t)},{\bm{U}}^{*})/4$.
For initialization we use the few lines of our Algorithm 1 and Lemma 4.1.
Consequently, AltMinComplete [3] initialized as given in the first few lines
of our Algorithm 1 needs $T=\log(1/\epsilon)$ iterations for
$\mathrm{SD}_{F}({\bm{U}}^{(t)},{\bm{U}}^{*})\leq\epsilon$.

## References

  * [1] A. A. Abbasi, S. Moothedath, and N. Vaswani, “Fast federated low rank matrix completion,” in _2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2023, pp. 1–6.
  * [2] E. J. Candes and B. Recht, “Exact matrix completion via convex optimization,” _Found. of Comput. Math_ , no. 9, pp. 717–772, 2008.
  * [3] P. Netrapalli, P. Jain, and S. Sanghavi, “Low-rank matrix completion using alternating minimization,” in _Annual ACM Symp. on Th. of Comp. (STOC)_ , 2013.
  * [4] M. Fazel, “Matrix rank minimization with applications,” _PhD thesis, Stanford Univ_ , 2002.
  * [5] R. Keshavan, A. Montanari, and S. Oh, “Matrix completion from a few entries,” _IEEE Trans. Info. Th._ , vol. 56, no. 6, pp. 2980–2998, 2010.
  * [6] R. Sun and Z.-Q. Luo, “Guaranteed matrix completion via non-convex factorization,” _IEEE Trans. Info. Th._ , vol. 62, no. 11, pp. 6535–6579, 2016.
  * [7] Y. Cherapanamjeri, K. Gupta, and P. Jain, “Nearly-optimal robust matrix completion,” _ICML_ , 2016.
  * [8] C. Ma, K. Wang, Y. Chi, and Y. Chen, “Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution,” in _Intl. Conf. Machine Learning (ICML)_ , 2018.
  * [9] M. Hardt and M. Wootters, “Fast matrix completion without the condition number,” in _Conf. on Learning Theory_ , 2014.
  * [10] Q. Zheng and J. Lafferty, “Convergence analysis for rectangular matrix completion using burer-monteiro factorization and gradient descent,” _arXiv preprint arXiv:1605.07051_ , 2016.
  * [11] X. Yi, D. Park, Y. Chen, and C. Caramanis, “Fast algorithms for robust pca via gradient descent,” in _Neur. Info. Proc. Sys. (NeurIPS)_ , 2016.
  * [12] M. Hardt, “Understanding alternating minimization for matrix completion,” in _2014 IEEE 55th Annual Symposium on Foundations of Computer Science_. IEEE, 2014, pp. 651–660.
  * [13] P. Jain and P. Netrapalli, “Fast exact matrix completion with finite samples,” in _Conf. on Learning Theory_ , 2015, pp. 1007–1034.
  * [14] L. W. Mackey, A. Talwalkar, and M. I. Jordan, “Distributed matrix completion and robust factorization,” _J. Mach. Learn. Res._ , vol. 16, no. 1, pp. 913–960, 2015.
  * [15] C. Teflioudi, F. Makari, and R. Gemulla, “Distributed matrix completion,” in _2012 ieee 12th international conference on data mining_. IEEE, 2012, pp. 655–664.
  * [16] Q. Ling, Y. Xu, W. Yin, and Z. Wen, “Decentralized low-rank matrix completion,” in _2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2012, pp. 2925–2928.
  * [17] A.-Y. Lin and Q. Ling, “Decentralized and privacy-preserving low-rank matrix completion,” _Journal of the Operations Research Society of China_ , vol. 3, no. 2, pp. 189–205, 2015.
  * [18] M. Mardani, G. Mateos, and G. Giannakis, “Decentralized sparsity-regularized rank minimization: Algorithms and applications,” _IEEE Trans. Sig. Proc._ , 2013.
  * [19] Z. Li, B. Ding, C. Zhang, N. Li, and J. Zhou, “Federated matrix factorization with privacy guarantee,” _Proceedings of the VLDB Endowment_ , vol. 15, no. 4, 2021.
  * [20] V. W. Anelli, Y. Deldjoo, T. Di Noia, A. Ferrara, and F. Narducci, “User-controlled federated matrix factorization for recommender systems,” _Journal of Intelligent Information Systems_ , vol. 58, no. 2, pp. 287–309, 2022.
  * [21] X. He, Q. Ling, and T. Chen, “Byzantine-robust stochastic gradient descent for distributed low-rank matrix completion,” in _2019 IEEE Data Science Workshop (DSW)_. IEEE, 2019, pp. 322–326.
  * [22] S. Nayer and N. Vaswani, “Fast and sample-efficient federated low rank matrix recovery from column-wise linear and quadratic projections,” _IEEE Trans. Info. Th._ , Feb. 2023, arXiv:2102.10217 (Feb. 2021).
  * [23] N. Vaswani, “Efficient federated low rank matrix recovery via alternating gd and minimization: A simple proof,” _IEEE Trans. Info. Th._ , 2024, arXiv: 2306.17782.
  * [24] S. Nayer, P. Narayanamurthy, and N. Vaswani, “Provable low rank phase retrieval,” _IEEE Trans. Info. Th._ , March 2020.
  * [25] S. Nayer and N. Vaswani, “Sample-efficient low rank phase retrieval,” _IEEE Trans. Info. Th._ , Dec. 2021.
  * [26] R. Vershynin, _High-dimensional probability: An introduction with applications in data science_. Cambridge University Press, 2018, vol. 47.
  * [27] Y. Chen, Y. Chi, J. Fan, and C. Ma, “Spectral methods for data science: A statistical perspective,” _Foundations and Trends® in Machine Learning_ , vol. 14, no. 5, p. 566–806, 2021. [Online]. Available: http://dx.doi.org/10.1561/2200000079
  * [28] M. Nashed, “A decomposition relative to convex sets,” _Proceedings of the American Mathematical Society_ , vol. 19, no. 4, pp. 782–786, 1968.
  * [29] E. H. Zarantonello, “Projections on convex sets in hilbert space and spectral theory: Part i. projections on convex sets: Part ii. spectral theory,” in _Contributions to nonlinear functional analysis_. Elsevier, 1971, pp. 237–424.
  * [30] Y. Chen and E. Candes, “Solving random quadratic systems of equations is nearly as easy as solving linear systems,” in _Neur. Info. Proc. Sys. (NeurIPS)_ , 2015, pp. 739–747.
  * [31] A. A. Abbasi, S. Moothedath, and N. Vaswani, “Fast federated low rank matrix completion,” in _2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2023, pp. 1–6.
  * [32] Y. Chen, Y. Chi, J. Fan, and C. Ma, “Spectral methods for data science: A statistical perspective,” _arXiv preprint arXiv:2012.08496_ , 2020.
  * [33] L. N. Trefethen and D. Bau, _Numerical linear algebra_. Siam, 2022, vol. 181.

Algorithm 2 AltGDMin-Federated

1:Partition $\bm{Y}$ into $2T+1$ subsets
$\bm{Y}_{\Omega^{(0)}},\cdots,\bm{Y}_{\Omega^{(2T)}}$

2://Initialize ${\bm{U}}^{(0)}$ by Power Method

3:Center: Initialize random ${\bm{U}}\in\mathbb{R}^{n\times r}$; push to
nodes.

4:for $t\in 1\cdots T_{\text{init}}$ do

5: Node $\ell$, $\ell\in[\gamma]$

6:
$\bm{M}_{\ell}\leftarrow\sum_{k\in\bm{S}_{\ell}}\bm{y}_{\Omega_{k}^{(0)}}\bm{y}_{\Omega_{k}^{(0)}}^{\intercal}{\bm{U}}$;
push to center.

7: Center: ${\bm{U}}\leftarrow\mathrm{QR}(\sum_{\ell}\bm{M}_{\ell})$; push to
nodes.

8:Center: Clip and orthonormalize ${\bm{U}}$ as given in Algorithm 1

9://AltGDMin Iterations

10:for $t\in 1\cdots T$ do

11: Node $\ell$, $\ell\in[\gamma]$:

12:
$\bm{b}_{k}^{(t)}\leftarrow({\bm{U}}_{k}^{(t-1)})^{\dagger}\bm{y}_{\Omega_{k}^{(t)}}\,\text{
for all }\,k\in\mathcal{S}_{\ell}$

13:
$\mathrm{GradU}_{\ell}\leftarrow\sum_{k\in\bm{S}_{\ell}}({\bm{U}}_{k}\bm{b}_{k}-\bm{y})_{\Omega_{k}}\bm{b}_{k}^{\intercal}$;
push to center.

14: Center:

15:
${\bm{U}}^{(t)}\leftarrow\mathrm{QR}({\bm{U}}^{(t-1)}-\eta\sum_{\ell}\mathrm{GradU}_{\ell})$;
push to nodes.

##  Appendix C Federated AltGDmin and comparison with benchmarks

The following material is essentially taken from [1] (few errors there are
corrected). We repeat it here for ease of review. Details on how AltGDmin is
federated are given below. We also provide details on how to develop efficient
federated implementations of the other benchmark methods.

###  C-A Federated AltGDMin and its Complexity and Privacy

In a federated setting, at each algorithm iteration, $t$, each node $\ell$
performs two operations i) updating $\bm{b}_{k}$ by the LS solution, for all
$k\in\bm{S}_{\ell}$; and ii) computation of the partial gradient
$\sum_{k\in\bm{S}_{\ell}}[\nabla_{{\bm{U}}}f({\bm{U}},\bm{B})]_{k}=\sum_{k\in\bm{S}_{\ell}}({\bm{U}}_{k}\bm{b}_{k}-\bm{y})_{\Omega_{k}}\bm{b}_{k}^{\intercal}$.
Only the $n\times r$ partial gradient needs to be sent to the center. The
center computes its QR decomposition and broadcasts that to all the nodes.
This is used by the nodes in the next iteration. We summarize this in
Algorithm 2.

####  C-A1 Communication Complexity of AltGDmin

The upstream (node to center) communication cost is the cost needed to
transmit the partial gradient computed at node $\ell$ which is of size
$n\times r$, but may be sparse if $\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|<n$.
This will happen if $|\bm{S}_{\ell}|=q/\gamma$ is small, e.g., if
$\gamma\approx q$. In general, this cost is
$\min\left(n,\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|\right)r$. The center
communicates the updated ${\bm{U}}$ to the nodes with a downstream (center to
node) communication complexity of $nr$.

####  C-A2 Time Complexity of AltGDmin

Each LS problem can be solved in time $O(|\Omega_{k}|r^{2})$ since solving an
LS problem with design matrix of size $a\times b$ is $O(ab^{2})$, see equation
11.14 in [33]. Gradient computation for one $k$,
$({\bm{U}}_{k}\bm{b}_{k}-\bm{y}_{\Omega_{k}})\bm{b}_{k}^{\intercal}$, costs
$|\Omega_{k}|r$ time. Thus, the per-node time cost is
$\sum_{k\in\bm{S}_{\ell}}\max(|\Omega_{k}|r,|\Omega_{k}|r^{2})=\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|r^{2}$.
The QR decomposition of ${\bm{U}}\in\mathbb{R}^{n\times r}$ is performed at
the center and costs $O(nr^{2})$, see equation 10.9 in [33].

####  C-A3 Privacy

The algorithm is private because, given only the partial gradient terms
$\sum_{k\in\bm{S}_{\ell}}[\nabla_{{\bm{U}}}f({\bm{U}},\bm{B}]_{k}$ and
${\bm{U}}$, the center cannot recover $\bm{B}$ or the $\bm{y}_{k}$’s.

####  C-A4 SVD Initialization

This is computed by using power method for $\bm{Y}\bm{Y}^{\intercal}$. This
costs $O(\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|r)$ per power method iteration.
The upstream per-node communication cost is
$O(\min(n,\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|)r)$ and the downstream cost is
$O(nr)$. The method converges linearly and thus, for $\epsilon_{svd}$
accuracy, $\log(1/\epsilon_{svd})$ iterations are required. Typically,
$\epsilon_{svd}=c$ or $c/r$ suffices since SVD is only used for
initialization.

###  C-B Complexity of Benchmark Methods

####  C-B1 AltMin [3]

Since LRMC measurements are both row-wise and column-wise local, the LS steps
to update both $\bm{B}$ and ${\bm{U}}$ decouple column-wise and row-wise
respectively. Hence, for LRMC, AltMin is also quite fast. In the centralized
setting, both AltMin and AltGDmin have a time cost of $|\Omega|r^{2}$ per
iteration.

When AltMin is used in a federated setting (different subsets of data observed
at different nodes) without requiring privacy, the update of columns of
$\bm{B}$ is done locally at the respective nodes, with a time cost of
$\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|r^{2}$. These, and the observed data
vectors, are transmitted to the center with a communication cost of
$\sum_{k\in\bm{S}_{\ell}}\max(|\Omega_{k}|,r)=\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|$.
The center implements the LS step for each row of ${\bm{U}}$ with a time cost
of $|\Omega|r^{2}$ and sends the new ${\bm{U}}$ to the nodes. The time cost at
the center, and the communication cost at the nodes, are both higher than that
of AltGDmin by a factor of $|\Omega|/n$ and $|\Omega|/(\gamma n)$
respectively.

The above approach to federate AltMin does not guarantee privacy because the
data needs to be sent to the center. In order to guarantee privacy, the LS
step for updating ${\bm{U}}$ needs to be solved using multiple GD iterations.
With this, the time cost at the node becomes
$\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|r\max(r,\log(1/\epsilon))$, while the
time cost at the center becomes zero (ignoring the cost of
addition/subtraction). The communication cost from node to center now becomes
$\min(n,\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|)r\log(1/\epsilon)$. Both time and
communication cost are higher than those of AltGDmin by a factor of
$\log(1/\epsilon)$.

####  C-B2 ProjGD [7, 13]

Each iteration of Projected GD (ProjGD) involves one step of GD w.r.t. the
cost function to be minimized, followed by projecting onto the constraint set
which is the set of rank $r$ matrices (by SVD) [7, 13], i.e.,
${\bm{X}}^{+}=\textrm{Proj}_{r}({\bm{X}}-\eta({\bm{X}}-\bm{Y})_{\Omega})$. The
nodes transmit the partial gradients
$(\bm{x}_{\Omega_{k}}-\bm{y}_{\Omega_{k}})\in\mathbb{R}^{|\Omega_{k}|}$ to the
center. This has cost $\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|$. The center
computes the SVD of $({\bm{X}}-\eta({\bm{X}}-\bm{Y})_{\Omega})$. Since
${\bm{X}}$ is rank-$r$ and the second term is sparse, thus, the SVD step needs
time of order $\max(n,q)r^{2}+|\Omega|r$ per SVD iteration [7]. Hence the cost
of this step is $\max(\max(n,q)r^{2},|\Omega|r)r\log(1/\epsilon)$. The cost is
dominated by the time needed for the SVD step at the $T$-th algorithm
iteration; at this iteration the SVD accuracy needs to be of order $\epsilon$.
This method is not private because the center knows ${\bm{X}}$. The center
then transmits $\bm{x}_{\Omega_{k}}$ to node $k$, with total downstream
communication complexity $|\Omega|$.

####  C-B3 Federated FactGD [11]

FactGD factorizes ${\bm{X}}={\bm{U}}\bm{B}$. After initialization, at each
iteration, it updates ${\bm{U}}$ and $\bm{B}$ by one GD step (for the cost
function specified next), followed by projecting each of them onto the set of
matrices with incoherent rows and columns respectively. Denote the latter set
by ${\mathcal{U}}$. Initialization involves SVD on $\bm{Y}$ followed by a
similar projection onto ${\mathcal{U}}$. The GD steps are for the cost
function
$f({\bm{U}},\bm{B})+\|{\bm{U}}^{\intercal}{\bm{U}}-\bm{B}\bm{B}^{\intercal}\|_{F}^{2}$.
The second term is a norm balancing term that ensures the norm of ${\bm{U}}$
does not keep increasing with iterations while that of $\bm{B}$ decreases (or
vice versa). The gradients of $f({\bm{U}},\bm{B})$ are
$\nabla_{\bm{U}}=\nabla_{{\bm{X}}}\bm{B}^{\intercal}=\sum_{\ell}(\nabla_{{\bm{X}},\ell}\bm{B}_{\ell}^{\intercal}$
and $\nabla_{\bm{B}}={\bm{U}}^{\intercal}\nabla_{{\bm{X}}}$ with
$\nabla_{\bm{X}}=({\bm{X}}-\bm{Y})_{\Omega}$. Parts of these can be computed
at the nodes with a computation cost of
$\min(n,\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|)$ and
$\min(q,\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|)$ respectively, and sent to the
center. The center just needs to concatenate or sum what is received from the
nodes. The communication cost is dominated by the cost to communicate the
terms for $\nabla_{\bm{U}}$ and is
$\min(n,\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|)r$. The gradients w.r.t. the
second term are $\nabla_{\bm{U}}={\bm{U}}({\bm{U}}^{\intercal}{\bm{U}})$ and
$\nabla_{B}=\bm{B}^{\intercal}(\bm{B}\bm{B}^{\intercal})=\bm{B}^{\intercal}(\sum_{\ell}\bm{B}_{\ell}\bm{B}_{\ell}^{\intercal})$.

Algorithm | Time (node) | Time (center) | Comm. (node) | Comm. (center) | Sample $\lvert\Omega\rvert$ | Iteration $(T)$ | Private?
---|---|---|---|---|---|---|---
| per iter. | per iter. | per iter. | per iter. | Complexity | Complexity |
AltGDMin (Proposed) | $\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|r^{2}$ | $nr^{2}$ | $\min(n,\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|)r$ | $nr$ | $nr^{2}\log n\log(\frac{1}{\epsilon})$ | $\log(\frac{1}{\epsilon})$ | yes
FactGD [11] | $\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|r$ | $nr^{2}$ | $\min(n,\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|)r$ | $nr$ | $nr^{2}\log n$ | $r\log(\frac{1}{\epsilon})$ | yes
AltMin-Private [3] | $\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|r\log(1/\epsilon)$ | $0$ | $\min(n,\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|)r\log(\frac{1}{\epsilon})$ | $nr$ | $nr^{4.5}\log n\log(\frac{1}{\epsilon})$ | $\log(\frac{1}{\epsilon})$ | yes
AltMin-Not-Private [3] | $\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|r^{2}$ | $|\Omega|r^{2}$ | $\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|$ | $nr$ | $nr^{4.5}\log n\log(\frac{1}{\epsilon})$ | $\log(\frac{1}{\epsilon})$ | no
Smooth AltMin [12] | $\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|r^{2}$ | $nr^{2}$ | $\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|$ | $nr$ | $nr^{3}\log n\log(\frac{1}{\epsilon})$ | $\log(\frac{1}{\epsilon})$ | no
ProjGD [13, 7] | 0 | $\max(|\Omega|r,nr^{2})\log\frac{1}{\epsilon}$ | $\sum_{k\in\bm{S}_{\ell}}|\Omega_{k}|$ | $\lvert\Omega\rvert$ | $nr^{2}\log^{2}n\log(\frac{{\sigma_{\max}^{*}}}{\epsilon})$ | $\log(\frac{n}{\epsilon})$ | no

TABLE II: Detailed complexities: time, communication, sample, iteration.