\section{Proofs of the lemmas} \label{lemmas_proofs}


We provide the real measurements case proof here, and postpone the extra steps for the complex case to Appendix \ref{proofs_complex}. 


Without loss of generality, as done in past works on PR, e.g., \cite{pr_altmin,lrpr_it}, for simplicity, at some places, we assume that $\xstar_k$ is replaced by $\bar{z} \xstar_k$ where $z = \mathrm{phase}(\langle \xstar_k, \xhat_k \rangle)$. Here $\mathrm{phase}(z):= z/|z|$ and $\bar{z}$ denotes its complex conjugate. With this,  $\dist(\xstar_k, \xhat_k) = \|\xstar_k - \xhat_k\|$.  A similar replacement can be done for each column of $\Xhat$ as well so that $\matdist(\Xstar,\Xhat) = \|\Xstar - \Xhat\|_F$. This point is explained carefully in \cite{lrpr_it}, Appendix A-C.


Our proofs rely on the sub-exponential Bernstein inequality (Theorem 2.8.1 of \cite{versh_book}) and the fact that the product of two sub-Gaussians $X,Y$ with sub-Gaussian norms $K_X, K_Y$ is sub-exponential with sub-exponential norm $K_X K_Y$ (Lemma 2.7.7 \cite{versh_book}). We state this as the following concentration bound:

\begin{lemma}[Lemma 2.7.7 and Theorem 2.8.1 of \cite{versh_book}] 
	\label{prodsubg}
\label{productsubg}
	Let $X_{i}, Y_{i}$, $i=1,2,\dots, N$, be sub-Gaussian random variables with sub-Gaussian norms $K_{X_i}$ and $K_{Y_i}$ respectively and with $\E[X_iY_i] = 0$ and the pairs $\{X_i,Y_i\},i=1,2,\dots,N$ mutually independent for different $i$. Then
	\begin{align*}
		\Pr \left\lbrace   |\sum_{i}^N   X_i Y_i | \geq t \right\rbrace
	 \leq 2\exp{\left( -c \min{\left(\frac{t^2}{\sum_i K_{X_i}^2 K_{Y_i}^2 }, \frac{t}{\max_i{|K_{X_i}K_{Y_i} |}} \right) } \right)}.
	\end{align*}


\end{lemma}


\subsection{Proof of Lemma \ref{key_lem_SEF}} \label{proof_key_lem}
The proof is almost the same as that of   Lemma 3.9 of \cite{lrpr_it} given in Appendix B in \cite{lrpr_it}.
As shown in equation (21) in that proof,
\begin{equation}
\Uhat^{t+1} =  \Xstar  \B^\top  - \F . 
\label{Uhat_express}
\end{equation}
with $\F$ being the $n \times r$ matrix version of the $nr$-length vector $\F_{vec}$ defined in the proof. As shown in equations (24)-(27) of the proof,
\begin{equation}
\|\F_{vec}\| \le  \frac{\max_{\W \in \S_{\W}} |\mathrm{Term1}(\W)| + \max_{\W \in \S_{\W}} |\mathrm{Term2}(\W)|}{\min_{\W \in \S_{\W}} |\mathrm{Term3}(\W)|}:=   \mathrm{MainTerm}.
\label{Fvec_bnd}
\end{equation}
Consequently, using \eqref{Uhat_express},
\[
||(\I - \Ustar \Ustar{}^\top) \Uhat^{t+1}||_F = \|\F\|_F = \|\F_{vec}\| \le \mathrm{MainTerm}
\]
Since $ \Uhat^{t+1} \qreq \U^{t+1} \R_U^{t+1}$, this means that $$\SE_F(\Ustar,\U^{t+1}) \le \mathrm{MainTerm} \ ||\R_U^{-1}|| = \frac{\mathrm{MainTerm}}{ \sigma_{\min}(\R_U)}.$$
Using $\sigma_{\min}(\R_U) = \sigma_{\min}(\Uhat^{t+1})$ and \eqref{Uhat_express},   $\sigma_{\min}(\R_U) = \sigma_{\min}(\Xstar \B^\top  - \F) \ge \sigma_{\min}(\Xstar \B^\top ) - \|\F\| \ge  \sigma_{\min}(\Xstar \B^\top ) - \|\F\|_F =
\sigma_{\min}( \Xstar \B^\top ) - \|\F_{vec}\| \ge \sigma_{\min}( \Xstar \B^\top ) - \mathrm{MainTerm} $.  
Thus,
\begin{align}\label{eq:se_1}
\SE_F(\Ustar,\U_{t+1}) 
\le \frac{ \mathrm{MainTerm}}{  \sigma_{\min}(\Xstar \B^\top ) -  \mathrm{MainTerm}}
\end{align}


