In this section we give the full proof of Theorem~\ref{thm:mf-main}.

First we recall the gradient of our objective function $f(\mat{U}, \mat{V}) = \frac12 \norm{\mat{U}\mat{V}^\top - \mat{M}^*}_F^2$:
\begin{align*}
\frac{\partial f(\mat U, \mat V)}{\partial \mat U} = (\mat U \mat V^\top - \mat M^*) \mat V, \qquad
\frac{\partial f(\mat U, \mat V)}{\partial \mat V} = (\mat U \mat V^\top - \mat M^*)^\top \mat U.
\end{align*}

We also need to calculate the Hessian $\nabla^2 f(\mat U, \mat V)$.
The Hessian can be viewed as a matrix that operates on vectorized matrices of dimension $(d_1+d_2)\times r$ (i.e., the same shape as $\begin{pmatrix}
\mat U\\ \mat V
\end{pmatrix}$).
Then, for any $\mat W \in \R^{(d_1+d_2)\times r}$, the Hessian $\nabla^2 f(\mat W)$ defines a quadratic form
\[
[\nabla^2 f(\mat W)] (\mat A, \mat B) = \sum_{i, j, k, l} \frac{\partial^2 f(\mat W)}{\partial \mat W[i, j] \partial \mat W[k, l]} \mat A[i, j] \mat B[k, l], \qquad \forall \mat A, \mat B \in \R^{(d_1+d_2)\times r}.
\]
With this notation, we can express the Hessian $\nabla^2 f(\mat U, \mat V)$ as follows:
\begin{equation} \label{eqn:mf-hessian}
\begin{aligned}  \
[\nabla^2 f(\mat U, \mat V)] (\mat \Delta, \mat \Delta)
= 2 \left\langle \mat U \mat V^\top - \mat M^*, \mat\Delta_{\mat U} \mat{\Delta}_{\mat V}^\top \right\rangle + \norm{\mat U \mat\Delta_{\mat V}^\top + \mat\Delta_{\mat U} \mat V^\top }_F^2, &
\\
\forall \mat \Delta = \begin{pmatrix}
\mat \Delta_{\mat U} \\ \mat{\Delta}_{\mat V}
\end{pmatrix}, 
\mat \Delta_{\mat U} \in \R^{d_1\times r}, \ &\mat \Delta_{\mat V} \in \R^{d_2\times r}.
\end{aligned}
\end{equation}


Now we use the expression of the Hessian to prove that $f(\mat U, \mat V)$ is locally smooth when both arguments $\mat U$ and $\mat V$ are bounded.

\begin{lem}[Smoothness over a bounded set]\label{lem:mf-local-smooth}
	For any $c>0$, constrained on the set $\cS = \{(\mat U, \mat V): \mat U \in \R^{d_1\times r}, \mat V \in \R^{d_2\times r}, \norm{\mat U}_F^2 \le c\norm{\mat M^*}_F, \norm{\mat V}_F^2 \le c\norm{\mat M^*}_F \}$, the function $f$ is $\left( (6c+2) \norm{\mat M^*}_F \right)$-smooth.
\end{lem}
\begin{proof}
	We prove smoothness by giving an upper bound on $\lambda_{\max}(\nabla^2 f(\mat U, \mat V)) $ for any $(\mat U, \mat V) \in \cS$.
	
	For any $(\mat U, \mat V) \in \cS$ and any $ \mat \Delta = \begin{pmatrix}
	\mat \Delta_{\mat U} \\ \mat{\Delta}_{\mat V}
	\end{pmatrix}$ ($\mat \Delta_{\mat U} \in \R^{d_1\times r}, \mat \Delta_{\mat V} \in \R^{d_2\times r}$),
	from \eqref{eqn:mf-hessian} we have
	\begin{align*}
	& [\nabla^2 f(\mat U, \mat V)] (\mat \Delta, \mat \Delta) \\
	\le\,& 2 \norm{ \mat U \mat V^\top - \mat M^*}_F \norm{ \mat\Delta_{\mat U} \mat{\Delta}_{\mat V}^\top}_F  + \norm{\mat U \mat\Delta_{\mat V}^\top + \mat\Delta_{\mat U} \mat V^\top }_F^2 \\
	\le\,& 2 \left( \norm{ \mat U}_F \norm{\mat V^\top}_F + \norm{\mat M^*}_F \right) \norm{ \mat\Delta_{\mat U}}_F \norm{\mat{\Delta}_{\mat V}^\top}_F  + \left( \norm{\mat U}_F \norm {\mat\Delta_{\mat V}^\top }_F + \norm{\mat\Delta_{\mat U}}_F \norm{\mat V^\top}_F \right)^2 \\
	\le\,& 2\left( c\norm{\mat M^*}_F + \norm{\mat M^*}_F  \right) \norm{\mat{\Delta}}_F^2 + \left( 2\sqrt{c\norm{\mat M^*}_F} \cdot  \norm{\mat{\Delta}}_F \right)^2 \\
	=\,& (6c+2) \norm{\mat M^*}_F  \norm{\mat{\Delta}}_F^2.
	\end{align*}
	This implies $\lambda_{\max}(\nabla^2 f(\mat U, \mat V)) \le (6c+2) \norm{\mat M^*}_F$.