\subsection{Proof of Lemma \ref{Terms_bnds}: Term1 bound}\label{proof_Terms_bnds_1}
Let 
\begin{align*}
\p_k := \Xstar \B^\top  \b_k - \xstar_k , \text{ and }  \P  := [\p_1, \p_2, \dots, \p_q] =  \Xstar ( \B^\top  \B - \I).
\end{align*}
Recall that
$
	\mathrm{Term1}(\W)= \sum_{ik} \b_k{}^\top  \W{}^\top  \a_{ik} \a_{ik}{}^\top   \p_k.
$
The main change from \cite{lrpr_it} is the fact that we now obtain a tighter upper bound on $\|\p_k\|, \|\P\|_F$ that relies on our tighter bound on $\|\Xstar - \Xhat\|_F$ given in Lemma \ref{B_lemma}.

First, as done in the proof of Lemma 3.11 of \cite{lrpr_it} \footnote{$\E[\mathrm{Term1}(\W)] = \E[\trace(\mathrm{Term1}(\W)] =  \E[\trace(\W{}^\top  \sum_\ik \a_{ik} \a_{ik}{}^\top   \p_k \b_k{}^\top )] =  m \trace(\W{}^\top  \sum_k \p_k \b_k{}^\top )]$. Since $\B\B^\top  =I$, $\sum_k \p_k \b_k{}^\top  = \Xstar \B^\top  \B \B^\top  - \Xstar \B^\top  =  \bm{0}$.},
\[
\E[\mathrm{Term1}(\W)]=0.
\]
Next, we bound $\|\p_k\|$ and $\|\P\|_F$. 

Observe that $\Xhat = \U \Bhat$ with $\Bhat \qreq \R_B \B$. Since $\B \B^\top  = I$, this means that  
\[
\Xhat \B^\top  \b_k = \U \R_B \B \B^\top  b_k = \U \R_B \b_k = \U \hat\b_k = \xhat_k
\]
Thus, by Lemma \ref{B_lemma},


\begin{align}
\|\p_k\|& = \|\Xstar \B^\top  \b_k - \Xhat \B^\top  \b_k   + \xhat_k - \xstar_k\|  \nonumber \\
& \le \|\Xstar - \Xhat\| \ \|\B\| \ \|\b_k\| + \|\xstar_k - \xhat_k\|  \nonumber \\
& \le \|\Xstar - \Xhat\|_F   \|\b_k\| +  C \deltatfrob \|\xstar_k\|  \nonumber \\

& \le C\deltatfrob \sigmax \max(\|\bstar_k\|, \|\b_k\|) \le  C \deltatfrob \sigmax  ( \kappa  \mu  \sqrt{r/q} )
\end{align}
Using $\Xhat = \U \Bhat = \U \R_B \B$, $\B(\B^\top \B - \I) = 0$, $\|\B\B^\top  - \I\| \le 2$, and $\|\P \M\|_F \le \|\P\| \|\M\|_F$,
\begin{align}
\|\P\|_F
& = \|(\Xstar - \Xhat + \Xhat)(\B^\top \B - \I)\|_F \nonumber  \\
& =  \|(\Xstar - \Xhat)(\B^\top \B - \I)\|_F  \le 2 \|\Xstar - \Xhat\|_F  \le  C \deltatfrob \sigmax
\label{P_bnd_SEF}
\end{align}


	
	