\end{proof}


\subsection{Proof of Lemma~\ref{lem:mf-balance}}


Recall the following three properties we want to prove in Lemma~\ref{lem:mf-balance}, which we call $\cA(t)$, $\cB(t)$ and $\cC(t)$, respectively:
\begin{align*}
	\cA(t):\qquad & \norm{\mat U_t^\top \mat U_t - \mat V_t^\top \mat V_t}_F \le \epsilon, \\
	\cB(t):\qquad & f(\mat U_{t}, \mat V_{t}) \le f(\mat U_{t-1}, \mat V_{t-1}) \le \cdots \le f(\mat U_{0}, \mat V_{0}) \le 2 \norm{\mat M^*}_F^2, \\
	\cC(t):\qquad & \norm{\mat U_{t}}_F^2 \le  5\sqrt{r} \norm{\mat M^*}_F, \norm{\mat V_t}_F^2 \le  5\sqrt{r} \norm{\mat M^*}_F.
\end{align*}

We use induction to prove these statements.
For $t=0$, we can make the Gaussian variance in the initialization sufficiently small such that with high probability we have $$\norm{\mat U_{0}}_F^2 \le  \epsilon,\qquad \norm{\mat V_0}_F^2 \le  \epsilon, \qquad \norm{\mat U_0^\top \mat U_0 - \mat V_0^\top \mat V_0}_F \le \frac\epsilon2.$$
From now on we assume they are all satisfied.
Then $\cA(0)$ is already satisfied, $\cC(0)$ is satisfied because $\epsilon < \norm{\mat M^*}_F$,
and $\cB(0)$ can be verified by $f(\mat U_{0}, \mat V_{0}) = \frac12 \norm{\mat U_0 \mat V_0^\top - \mat M^*}_F^2 \le \norm{\mat U_0 \mat V_0^\top}_F^2 + \norm{\mat M^*}_F^2 \le \norm{\mat U_0}_F^2 \norm{\mat V_0^\top}_F^2 + \norm{\mat M^*}_F^2 \le \epsilon^2+\norm{\mat M^*}_F^2\le 2\norm{\mat M^*}_F^2$.

To prove $\cA(t)$, $\cB(t)$ and $\cC(t)$ for all $t$, we prove the following three claims. Since we have $\cA(0)$, $\cB(0)$ and $\cC(0)$, if the following claims are all true, the proof will be completed by induction.
\begin{enumerate}[(i)]
	\item $\cB(0), \ldots, \cB(t), \cC(0),  \ldots, \cC(t) \implies \cA(t+1)$;
	\item $\cB(0), \ldots, \cB(t), \cC(t) \implies \cB(t+1)$;
	\item $\cA(t), \cB(t) \implies \cC(t)$.
\end{enumerate}


\begin{claim}
	$\cB(0), \ldots, \cB(t), \cC(0),  \ldots, \cC(t) \implies \cA(t+1)$.