Let $X_{ik} = \a_{ik}^\top  \W \b_k$ and $Y_{ik} =\a_{ik}^\top  \p_k$. Both are sub-Gaussian with sub-Gaussian norms $K_{X_{ik}} = \|\W\b_k\| \leq \|\W\|_F \|\b_k\| \le \|\b_k\|$, and $K_{Y_{ik}}\leq  \|\p_k \| $.

Applying Lemma \ref{productsubg} with $t = m \epsilon_1 \deltatfrob \sigmax$, and using the bounds on $\|\p_k\|$, $\|\P\|_F$,
	\begin{align*}
		\frac{t^2}{\sum_{ik} K_{X_{ik}}^2 K_{Y_{ik}}^2}
		& = \frac{m^2 \epsilon_1^2  \deltatfrob^2 \sigmax^2}{m \sum_k \|\b_k\|^2  \|\p_k \|^2}

= c \frac{m  \epsilon_1^2 \deltatfrob^2  \sigmax^2}{ \max_k \|\b_k\|^2 \|\P\|_F^2}

 \ge c \frac{mq  \epsilon_1^2}{\kappa^2 \mu^2 \ r}, \\
	
		\frac{t}{\max_\ik K_{X_{ik}} K_{Y_{ik}}}
		& = \frac{m \epsilon_1 \deltatfrob \sigmax}{\max_k \|\b_k\| \|\p_k \|}
		
  =  c \frac{mq \epsilon_1}{\kappa^2 \mu^2 r}
		
		
	\end{align*}
and, hence,
	\[
	\Pr \lbrace |\mathrm{Term1}(\W)| \le m \epsilon_1 \deltatfrob \sigmax \rbrace \ge 1 -  \exp\left( - c \frac{mq  \epsilon_1^2}{\kappa^2 \mu^2 \ r} \right)
	\]
Now we just need to extend our bound for all $\W \in \S_W$ by developing an epsilon-net argument.
This part is exactly analogous to the Term1 bound proof from \cite{lrpr_it} except we now use $|\mathrm{Term1}(\W)| \le m \epsilon_1 \deltatfrob \sigmax$ instead of
$|\mathrm{Term1}(\W)| \le m \epsilon_1 \delta_t \sqrt{r} \sigmax$.

Thus,  w.p. at least $1 - 2 \exp\left(nr (\log 17) -c \frac{mq \epsilon_1^2}{\kappa^2 \mu^2 r} \right) - \exp(\log q + r - c m )$,
$
\max_{\W \in \S_{W}} |\mathrm{Term1}(\W)|  \le C m \epsilon_1 \deltatfrob \sigmax.
$


\subsection{Proof of Lemma \ref{Terms_bnds}: Bound on Term2 for real measurements}\label{proof_Terms_bnds_2}
We have $\mathrm{Term2}(\W)  :=  \sum_{ik} (\bar{\cb^*_\ik}  \hat\cb_\ik - 1) ( \a_\ik{}^\top  \xstar_k) (\a_\ik{}^\top  \W \b_k) = \sum_{ik} (\hat\cb_\ik - {\cb^*_\ik})  | \a_\ik{}^\top  \xstar_k | (\a_\ik{}^\top  \W \b_k)$ and so
\[
|\mathrm{Term2}(\W) |
= |\sum_{ik} (\hat\cb_\ik - {\cb^*_\ik})  | \a_\ik{}^\top  \xstar_k | (\a_\ik{}^\top  \W \b_k) |
\le \sum_{ik} |\hat\cb_\ik - {\cb^*_\ik}|  | \a_\ik{}^\top  \xstar_k | |\a_\ik{}^\top  \W \b_k| := \mathrm{Term2abs}(\W)
\]


\subsubsection{Bounding $\E[\mathrm{Term2abs}(\W)]$}
Using the Cauchy-Schwarz inequality,
\begin{align}
\E[\mathrm{Term2abs}(\W)]^2 \le \sum_{ik} \E[(\hat\cb_\ik - {\cb^*_\ik})^2  (\a_\ik{}^\top  \xstar_k )^2 ] \ \sum_{ik} \E[|\a_\ik{}^\top  \W \b_k|^2]
\label{cauchy_1}
\end{align}