\end{claim}
\begin{proof}
	Using the update rule \eqref{eqn:mf-gd-dynamics} we can calculate
	\begin{align*}
	& \mat U_{t+1}^\top \mat U_{t+1} - \mat V_{t+1}^\top \mat V_{t+1} \\ 
	=\, & \left(\mat U_t - \eta_t (\mat U_t \mat V_t^\top - \mat M^*) \mat V_t\right)^\top \left(\mat U_t - \eta_t (\mat U_t \mat V_t^\top - \mat M^*) \mat V_t\right) \\ & - \left(\mat V_t - \eta_t (\mat U_t \mat V_t^\top - \mat M^*)^\top \mat U_t\right)^\top \left(\mat V_t - \eta_t (\mat U_t \mat V_t^\top - \mat M^*)^\top \mat U_t\right) \\
	=\, & \mat U_t^\top \mat U_t - \mat V_t^\top \mat V_t + \eta_t^2 \left( \mat V_t^\top \mat R_t^\top \mat R_t \mat V_t - \mat U_t^\top \mat R_t^\top \mat R_t \mat U_t \right),
	\end{align*}
	where $\mat R_t = \mat U_t \mat V_t^\top - \mat M^*$.
	Then we have
	\begin{equation} \label{eqn:mf-inproof-1}
	\begin{aligned}
	&\norm{\mat U_{t+1}^\top \mat U_{t+1} - \mat V_{t+1}^\top \mat V_{t+1}}_F\\
	\le\,& \norm{\mat U_t^\top \mat U_t - \mat V_t^\top \mat V_t}_F + \eta_t^2 \left( \norm{\mat V_t^\top \mat R_t^\top \mat R_t \mat V_t }_F + \norm{ \mat U_t^\top \mat R_t^\top \mat R_t \mat U_t}_F \right) \\
	\le\,& \norm{\mat U_t^\top \mat U_t - \mat V_t^\top \mat V_t}_F + \eta_t^2 \left( \norm{\mat V_t}_F^2 \norm{\mat R_t}_F^2  + \norm{\mat U_t}_F^2 \norm{\mat R_t}_F^2  \right) \\
	=\,& \norm{\mat U_t^\top \mat U_t - \mat V_t^\top \mat V_t}_F + 2\eta_t^2 \left( \norm{\mat V_t}_F^2   + \norm{\mat U_t}_F^2   \right) f(\mat U_t, \mat V_t) \\
	\le\,& \norm{\mat U_t^\top \mat U_t - \mat V_t^\top \mat V_t}_F + 2\eta_t^2 \cdot 10\sqrt{r} \norm{\mat M^*}_F \cdot 2 \norm{\mat M^*}_F^2,
	\end{aligned}
	\end{equation}
	where the last line is due to $\cB(t)$ and $\cC(t)$.
	
	Since we have $\cB(t')$ and $\cC(t')$ for all $t' \le t$, \eqref{eqn:mf-inproof-1} is still true when substituting $t$ with any $t'\le t$. Summing all of them and noting $\norm{\mat U_0^\top \mat U_0 - \mat V_0^\top \mat V_0}_F \le \frac{\epsilon}{2}$, we get
	\begin{align*}
	&\norm{\mat U_{t+1}^\top \mat U_{t+1} - \mat V_{t+1}^\top \mat V_{t+1}}_F \\
	\le\,& \norm{\mat U_0^\top \mat U_0 - \mat V_0^\top \mat V_0}_F + 40\sqrt{r} \norm{\mat M^*}_F^3 \sum_{i=0}^t \eta_i^2 \\
	\le\,& \frac\epsilon2 + 40\sqrt{r} \norm{\mat M^*}_F^3 \sum_{i=0}^t \frac{1}{(i+1)^2} \cdot \frac{\epsilon/r}{100^2\norm{\mat M^*}_F^3}\\ 
	\le\,&\epsilon.
	\end{align*}
	Therefore we have proved $\cA(t+1)$.
\end{proof}

\begin{claim}
	$\cB(0), \ldots, \cB(t), \cC(t) \implies \cB(t+1)$.