As also shown in the proof of Lemma 3.10 of \cite{lrpr_it}, using $\B \B^\top = \I$ and $\|\W\|_F = 1$,
\[
 \sum_{ik}\E[(\a_\ik{}^\top  \W \b_k)^2] = m \sum_k \|\W \b_k\|^2 = m \|\W \B\|_F^2   = m  
\]
Consider the first term in \eqref{cauchy_1} and let
\begin{align}
Q_\ik:= |(\hat\cb_\ik - \cb^*_\ik)   (\a_\ik{}^\top  \xstar_k )|^2 = \indic_{ \cb^*_\ik \neq \hat\cb_\ik } (\a_\ik{}^\top  \xstar_k )^2
\label{def_Q_ik}
\end{align}
denote its one summand. We get the second equality because, for real measurements, phase = sign.


We proved the following in the proof of Lemma 3.12 (Term2 bound proof) of  \cite{lrpr_it}. We state it as a lemma to keep things clear
\begin{lemma}[Real measurements \cite{lrpr_it}]
\[
\E[\Q_\ik] = \E[\indic_{ \cb^*_\ik \neq \hat\cb_\ik }  (\a_\ik{}^\top  \xstar_k )^2] \le C \frac{\dist(\xstar_k,\xhat_k)^3}{\|\xstar_k\|}.
\]
\end{lemma}
\begin{proof} See the few equations above equation (20) of \cite{lrpr_it} (in its proof of Term2 bound). \end{proof}

By the above lemma and Lemma \ref{B_lemma},
\begin{align}
  \sum_{ik} \E[ \indic_{ \cb^*_\ik \neq \hat\cb_\ik }  (\a_\ik{}^\top  \xstar_k )^2 ]
 & \le C m \sum_k \frac{\dist(\xstar_k,\xhat_k)^3}{\|\xstar_k\|}  \nonumber \\

& \le  C m \max_k \frac{\dist(\xstar_k,\xhat_k)}{\|\xstar_k\|} \matdist(\Xstar, \Xhat)^2
 =  C m \deltatfrob   \deltatfrob^2 \sigmax^2
\label{tight_Qik}
\end{align}
Notice how this bound is tighter by a factor of $r$ than that of (20) of \cite{lrpr_it}.

Combining the previous equations,
\begin{align}
\E[\mathrm{Term2abs}(\W)] \le  C m \sqrt{\deltatfrob} \cdot \deltatfrob  \sigmax  
\label{ETerm2}
\end{align}

\subsubsection{Concentration bounds}
Unlike in \cite{lrpr_it}, here we use Cauchy-Schwarz to only bound the expectation as done above, while applying the concentration bound, Lemma \ref{prodsubg}, directly to $|\mathrm{Term2abs}(\W) - \E[\mathrm{Term2abs}(\W)]|$. 

For real measurements,
\[
\mathrm{Term2abs}(\W) =  \sum_{ik}  \indic_{ \cb^*_\ik \neq \hat\cb_\ik }  | \a_\ik{}^\top  \xstar_k | |\a_\ik{}^\top  \W \b_k|
\]
We use the fact that \cite{rwf}\footnote{
let $\h_k= \xstar_k - \xhat_k$, $(\a_{ik}{}^\top  \xstar_k)(\a_{ik}{}^\top  \xhat_k) < 0$ implies  $(\a_{ik}{}^\top  \xstar_k)(\a_{ik}{}^\top  \xstar_k ) - (\a_{ik}{}^\top  \xstar_k)(\a_{ik}{}^\top  \h_k) < 0$ and hence $|\a_{ik}{}^\top  \xstar_k| < |\a_{ik}{}^\top  \h_k|$.}
$\cb^*_\ik \neq \hat{\cb}_\ik$ implies that $|\a_{ik}{}^\top  \xstar| < |\a_{ik}{}^\top  (\xstar_k - \xhat_k)|$. Consequently,
\[

\indic_{ \cb^*_\ik \neq \hat\cb_\ik } | \a_\ik{}^\top  \xstar_k |  \leq 2 \lvert \a_{ik}{}^\top  (\xstar_k - \xhat_k) \rvert
\]
Let $X_{ik} = \indic_{ \cb^*_\ik \neq \hat\cb_\ik } | \a_\ik{}^\top  \xstar_k |  $, 	and  $Y_{ik} = \a_{ik}{}^\top \W \b_k$. Using above,

 $K_{X_{ik}} \leq C {\|\xstar_k - \xhat_k\|}$. Also, $K_{Y_{ik}} = C\|\W\b_k\|$.

We will apply Lemma \ref{prodsubg} with $t= m \epsilon_2 \deltatfrob \sigmax$. Using $\|\W \B\|_F^2 = 1$ and Lemma \ref{B_lemma},
	\begin{align*}
\frac{t^2}{\sum_\ik K_{X_\ik}^2  K_{Y_\ik}^2}
	& =  \frac{m^2 \epsilon_2^2 \deltatfrob^2 \sigmax^2}{\sum_{ik} \|\W \b_k\|^2 \|\xstar_k - \xhat_k\|^2 }
  \geq \frac{m \epsilon_2^2\deltatfrob^2 \sigmax^2}{\max_k \|\xstar_k - \xhat_k\|^2 \sum_{k} \|\W \b_k\|^2  }
	
	 \geq c  \frac{m q\epsilon_2^2}{\mu  r},  \\

\frac{t}{\max_\ik K_{X_\ik}  K_{Y_\ik}} 	

	& \geq \frac{m \epsilon_2\deltatfrob \sigmax  }{  \max_{k} \|\W \b_k\| \max_k \|\xstar_k - \xhat_k \| }
	 \geq c \frac{m \epsilon_2\deltatfrob \sigmax  }{ ( \mu \kappa  \sqrt{r/q})  (\mu \deltatfrob \sigmax \sqrt{r/q} ) }
	 =  c\frac{mq \epsilon_2  }{ \mu^2 \kappa r }
	\end{align*}
Since $\min\left( \frac{m q\epsilon_2^2}{\mu  r},\frac{mq \epsilon_2  }{ \mu^2 \kappa r } \right)  = \frac{m q\epsilon_2^2}{ \mu^2 \kappa  r}$, applying Lemma \ref{prodsubg},
\begin{align*}
\Pr \left( | \mathrm{Term2abs}(\W) -\E[\mathrm{Term2abs}(\W)]|  \leq C m \epsilon_2  \deltatfrob \sigmax   \right)
	\geq  1-  2 \exp\left( - c \frac{m q\epsilon_2^2}{ \mu^2 \kappa  r} \right).
\end{align*}
Using \eqref{ETerm2},  this implies that, w.p. at least $1-  2 \exp\left( - c \frac{m q\epsilon_2^2}{ \mu^2 \kappa  r} \right)$,
\[
|\mathrm{Term2abs}(\W)|  \leq C m ( \epsilon_2  +   \sqrt{\deltatfrob} ) \deltatfrob \sigmax  .
\]

Finally, we just need an epsilon-net argument to extend the above bound to all unit Frobenius norm matrices $\W$. This is pretty standard. We provide it here for completion. 

\subsubsection{Epsilon-net argument (pretty standard)}
By Lemma 5.2 of  \cite{vershynin} there exists a set (called epsilon-net), $\bar{\S}_W \subset \S_W$ so that, for any $\W \in \S_W$, there is a $\bar{\W} \in \bar{\S}_W$ such that $\|\bar{\W} - \W\|_F \leq \epsilon_{net}$ and $\lvert \bar{\S}_W \rvert \leq \left( 1+\frac{2}{\epsilon_{net}} \right)^{nr}$. By picking $\epsilon_{net} =1/8$ we have $\lvert \bar{\S}_W \rvert \leq (17)^{nr}$. Define $\Delta\W := \W - \bar{\W}$ so that $\|\Delta\W\|_F \leq \epsilon_{net} = \frac{1}{8}$. Using union bound for all entries in $\bar{\S}_W$,
	\begin{align}
	
	\Pr\left\{ \mathrm{Term2abs}(\bar{\W}) \leq  C m ( \epsilon_2  +   \sqrt{\deltatfrob} ) \deltatfrob \sigmax \ \text{for all $\bar\W \in \bar\S_W$}  \right\}
	
	& \geq 1-  2 \exp\left( nr \log(17)   - c \frac{m q\epsilon_2^2}{ \mu^2 \kappa  r} \right).