\end{claim}
\begin{proof}
	Note that we only need to show $f(\mat U_{t+1}, \mat V_{t+1}) \le f(\mat U_{t}, \mat V_{t})$.
	We prove this using the standard analysis of gradient descent, for which we need the smoothness of the objective function $f$ (Lemma~\ref{lem:mf-local-smooth}).
	We first need to bound $\norm{\mat U_t}_F$, $\norm{\mat V_t}_F$, $\norm{\mat U_{t+1}}_F$ and $\norm{\mat V_{t+1}}_F$. We know from $\cC(t)$ that $\norm{\mat U_{t}}_F^2 \le  5\sqrt{r} \norm{\mat M^*}_F$ and $\norm{\mat V_t}_F^2 \le  5\sqrt{r} \norm{\mat M^*}_F$.
	We can also bound $\norm{\mat U_{t+1}}_F^2$ and $\norm{\mat V_{t+1}}_F^2$ easily from the GD update rule:
	\begin{align*}
		&\norm{\mat U_{t+1}}_F^2 \\
		=\,& \norm{\mat U_t - \eta_t (\mat U_t \mat V_t^\top - \mat M^*) \mat V_t}_F^2 \\
		\le\,& 2 \norm{\mat U_t}_F^2 + 2\eta_t^2 \norm{\mat U_t \mat V_t^\top - \mat M^*}_F^2 \norm{\mat V_t}_F^2 \\
		\le\,& 2\cdot 5\sqrt{r} \norm{\mat M^*}_F + 2 \eta_t^2 \cdot 2f(\mat U_t, \mat V_t) \cdot 5\sqrt{r} \norm{\mat M^*}_F\\
		\le\,& 10\sqrt{r} \norm{\mat M^*}_F + 2 \cdot \frac{\epsilon/r}{100^2 (t+1)^2 \norm{\mat M^*}_F^3} \cdot 4\norm{\mat M^*}_F^2 \cdot 5\sqrt{r} \norm{\mat M^*}_F & \text{(using $\cB(t)$)} \\
		\le \,& 10\sqrt{r} \norm{\mat M^*}_F + \frac{\epsilon}{100} \\
		\le\, & 11\sqrt{r} \norm{\mat M^*}_F. & \text{(using $\epsilon < \norm{\mat M^*}_F$)}
	\end{align*}
	Let $\beta =  (66\sqrt{r}+2) \norm{\mat M^*}_F $.
	 From Lemma~\ref{lem:mf-local-smooth}, $f$ is $\beta$-smooth over $\cS = \{(\mat U, \mat V): \norm{\mat U}_F^2 \le 11\sqrt{r} \norm{\mat M^*}_F, \norm{\mat V}_F^2 \le 11\sqrt{r} \norm{\mat M^*}_F \}$.
	 Also note that $\eta_t < \frac{1}{\beta}$ by our choice. Then using smoothness we have
	 \begin{equation} \label{eqn:mf-obj-decrease}
	 \begin{aligned}
	 &f(\mat U_{t+1}, \mat V_{t+1}) \\
	 \le\,& f(\mat U_{t}, \mat V_{t}) + \left\langle  \nabla f(\mat U_t, \mat V_t), \begin{pmatrix}
		\mat U_{t+1}\\ \mat V_{t+1}
	 	\end{pmatrix} - \begin{pmatrix}
	 	\mat U_{t}\\ \mat V_{t}
	 	\end{pmatrix} \right\rangle + \frac{\beta}{2} \norm{ \begin{pmatrix}
	 		\mat U_{t+1}\\ \mat V_{t+1}
	 		\end{pmatrix} - \begin{pmatrix}
	 		\mat U_{t}\\ \mat V_{t}
	 		\end{pmatrix}  }_F^2 \\
 	=\,& f(\mat U_{t}, \mat V_{t}) - \eta_t \norm{ \nabla f(\mat U_t, \mat V_t) }_F^2 + \frac{\beta}{2}\eta_t^2 \norm{ \nabla f(\mat U_t, \mat V_t) }_F^2 \\
 	\le\,& f(\mat U_{t}, \mat V_{t}) - \frac{\eta_t}{2} \norm{ \nabla f(\mat U_t, \mat V_t) }_F^2.
	 \end{aligned}
	 \end{equation}
	 Therefore we have shown $\cB(t+1)$.
\end{proof}


\begin{claim}
	$\cA(t), \cB(t) \implies \cC(t)$.