\label{Term2_epsnet}
	\end{align}
	Next we extend this for the entire hyper-sphere, $\S_W$. Define $\Gamma_W := \max_{\W \in \S_W}  \mathrm{Term2abs}(\W) $.
	Since $\frac{\Delta\W}{\|\Delta\W\|_F} \in \S_W$, 


using \eqref{Term2_epsnet},  for any $\W \in \S_W$,
w.p. at least $1-  2 \exp\left( nr \log(17)   - c \frac{m q\epsilon_2^2}{ \mu^2 \kappa  r} \right)$,

	\begin{align*}
	\mathrm{Term2abs}(\W) 
	& =   \sum_{ik} |\hat{\cb}_{ik} - \cb^*_{ik}|  | \a_{ik}{}^\top  \xstar_k | |\b_k{} ^\top (\bar{\W} + \Delta\W)^\top  \a_{ik}|  \\
	
	& \leq  C m ( \epsilon_2  +   \sqrt{\deltatfrob} )  \deltatfrob \sigmax  + \Gamma_W \|\Delta\W\|_F  \le C m ( \epsilon_2  +   \sqrt{\deltatfrob} )  \deltatfrob \sigmax + \Gamma_W \epsilon_{net}
	\end{align*}
where we used $\|\Delta\W\|_F \le \epsilon_{net}$ in the last bound.
Taking $\max$ over ${\W \in \S_W}$ on both sides,
\[
\Gamma_W = \max_{\W \in \S_W} \mathrm{Term2abs}(\W)  \le C m ( \epsilon_2  +   \sqrt{\deltatfrob} )  \deltatfrob \sigmax + \epsilon_{net} \Gamma_W
\]
and so  $ \Gamma_W \leq \frac{ C m ( \epsilon_2  +   \sqrt{\deltatfrob} )  \deltatfrob \sigmax }{1-\epsilon_{net}} = \frac{8}{7} C  m ( \epsilon_2  +   \sqrt{\deltatfrob} )  \deltatfrob \sigmax$ since we set $\epsilon_{net} = 1/8$.

Thus, using  $|\mathrm{Term2}(\W) | \le \mathrm{Term2abs}(\W)$,
w.p. at least  $1-  2 \exp\left( nr \log(17)   - c \frac{m q\epsilon_2^2}{ \mu^2 \kappa  r} \right) -   \exp(\log q + r - c m )$,
\[
\max_{\W \in \S_W} |\mathrm{Term2}(\W)| \le   C m ( \epsilon_2  +   \sqrt{\deltatfrob} )  \deltatfrob \sigmax.
\]

\subsection{Proof of Lemma \ref{Terms_bnds}: Lower bound on Term3}\label{proof_Terms_bnds_3}
This proof is the same as that of Lemma 3.10 of \cite{lrpr_it}. It uses the last claim of Lemma \ref{B_lemma} ($\b_k$s are $\hat\mu$-incoherent).


\subsection{Proof of Lemma \ref{Terms_bnds}: Lower bound on $\sigma_{\min}(\Xstar \B^\top )$}\label{proof_Terms_bnds_4}
$\sigma_{\min}(\Xstar \B^\top) \ge \sigma_{\min}(\Ustar \bSigma) \sigma_{\min}(\Bstar) \sigma_{\min}(\B^\top) = \sigmin$ since $\sigma_{\min}(\B) = \sigma_{\min}(\Bstar)=1$ (both are basis matrices).


\subsection{Proof of Lemma \ref{B_lemma}, part 1: Bound on $\|\g_k - \bhat_k\|$, $\|\G - \Bhat\|_F$ and $\|\Xstar - \Xhat\|_F$} \label{proof_B_bnds_1}