\end{claim}
\begin{proof}
	From $\cB(t)$ we know $\frac12 \norm{\mat U_t \mat V_t^\top - \mat M^*}_F^2 \le 2 \norm{\mat M^*}_F^2$ which implies $\norm{\mat U_t \mat V_t^\top}_F \le 3\norm{\mat M^*}_F$.
	Therefore it suffices to prove
	\begin{equation} \label{eqn:mf-inproof-toshow-1}
		 \norm{\mat U \mat V^\top}_F \le 3\norm{\mat M^*}_F,
		 \norm{\mat U^\top \mat U - \mat V^\top \mat V}_F \le \epsilon
		 \implies \norm{\mat U}_F^2 \le 5\sqrt{r} \norm{\mat M^*}_F, \norm{\mat V}_F^2 \le 5\sqrt{r} \norm{\mat M^*}_F.
	\end{equation}
	
	Now we prove \eqref{eqn:mf-inproof-toshow-1}.
	Consider the SVD $\mat U = \mat\Phi \mat\Sigma \mat{\Psi}^\top$, where $\mat \Phi \in \R^{d_1\times d_1}$ and $\mat{\Psi} \in \R^{r\times r}$ are orthogonal matrices, and $\mat\Sigma \in \R^{d_1\times r}$ is a diagonal matrix.
	Let $\sigma_i = \mat \Sigma[i, i]$ ($i\in[r]$) which are all the singular values of $\mat U$.
	Define $\widetilde{\mat V} = \mat V \mat\Psi$. Then we have
	\begin{align*}
	3\norm{\mat M^*}_F
	\ge \norm{\mat U \mat V^\top}_F 
	= \norm{\mat\Phi \mat\Sigma \mat{\Psi}^\top  \mat{\Psi} \widetilde{\mat V}^\top }_F
	= 	\norm{\mat \Sigma \widetilde{\mat V}^\top }_F
	= \sqrt{\sum_{i=1}^r \sigma_i^2 \norm{\widetilde{\mat V}[:,i]}^2}
	\end{align*}
	and
	\begin{align*}
	\epsilon &\ge  \norm{\mat U^\top \mat U - \mat V^\top \mat V}_F
	= \norm{ \mat\Psi \mat\Sigma^\top \mat{\Phi}^\top \mat\Phi \mat\Sigma \mat{\Psi}^\top - \mat{\Psi} \widetilde{\mat V}^\top \widetilde{\mat V} \mat{\Psi}^\top }_F
	= \norm{ \mat\Sigma^\top \mat\Sigma  -  \widetilde{\mat V}^\top \widetilde{\mat V} }_F \\
	&\ge \sqrt{\sum_{i=1}^r \left( \sigma_i^2  - \norm{\widetilde{\mat V}[:,i]}^2 \right)^2}.
	\end{align*}
	Using the above two inequalities we get
	\begin{align*}
	\sum_{i=1}^r \sigma_i^4
	&\le \sum_{i=1}^r \left( \sigma_i^4 + \norm{\widetilde{\mat V}[:,i]}^4 \right)
	= \sum_{i=1}^r \left( \sigma_i^2  - \norm{\widetilde{\mat V}[:,i]}^2 \right)^2 + 2 \sum_{i=1}^r \sigma_i^2 \norm{\widetilde{\mat V}[:,i]}^2 \\
	&\le \epsilon^2 + 2 \left(3\norm{\mat M^*}_F\right)^2
	\le 19 \norm{\mat M^*}_F^2.
	\end{align*}
	Then by the Cauchy-Schwarz inequality we have
	\begin{align*}
	\norm{\mat U}_F^2 = \sum_{i=1}^r \sigma_i^2
	\le \sqrt{r \sum_{i=1}^r \sigma_i^4}
	\le \sqrt{r\cdot 19 \norm{\mat M^*}_F^2}
	\le 5\sqrt{r} \norm{\mat M^*}_F.
	\end{align*}
	Similarly, we also have $\norm{\mat V}_F^2 \le 5\sqrt{r} \norm{\mat M^*}_F$. Therefore we have proved \eqref{eqn:mf-inproof-toshow-1}.
\end{proof}


\subsection{Convergence to a Stationary Point}

With the balancedness and boundedness properties in Lemma~\ref{lem:mf-balance}, it is then standard to show that $(\mat U_t, \mat V_t)$ converges to a stationary point of $f$.

\begin{lem} \label{lem:mf-convergence}
	Under the setting of Theorem~\ref{thm:mf-main}, with high probability $\lim_{t\to\infty}(\mat U_t, \mat V_t) = (\bar{\mat U}, \bar{\mat V})$ exists, and $(\bar{\mat U}, \bar{\mat V})$ is a stationary point of $f$.
	Furthermore, $(\bar{\mat U}, \bar{\mat V})$ satisfies $\norm{\bar{\mat U}^\top \bar{\mat U} - \bar{\mat V}^\top \bar{\mat V}}\le \epsilon$.