Recall that $\g_k = \U^\top \xstar_k$, and with this $\y_\ik =  |\a_\ik{}^\top  \U \g_k + \a_\ik{}^\top  (\I - \U \U^\top ) \xstar_k|$.
Thus, we can write
	\begin{align*}
	\y_\ik & = \lvert \a_{ik}{}^\top  \U g_k \rvert + \nu_{ik}, \text{ with }  \\
\nu_{ik} & =   |\a_\ik{}^\top  \U \g_k + \a_\ik{}^\top  (\I - \U \U^\top ) \xstar_k| - \lvert \a_{ik}{}^\top  \U \g_k \rvert
\end{align*}
Hence recovering $\g_k$ from $\y_\ik$s, $i \in [m]$, is a noisy $r$-dimensional standard PR problem with
\begin{align*}
\|\bnu_k\|^2 := \sum_{i} \nu_{ik}^2 \le \sum_{i}  |\a_\ik{}^\top  (\I - \U \U^\top ) \xstar_k|^2.
\end{align*}
	
Since both LHS and RHS are non-negative, we can take $\E[.]$ on both sides to conclude that
\[
\E[\|\bnu_k\|^2 ] \le \E[ |\a_\ik{}^\top  (\I - \U \U^\top ) \xstar_k|^2] =  m \|  (\I - \U \U^\top ) \xstar_k\|^2 = m \|  (\I - \U \U^\top ) \Ustar \tb_k\|^2
\]

Using above and applying Lemma \ref{prodsubg} with $t = m  \delta_b   \|  (\I - \U \U^\top ) \xstar_k\|^2$, $K_{X_{i}} = K_{Y_{i}} = \|  (\I - \U \U^\top ) \xstar_k\|$, and summing over $i=1,2,\dots,m$, we conclude that,
w.p. at least $1-\exp\left(  -c\delta_b ^2 m\right)$,
	\begin{align}
		{\|\bnu_k\|^2}  \leq m (1+\delta_b) \|  (\I - \U \U^\top ) \Ustar \tb_k\|^2  
\label{nuk_bnd}
	\end{align}


We estimate $\bhat_k$ by solving a standard PR problem using measurements $\y_\ik, i \in [m]$ with measurement vectors $(\U^\top  \a_\ik), i \in [m]$. We use RWF for this. 
 By Theorem 2 of \cite{rwf} for RWF,  if $m \ge Cr$, w.p. at least $1- \exp(r -c m)$,
	\begin{align*}
		& \dist\left( \g_k, \bhat_k \right) \leq C \frac{\|\bnu_k\|}{\sqrt{m}} + \rho^{T_{\PR,t}} \|\g_k\|,
	\end{align*}
	with $\rho<1$. 
By picking $T_{\PR,t}$ so that $\rho^{T_{\PR,t}} \le \deltatfrob / \sqrt{r}$, using $\|\g_k\| \le \|\tb_k\|$, using $(a+b)^2 \le 2 (a^2 + b^2)$, and finally using the bound on $\bnu_k$ from \eqref{nuk_bnd} with $\delta_b=0.1$,
we can conclude that,  

w.p. at least $1 - 2 \exp(r -c m)$, 
	\begin{align*}
		 \dist\left( \g_k, \bhat_k \right)^2 & \leq C \frac{\|\bnu_k\|^2}{m}  + C \frac{\deltatfrob^2}{r} \|\tb_k\|^2  \\
& \le C  \|  (\I - \U \U^\top ) \Ustar \tb_k\|^2  + C \frac{\deltatfrob^2}{r} \|\tb_k\|^2 \
 \le C \deltatfrob^2 \|\bstar_k\|^2.
	\end{align*}
By union bound, the above bound holds for all $k=1,2,\dots,q$, w.p. at least
\[
1- q\exp(r - c m) = 1 - \exp(\log q + r -c m).
\]
Since $\sum_k \|\M \tb_k\|^2 = \|\M \tB\|_F^2 \le \|\M\|_F^2 \|\tB\|^2 =\|\M\|_F^2  \sigmax^2$, we can use the second-last inequality from above to conclude that
	\begin{align*}