\end{lem}
\begin{proof}
	We assume the three properties in Lemma~\ref{lem:mf-balance} hold, which happens with high probability.
	Then from \eqref{eqn:mf-obj-decrease} we have
	\begin{equation}\label{eqn:mf-obj-decrease-2}
	\begin{aligned}
	f(\mat U_{t+1}, \mat V_{t+1})
	&\le f(\mat U_{t}, \mat V_{t}) - \frac{\eta_t}{2} \norm{ \nabla f(\mat U_t, \mat V_t) }_F^2 \\
	&= f(\mat U_{t}, \mat V_{t}) - \frac{1}{2} \norm{ \nabla f(\mat U_t, \mat V_t) }_F \norm{\begin{pmatrix}
		\mat U_{t+1} \\ \mat V_{t+1}
		\end{pmatrix} - \begin{pmatrix}
		\mat U_{t} \\ \mat V_{t}
		\end{pmatrix}}_F .
	\end{aligned}
	\end{equation}
	Under the above descent condition, the result of \cite{absil2005convergence} says that the iterates either diverge to infinity or converge to a fixed point.
	According to Lemma~\ref{lem:mf-balance}, \{$(\mat U_t, \mat V_t)\}_{t=1}^\infty$ are all bounded, so they have to converge to a fixed point $(\bar{\mat U}, \bar{\mat V})$ as $t\to\infty$.
	
	Next, from \eqref{eqn:mf-obj-decrease-2} we know that $\sum_{t=1}^\infty \frac{\eta_t}{2} \norm{ \nabla f(\mat U_t, \mat V_t) }_F^2 \le f(\mat U_0, \mat V_0)$ is bounded.
	Notice that $\eta_t$ scales like $1/t$. So we must have $\liminf_{t\to\infty} \norm{ \nabla f(\mat U_t, \mat V_t) }_F = 0$.
	Then according to the smoothness of $f$ in a bounded region (Lemma~\ref{lem:mf-local-smooth}) we conclude $ \nabla f(\bar{\mat U}, \bar{\mat V})  = \mat0$, i.e., $(\bar{\mat U}, \bar{\mat V})$ is a stationary point.
	
	The second part of the lemma is evident according to Lemma~\ref{lem:mf-balance} (i).
\end{proof}


\subsection{Proof of Lemma~\ref{lem:mf-strict-saddle}}

The main idea in the proof is similar to \cite{ge2017no}. We want to find a direction $\mat \Delta$ such that either $[\nabla^2 f(\mat U, \mat V)] (\mat \Delta, \mat \Delta)$ is negative or $(\mat U, \mat V)$ is close to a global minimum. We show that this is possible when $\norm{\mat U^\top \mat U - \mat V^\top \mat V}_F \le \epsilon$.

First we define some notation.
Take the SVD $\mat M^* = \mat \Phi^* \mat \Sigma^* \mat \Psi^{*\top}$, where $\mat \Phi^* \in \R^{d_1\times r}$ and $\mat \Psi^* \in \R^{d_2\times r}$ have orthonormal columns and $\mat \Sigma^* \in \R^{r\times r}$ is diagonal.
Denote $\mat U^* = \mat \Phi^*  (\mat \Sigma^*)^{1/2}$ and $\mat V^* = \mat \Psi^*  (\mat \Sigma^*)^{1/2}$.
Then we have $\mat U^* \mat V^{*\top} = \mat M^*$ (i.e., $(\mat U^*, \mat V^*)$ is a global minimum) and $\mat U^{*\top} \mat U^* = \mat V^{*\top} \mat V^*$.

Let $\mat M = \mat U \mat V^\top$, $\mat W = \begin{pmatrix}
\mat U\\ \mat V
\end{pmatrix}$ and $\mat W^* = \begin{pmatrix}
\mat U^*\\ \mat V^*
\end{pmatrix}$.
Define $$\mat{R} = \argmin_{\mat R' \in \R^{r\times r} \text{, orthogonal}} \norm{\mat W - \mat W^* \mat R'}_F$$
and
\[
\mat\Delta = \mat W - \mat W^* \mat R.
\]

We will show that $\mat\Delta$ is the desired direction.
Recall \eqref{eqn:mf-hessian}:
\begin{equation} \label{eqn:mf-hessian-to-bound}
\begin{aligned}  \
[\nabla^2 f(\mat U, \mat V)] (\mat \Delta, \mat \Delta)
= 2 \left\langle \mat M - \mat M^*, \mat\Delta_{\mat U} \mat{\Delta}_{\mat V}^\top \right\rangle + \norm{\mat U \mat\Delta_{\mat V}^\top  + \mat\Delta_{\mat U} \mat V^\top }_F^2, 
\end{aligned}
\end{equation}
where $ \mat \Delta = \begin{pmatrix}
\mat \Delta_{\mat U} \\ \mat{\Delta}_{\mat V}
\end{pmatrix}, 
\mat \Delta_{\mat U} \in \R^{d_1\times r}, \mat \Delta_{\mat V} \in \R^{d_2\times r}$.
We consider the two terms in \eqref{eqn:mf-hessian-to-bound} separately.

For the first term in \eqref{eqn:mf-hessian-to-bound}, we have:
\begin{claim} \label{claim:mf-hessian-to-bound-1}
	$\left\langle \mat M - \mat M^*, \mat\Delta_{\mat U} \mat{\Delta}_{\mat V}^\top \right\rangle  = -\norm{\mat M - \mat M^*}_F^2$.
\end{claim}
\begin{proof}
	Since $(\mat U, \mat V)$ is a stationary point of $f$, we have the first-order optimality condition:
	\begin{equation} \label{eqn:mf-inproof-first-order-opt-cond}
	\frac{\partial f(\mat U, \mat V)}{\partial \mat U} = (\mat M - \mat M^*) \mat V = \mat0, \qquad
	\frac{\partial f(\mat U, \mat V)}{\partial \mat V} = (\mat M - \mat M^*)^\top \mat U = \mat0.
	\end{equation}

Note that $\mat \Delta_{\mat U} = \mat U - \mat U^* \mat R$ and $\mat \Delta_{\mat V} = \mat V - \mat V^* \mat R$.
We have
\begin{align*}
&\left\langle \mat M - \mat M^*, \mat\Delta_{\mat U} \mat{\Delta}_{\mat V}^\top \right\rangle \\
=\,& \left\langle \mat M - \mat M^*, (\mat U - \mat U^* \mat R) (\mat V - \mat V^* \mat R)^\top \right\rangle \\
=\,& \left\langle \mat M - \mat M^*, \mat M - \mat U^* \mat R \mat V^\top - \mat U \mat R^\top \mat V^{*\top} + \mat M^*  \right\rangle \\
=\,& \left\langle \mat M - \mat M^*, \mat M^*\right\rangle \\
=\,& \left\langle \mat M - \mat M^*, \mat M^* - \mat M \right\rangle \\
=\,& -\norm{\mat M - \mat M^*}_F^2,
\end{align*}
where we have used the following consequences of \eqref{eqn:mf-inproof-first-order-opt-cond}:
\begin{align*}
&\left\langle \mat M - \mat M^*, \mat M \right\rangle = \left\langle \mat M - \mat M^*, \mat U \mat V^\top \right\rangle = 0, \\
&\left\langle \mat M - \mat M^*, \mat U^* \mat R \mat V^\top \right\rangle  = 0, \\
&\left\langle \mat M - \mat M^*, \mat U \mat R^\top \mat V^{*\top}  \right\rangle  = 0.
\end{align*}
\end{proof}