\matdist(\G, \Bhat)^2 & = \sum_k  \dist\left( \g_k, \bhat_k \right)^2  \\
&  \le C \sum_k \|  (\I - \U \U^\top ) \Ustar \tb_k\|^2  + C \frac{\deltatfrob^2}{r} \sum_k \|\bstar_k\|^2  \\


& \le  C  \|  (\I - \U \U^\top ) \Ustar \tB \|_F^2  + C \deltatfrob^2 (r \sigmax^2 ) / r \\
& \le  C  \deltatfrob^2 \sigmax^2  + C \deltatfrob^2 \sigmax^2  = C  \deltatfrob^2 \sigmax^2
	\end{align*}

Since $\xstar_k  - \xhat_k = \U \g_k + (\I - \U \U^\top ) \xstar_k  - \U \bhat_k =  \U (\g_k  - \bhat_k) + (\I - \U \U^\top ) \xstar_k $,
\begin{align*}
 \dist\left( \xstar_k, \xhat_k \right)^2 &  \le 	 \dist\left( \g_k, \bhat_k \right)^2  + \|(\I - \U \U^\top ) \Ustar \tb_k\|^2
\le C \deltatfrob^2 \|\tb_k\|^2.
\end{align*}
and, proceeding as before,
\[
\matdist(\Xstar, \Xhat)^2 \le C \sum_k  \dist\left( \g_k, \bhat_k \right)^2  + C \sum_k \|(\I - \U \U^\top ) \Ustar \tb_k\|^2  \le  C  \deltatfrob^2 \sigmax^2
\]
All the above claims hold w.p. at least $1 - \exp(\log q + r -c m)$.


\subsection{Proof of Lemma \ref{B_lemma}, part 2: Incoherence of columns of $\Bhat$}\label{proof_B_bnds_2}
	Recall that $\Bhat \qreq \R_B \B$ and so $\b_k = \R_B^{-1} \bhat_k$.
	Using the bound on $\|\bhat_k - \g_k\|$ from Lemma \ref{B_lemma}, and using $\|\g_k\| \le \|\tb_k\|$  and right singular vectors' incoherence (which implies that $\|\tb_k\|^2 \le \sigmax^2 \mu^2 r/q$),
	\begin{align*}
		\|\b_k\|  
		& \leq \| \R_B^{-1}\| \left( \dist(\bhat_k, \g_k) + \|\g_k\| \right)\\
		
		& \leq \frac{(1 + C\deltatfrob) \sigmax \mu \sqrt{r/q}}{\sigma_{\min}(\R_B)} 
		
	\end{align*}
Observe that $\sigma_{\min}(\R_B) = \sigma_{\min} (\Bhat )$. Using the bound on $\|\G - \Bhat\|_F$ from Lemma \ref{B_lemma}, w.p. at least $1 - \exp(\log q + r -c m)$, 
	
	\begin{align*}
		\sigma_{\min}(\R_B) = \sigma_{\min}(\Bhat) &\geq \sigma_{\min}\left(\G\right) - \|\G - \Bhat\| \\
		&	\geq \sigma_{\min}(\U^\top \U^*) \sigma_{\min}( \tB ) - \|\G - \Bhat\|_F \\
		& \ge  \sqrt{1- \SE_2^2(\U,\Ustar)} \sigmin  - C \deltatfrob \sigmax \\
		& \ge  \sqrt{1- \deltatfrob^2} \sigmin  -C \deltatfrob \sigmax.
	\end{align*}
Since we assumed $\deltatfrob \le c/ \kappa$,
$\sigma_{\min}(\R_B) \ge 0.9 \sigmin.$
Thus, letting $\hat\mu = C \kappa \mu$,
$
\|\b_k\| \le  \frac{C \sigmax \mu \sqrt{r/q} }{ 0.9 \sigmin } \le \hat\mu \sqrt{r/q} . 
$
{"config": "arxiv", "file": "2006.06198/sample_eff_new_result_proof.tex"}