The second term in \eqref{eqn:mf-hessian-to-bound} has the following upper bound:
\begin{claim} \label{claim:mf-hessian-to-bound-2}
$\norm{\mat U \mat\Delta_{\mat V} + \mat\Delta_{\mat U} \mat V}_F^2 \le \norm{\mat M - \mat M^*}_F^2 + \frac12 \epsilon^2 $.
\end{claim}
\begin{proof}
	We make use of the following identities, all of which can be directly verified by plugging in definitions:
	\begin{equation} \label{eqn:mf-inproof-identity-1}
	\mat U \mat\Delta_{\mat V}^\top + \mat\Delta_{\mat U} \mat V^\top = \mat\Delta_{\mat U} \mat\Delta_{\mat V}^\top + \mat M - \mat M^*,
	\end{equation}
	\begin{equation} \label{eqn:mf-inproof-identity-2}
	\norm{\mat{\Delta} \mat{\Delta}^\top}_F^2 = 4 \norm{\mat\Delta_{\mat U} \mat\Delta_{\mat V}^\top}_F^2 + \norm{\mat\Delta_{\mat U}^\top\mat\Delta_{\mat U} - \mat\Delta_{\mat V}^\top \mat\Delta_{\mat V}}_F^2,
	\end{equation}
	\begin{equation} \label{eqn:mf-inproof-identity-3}
	\begin{aligned}
	\norm{\mat W \mat W^\top - \mat W^* \mat W^{*\top}}_F^2 =\ & 4\norm{\mat M - \mat M^*}_F^2 - 2 \norm{\mat U^\top \mat U^* - \mat V^\top \mat V^*}_F^2 \\&+ \norm{\mat U^\top \mat U - \mat V^\top \mat V}_F^2 + \norm{\mat U^{*\top} \mat U^* - \mat V^{*\top} \mat V^*}_F^2.
	\end{aligned}
	\end{equation}
	We also need the following inequality, which is \citep[Lemma 6]{ge2017no}:
	\begin{equation} \label{eqn:mf-inproof-rong-ineq}
	\norm{\mat{\Delta} \mat{\Delta}^\top}_F^2 \le 2 \norm{\mat W \mat W^\top - \mat W^* \mat W^{*\top}}_F^2.
	\end{equation}
	
	Now we can prove the desired bound as follows:
	\begin{align*}
	& \norm{\mat U \mat\Delta_{\mat V} + \mat\Delta_{\mat U} \mat V}_F^2 \\
	=\, & \norm{\mat\Delta_{\mat U} \mat\Delta_{\mat V}^\top + \mat M - \mat M^*}_F^2 & (\eqref{eqn:mf-inproof-identity-1}) \\
	=\,& \norm{\mat\Delta_{\mat U} \mat\Delta_{\mat V}^\top }_F^2 + 2 \left\langle \mat M - \mat M^*, \mat\Delta_{\mat U} \mat{\Delta}_{\mat V}^\top \right\rangle  + \norm{\mat M - \mat M^*}_F^2 \\	
	=\,& \norm{\mat\Delta_{\mat U} \mat\Delta_{\mat V}^\top }_F^2 - \norm{\mat M - \mat M^*}_F^2 & (\text{Claim~\ref{claim:mf-hessian-to-bound-1}})\\
	\le\, & \frac14 \norm{\mat{\Delta} \mat{\Delta}^\top}_F^2 - \norm{\mat M - \mat M^*}_F^2  & (\eqref{eqn:mf-inproof-identity-2}) \\
	\le\, & \frac12 \norm{\mat W \mat W^\top - \mat W^* \mat W^{*\top}}_F^2  - \norm{\mat M - \mat M^*}_F^2  & (\eqref{eqn:mf-inproof-rong-ineq}) \\
	=\, & 2\norm{\mat M - \mat M^*}_F^2 -  \norm{\mat U^\top \mat U^* - \mat V^\top \mat V^*}_F^2  + \frac12\norm{\mat U^\top \mat U - \mat V^\top \mat V}_F^2 \\& + \frac12\norm{\mat U^{*\top} \mat U^* - \mat V^{*\top} \mat V^*}_F^2 - \norm{\mat M - \mat M^*}_F^2 & (\eqref{eqn:mf-inproof-identity-3}) \\
	\le\,& \norm{\mat M - \mat M^*}_F^2 + \frac12 \epsilon^2,
	\end{align*}
	where in the last line we have used $\mat U^{*\top} \mat U^* = \mat V^{*\top} \mat V^*$ and $\norm{\mat U^{\top} \mat U - \mat V^{\top} \mat V} \le \epsilon$.
\end{proof}


Using Claims~\ref{claim:mf-hessian-to-bound-1} and \ref{claim:mf-hessian-to-bound-2}, we obtain an upper bound on \eqref{eqn:mf-hessian-to-bound}:
\begin{align*}
[\nabla^2 f(\mat U, \mat V)] (\mat \Delta, \mat \Delta) \le -\norm{\mat M - \mat M^*}_F^2 + \frac12 \epsilon^2.
\end{align*}
Therefore, we have either $\norm{\mat U \mat V^\top - \mat M^*}_F = \norm{\mat M - \mat M^*}_F \le \epsilon$ or $[\nabla^2 f(\mat U, \mat V)] (\mat \Delta, \mat \Delta) \le -\frac12 \epsilon^2 <0$.
In the latter case, $(\mat U, \mat V)$ is a strict saddle point of $f$.
This completes the proof of Lemma~\ref{lem:mf-strict-saddle}.


\subsection{Finishing the Proof of Theorem~\ref{thm:mf-main}}

Theorem~\ref{thm:mf-main} is a direct corollary of Lemma~\ref{lem:mf-convergence}, Lemma~\ref{lem:mf-strict-saddle}, and the fact that gradient descent does not converge to a strict saddle point almost surely \citep{lee2016gradient, panageas2016gradient}.
{"config": "arxiv", "file": "1806.00900/proof_mf.tex"}