example belongs to the class under generalizations of Assumption 5.10.

####  A.4 Missing outcomes

So far, we have discussed corruption of the regressors $X_{i,\cdot}$ and taken
outcome $Y_{i}$ to be uncorrupted. Measurement error and differential privacy
of $Y_{i}$ is already captured by response noise $\varepsilon_{i}$. An
important additional issue in empirical research is outcome attrition: for
some observations, $Y_{i}$ is missing. Moreover, the outcome attrition
mechanism may depend on the true regressors. Our framework handles this case
as well with light modification. The enriched observation model is

$\displaystyle Y_{i}$
$\displaystyle=\gamma_{0}(D_{i},X_{i,\cdot},S_{i})+\varepsilon_{i},\quad
Z_{i,\cdot}=[X_{i,\cdot}+H_{i,\cdot}]\odot\pi_{i,\cdot},\quad\tilde{Y}_{i}=Y_{i}\cdot
S_{i}$

where $S_{i}\in\\{1,\texttt{NA}\\}$ encodes attrition. Instead of observing
$(Y_{i},D_{i},X_{i,\cdot})$ or even $(Y_{i},D_{i},Z_{i,\cdot})$, the analyst
observes $(\tilde{Y}_{i},D_{i},Z_{i,\cdot})$. In the taxonomy of [Rubin,
1976], we allow outcome $Y_{i}$ to be missing at random (MAR) conditional on
true regressors $(D_{i},X_{i,\cdot})$, of which $X_{i,\cdot}$ may be missing
completely at random (MCAR) or may have measurement error. The extended
semiparametric model is summarized by

$\displaystyle\mathbb{E}[\tilde{Y}_{i}|D_{i},X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot},S_{i}=1]$
$\displaystyle=\mathbb{E}[Y_{i}|D_{i},X_{i,\cdot},H_{i,\cdot},\pi_{i,\cdot},S_{i}=1]$
$\displaystyle=\mathbb{E}[Y_{i}|D_{i},X_{i,\cdot},S_{i}=1]$
$\displaystyle=\gamma_{0}(D_{i},X_{i,\cdot},S_{i}=1).$

Our framework handles this extension by replacing $Y_{i}$ with $\tilde{Y}_{i}$
and replacing $(D,X_{i,\cdot})$ with $(D_{i},X_{i,\cdot},S_{i})$, similar to
[Singh, 2021].

###  Appendix B Additional simulations and applications

In this appendix, we provide additional synthetic, semi-synthetic, and real
results to argue

  1. 1.

our procedure is robust to a broad variety of data shapes and sizes;

  2. 2.

data corruption can flip the sign of OLS and TSLS some of the time;

  3. 3.

our key assumption holds in popular Census data sets at different levels of
granularity.

####  B.1 Robustness to data dimensions

In the main text, the each sample from the simulated data generating process
produces a matrix of covariates $\boldsymbol{X}\in\mathbb{R}^{100\times 100}$
with rank $r=5$. In practice, economic data sets come in a variety of shapes
and sizes. In this subsection, we ask: how robust is our end-to-end procedure
across realistic dimensions of economic data? We consider the following
variations of the simulated data generating process:
$\boldsymbol{X}\in\mathbb{R}^{50\times 200}$, $\mathbb{R}^{100\times 100}$,
$\mathbb{R}^{200\times 50}$, $\mathbb{R}^{500\times 20}$, and
$\mathbb{R}^{1000\times 10}$. For each choice of sample size $n$ and covariate
dimension $p$, we set the rank to be $r=\\{\min(n,p)\\}^{1/3}$. Across data
dimensions, we introduce measurement error with the fixed noise-to-signal
ratio of $20\%$. We consider the oracle tuning of the PCA hyperparameter
$k=r$.

Figure 12: Our approach adapts to data shape

Table 12 quantifies coverage performance. Different rows correspond to
different data dimensions. As in the main text, we record the average point
estimates, which are close to $\theta_{0}=2.2$. Next, we record the average
standard errors, which adaptively decrease in length for larger sample sizes.
These confidence intervals are the correct length, since coverage is close to
the nominal level. In anticipation of the empirical application, we repeat
this exercise for the simulated data generating process with
$\boldsymbol{X}\in\mathbb{R}^{722\times 30}$ and rank $r=5$. Table 12 confirms
that our procedure attains coverage close to the nominal level.

####  B.2 Can data corruption flip signs?

In the main text, we show that for the simulated data generating process with
$\boldsymbol{X}\in\mathbb{R}^{100\times 100}$ and rank $r=5$, OLS performs
well with clean data and performs poorly with corrupted data. In particular,
measurement error with a $20\%$ noise-to-signal ratio is enough to pose a
problem for OLS. We investigate two follow-up questions. First, can data
corruption flip the sign of OLS estimates, i.e. can it lead to negative point
estimates when the average treatment effect is $\theta_{0}=2.2>0$? Second, can
can data corruption flip the sign of OLS and 2SLS estimates in scenarios more
similar to our real world example?

As an answer to the first question, we find that data corruption can flip the
sign of OLS estimates some of the time. Figure 13(a) visualizes the histogram
of 1000 OLS point estimates from the data generating process with dimensions
$\boldsymbol{X}\in\mathbb{R}^{100\times 100}$, rank $r=5$, and $20\%$
measurement error. Roughly one quarter of the OLS estimates have flipped
signs. As Figure 13(b) shows, the histogram of 1000 point estimates using our
procedure remain close to $\theta_{0}=2.2$ with no flipped signs.

(a) OLS

(b) Our approach

Figure 13:  Data corruption can flip signs: $100\times 100$

In order to answer the second question, we repeat this exercise for the
simulated data generating process with $\boldsymbol{X}\in\mathbb{R}^{722\times
30}$ and rank $r=5$. Flipping signs requires not only 20% measurement error
but also 10% missingness. Figure 14 visualizes the histograms of 1000 point
estimates, using OLS versus our procedure. A similar fraction of OLS estimates
have flipped signs, while none of our estimates have flipped signs.

(a) OLS

(b) Our approach

Figure 14:  Data corruption can flip signs: $722\times 30$

Finally, we conduct a semi-synthetic sign flipping exercise. We consider the
Census covariates from [Autor et al., 2013] at the commuting zone level.
Rather than a synthetic average treatment effect, the estimand is the actual
effect of import competition on manufacturing employment in a partially linear
instrumental variable model. Flipping signs requires not only 20% measurement
error but also 20% missingness. In this thought experiment, we take the
reported effect from [Autor et al., 2013] as the ground truth, we take the
data set from [Autor et al., 2013] as clean data, and we generate synthetic
measurement error and missingness. Figure 15 visualizes the histograms of 1000
point estimates across 1000 draws of synthetic corruption, using 2SLS versus
our procedure. A relatively small fraction of 2SLS estimates have flipped
signs, while none of our estimates have flipped signs.

(a) 2SLS

(b) Our approach

Figure 15:  Data corruption can flip signs: Census Figure 16: Data corruption
can flip signs

We summarize the results of these various sign flipping exercises in Table 16.
The three rows correspond to (i) synthetic data with
$\boldsymbol{X}\in\mathbb{R}^{100\times 100}$; (ii) synthetic data with
$\boldsymbol{X}\in\mathbb{R}^{722\times 30}$; and (iii) semi-synthetic data
from [Autor et al., 2013]. We interpret the OLS and TSLS results as motivation
for data cleaning before data analysis. Our procedure may be viewed as an
extension of OLS and TSLS with a very simple type of data cleaning that we
subsequently account for in our data cleaning-adjusted confidence intervals.
An exciting direction for future work is to extend our results to richer types
of data cleaning which more closely resemble empirical practice.

####  B.3 The key assumption holds in many Census data sets

Our key assumption, which powers our entire analysis, is that the true
covariates $\boldsymbol{X}$ are approximately low rank. In the main text, we
visually confirm that this assumption holds in Census data by plotting the
singular values of the covariates from [Autor et al., 2013]. In this
subsection, we argue that this key assumption holds in several Census data
sets that are popular in economic research. We visualize the singular values
of covariates from [LaLonde, 1986, Poterba et al., 1996, Chetty and Hendren,
2018a].

(a) NSW

(b) PSID

(c) CPS

Figure 17:  National Supported Work demonstration Figure 18: 401(k)
participation

We begin with data sets at the individual level. In [LaLonde, 1986], the
author considers the problem of estimating the average treatment effect of the
National Supported Work (NSW) demonstration, a randomized job training
program. There are three data sets: one using actual NSW participants as the
treated and control group; another using NSW participants as the treated group
and a PSID sample as the comparison group, and yet another using NSW
participants as the treated group and a CPS sample as the comparison group. In
Figure 17, we visualize the singular values of covariates for these three data
sets. Across data sets, the rank is approximately $r=3$ while the ambient
dimension of covariates is $p=10$. In [Poterba et al., 1996], the authors
consider the problem of estimating the (local) average treatment effect of
401(k) participation on savings. Figure 18 visualizes the singular values of
covariates, showing that the rank is approximately $r=2$ while the ambient
dimension of covariates is $p=9$.

Next, we turn to data sets of aggregate units. In [Chetty and Hendren, 2018a],
the authors consider commuting zones to be the aggregate units. In [Chetty and
Hendren, 2018b], a companion paper, the authors consider counties to be the
aggregate units. These two data sets help to evaluate the robustness of the
approximate low rank assumption across different levels of geography. In
Figure 19, we show that the approximate rank is $r=5$ while the ambient
dimension of covariates is $p=45$. Since the data set has missing values, we
report the singular values using complete cases and using filled cases
according to our filling procedure from the main text.

(a) County (complete cases)

(b) Commuting zone (complete cases)

(c) County (filled)

(d) Commuting zone (filled)

Figure 19:  Opportunity insights

###  Appendix C Nonlinearity

In this appendix, we characterize the class of nonlinear dictionaries
$b:\mathbb{R}^{p}\rightarrow\mathbb{R}^{p^{\prime}}$ for which our main
results go through. We delay proofs until the last subsection of this
appendix. We discuss two classes of dictionaries.

####  C.1 Polynomial dictionary

We refer to the following three simple properties as data cleaning continuity,
since they imply that the data cleaning results for original regressors imply
similar data cleaning results for technical regressors. We state the
properties then verify them for the polynomial dictionary of degree
$d_{\max}$.

######  Assumption C.1 (Dictionary continuity).

The dictionary satisfies three conditions:

  1. 1.

For any two matrices
$\boldsymbol{M}^{(1)},\boldsymbol{M}^{(2)}\in\mathbb{R}^{n\times p}$,
$\|b(\boldsymbol{M}^{(1)})-b(\boldsymbol{M}^{(2)})\|^{2}_{2,\infty}\leq
C_{b}^{\prime}\|\boldsymbol{M}^{(1)}-\boldsymbol{M}^{(2)}\|^{2}_{2,\infty}$;

  2. 2.

For any $\boldsymbol{M}\in\mathbb{R}^{n\times p}$,
$rank\\{b(\boldsymbol{M})\\}\leq\left\\{rank(\boldsymbol{M})\right\\}^{C_{b}^{\prime\prime}}$;

  3. 3.

For any $v\in\mathbb{R}^{p}$,
$\|b(v)\|_{\max}\leq\left(\|v\|_{\max}\right)^{C_{b}^{\prime\prime\prime}}$.

For much of our argument to go through, it suffices that the dictionary
exhibits three simple properties: clean original regressors should imply clean
technical regressors; low rank original regressors should imply low rank
technical regressors; and a bound on the maximum value of original regressors
should imply a bound on the maximum value of technical regressors.

######  Definition C.1 (Polynomial dictionary).

Let $v=(v_{1},v_{2},\dots,v_{p})\in\mathbb{R}^{p}$. Consider the dictionary
$b^{\textsc{poly}}$, where for $k\in[p^{\prime}]$,
$b^{\textsc{poly}}_{k}(v)=\prod_{\ell=1}^{d(k)}v_{\ell}$ with
$v_{\ell}\in\\{v_{1},\dots,v_{p}\\}$.

That is, each basis function $b^{\textsc{poly}}_{k}(v)$ in the dictionary is a
polynomial of degree $d(k)\leq d_{\max}$ constructed from coordinates of $v$,
allowing for repeats. This class of dictionaries is commonly used in empirical
economic research. It nests as a special case the interacted dictionary
studied in the main text, which permits a rich model of heterogeneous
treatment effects. Pleasingly, for this class, the dictionary constants
$(C_{b}^{\prime},C_{b}^{\prime\prime},C_{b}^{\prime\prime\prime})$ have no
dependence on $p^{\prime}$, the number of elements in the dictionary. Rather,
$(C_{b}^{\prime},C_{b}^{\prime\prime},C_{b}^{\prime\prime\prime})$ only depend
on the maximum degree $d_{\max}$ of the polynomial dictionary.

######  Proposition C.1 (Verifying Assumption C.1).

The polynomial dictionary $b^{\textsc{poly}}$ of degree $d_{\max}$ satisfies
Assumption C.1 with the following constants

  1. 1.

$C_{b}^{\prime}\leq
2^{d_{\max}}\cdot\|\boldsymbol{M}^{(1)}\|^{2d_{\max}}_{\max}\cdot\|\boldsymbol{M}^{(2)}\|^{2d_{\max}}_{\max}$;

  2. 2.

$C_{b}^{\prime\prime}\leq d_{\max}$;

  3. 3.

$C_{b}^{\prime\prime\prime}\leq d_{\max}$.

Remarkably, this class of dictionaries also preserves the low rank
approximation in the following sense.

######  Proposition C.2 (Low rank approximation is preserved).

Suppose Assumption 5.1 holds and the true covariates have the low rank
approximation
$\boldsymbol{X}=\boldsymbol{X}^{\textsc{(lr)}}+\boldsymbol{E}^{\textsc{(lr)}}$
where $r=rank\\{\boldsymbol{X}^{\textsc{(lr)}}\\}$ and
$\Delta_{E}=\|\boldsymbol{E}^{\textsc{(lr)}}\|_{\max}$. Consider the
polynomial dictionary $b^{\textsc{poly}}$ of degree $d_{\max}$. Then
$r^{\prime}:=rank\\{b(\boldsymbol{X}^{\textsc{(lr)}})\\}\leq r^{d_{\max}}$ and
$\Delta^{\prime}_{E}:=\|b(\boldsymbol{X})-b(\boldsymbol{X}^{\textsc{(lr)}})\|_{\max}\leq
C\bar{A}^{d_{\max}}\cdot d_{\max}\Delta_{E}$.

The same logic applies for dictionaries applied to $(D_{i},X_{i,\cdot})$
rather than $X_{i,\cdot}$.

####  C.2 Polynomial dictionary with uncorrupted nonlinearity

Assumption C.1 suffices to generalize our data cleaning results. For analysis
of the error-in-variables estimators, we impose a further assumption, which
constrains which kinds of terms can appear as technical regressors. Consider
the polynomial dictionary of degree $d_{\max}$, where the only source of
nonlinearity is powers and interactions with regressors known to be
uncorrupted.

######  Definition C.2 (Polynomial dictionary with uncorrupted nonlinearity).

Suppose the observed regressors consist of one uncorrupted regressor $D_{i}$
and several corrupted regressors $X_{i,\cdot}$. Consider a polynomial
dictionary $b^{\textsc{poly}}$ of degree $d_{\max}$ such that each basis
function $b^{\textsc{poly}}_{k}$ is at most linear in the corrupted
regressors. By definition, $p^{\prime}\leq C\cdot d_{\max}p$.

For example, in Example A.1 where $D_{i}$ is uncorrupted, the interacted
dictionary
$b:(D_{i},X_{i,\cdot})\mapsto\\{D_{i}X_{i,\cdot},(1-D_{i})X_{i,\cdot}\\}$
satisfies this property. In Example A.4 where $D_{i}$ is uncorrupted, the
nonlinear dictionary
$b:(D_{i},X_{i,\cdot})\mapsto(1,D_{i},X_{i,\cdot},D_{i}X_{i,\cdot},D_{i}^{2})$
satisfies this property as well since it contains $D_{i}^{2}$ but does not
contain $X_{ij}^{2}$. Intuitively, this family of dictionaries avoids
compounding measurement error because the corrupted regressors are not
multiplied with each other. For readability, we focus on the case of one
uncorrupted regressor, which can be conceptualized as

$b:(D_{i},X_{i,\cdot})\mapsto(1,D_{i},...,D_{i}^{d_{\max}},X_{i,\cdot},D_{i}X_{i,\cdot},...,D_{i}^{d_{\max}-1}X_{i,\cdot})$
(6)

where $D_{i}$ is uncorrupted and $X_{i,\cdot}$ are uncorrupted. Definition C.2
naturally generalizes to the case of multiple uncorrupted regressors. We
require three properties to hold after the dictionary is applied to the data.

######  Assumption C.2 (Dictionary is non-collapsing).

The dictionary does not collapse in the following sense.

  1. 1.

Recall that we set $k:=rank(\hat{\boldsymbol{X}})$ equal to
$r:=rank\\{\boldsymbol{X}^{\textsc{(lr)}}\\}$. We further assume
$k^{\prime}:=rank\\{b(D,\hat{\boldsymbol{X}})\\}$ is equal to
$r^{\prime}:=rank[b\\{D,\boldsymbol{X}^{\textsc{(lr)}}\\}]$.

  2. 2.

Assumption 5.4 posits that the smallest singular value of
$\boldsymbol{X}^{\textsc{(lr)}}$ is $s_{r}\geq C\sqrt{\frac{np}{r}}$. We
further posit that the smallest singular value of
$b\\{D,\boldsymbol{X}^{\textsc{(lr)}}\\}$ is $s^{\prime}_{r^{\prime}}\geq
C\sqrt{\frac{np}{r^{\prime}}}$.

  3. 3.

Using the notation of (6), the technical regressors
$(1,D_{i},...D_{i}^{d_{\max}})$ are full rank.

The first property in Assumption C.2 ensures two matrices of equal rank get
mapped to two new matrices of equal rank. The second property imposes that
singular values, after dictionary mapping, remain well balanced. In
particular, we allow for a weaker signal to noise ratio for technical
regressors since $r^{\prime}\geq r$. We do not impose
$s^{\prime}_{r^{\prime}}\geq C\sqrt{\frac{np^{\prime}}{r^{\prime}}}$, which is
a stronger and less plausible requirement since it implies that the signal to
noise ratio increases with the dictionary dimension $p^{\prime}$. The third
property is a technical assumption which allows the theory of implicit data
cleaning to generalize.

####  C.3 Proofs

We prove Proposition C.1 via the following sequence of lemmas.

######  Lemma C.1 ($C_{b}^{\prime}$).

For $b^{\textsc{poly}}$, $C_{b}^{\prime}\leq
2^{d_{\max}}\cdot\|\boldsymbol{M}^{(1)}\|^{2d_{\max}}_{\max}\cdot\|\boldsymbol{M}^{(2)}\|^{2d_{\max}}_{\max}$.

###### Proof.

We introduce the notation
$[b^{\textsc{poly}}(\boldsymbol{M})]_{ik}=\prod_{\\{j(k)\\}}M_{ij(k)}$, where
$j(k)\in[p]$, $M_{ij(k)}\in\\{M_{i1},\dots,M_{ip}\\}$, and
$|\\{j(k)\\}|=d(k)$. We will simplify notation in the following way. Fix $k$.
Let $M_{i\ell}$ refer to the $\ell$-th element of the product, where
$\ell\in[d(k)]$. Therefore

$[b^{\textsc{poly}}(\boldsymbol{M})]_{ik}=\prod_{\\{j(k)\\}}M_{ij(k)}=\prod_{\ell=1}^{d(k)}M_{i\ell}.$

Then for any column $k\in[p^{\prime}]$,

$\displaystyle\|b(\boldsymbol{M}^{(1)})_{\cdot,k}-b(\boldsymbol{M}^{(2)})_{\cdot,k}\|^{2}_{2}$
$\displaystyle=\sum_{i=1}^{n}\left(\prod_{\ell=1}^{d(k)}M^{(1)}_{i\ell}-\prod_{\ell=1}^{d(k)}M^{(2)}_{i\ell}\right)^{2}$
$\displaystyle=\sum_{i=1}^{n}\left(\prod_{\ell=1}^{d(k)}M^{(1)}_{i\ell}-\prod_{\ell=1}^{d(k)}M^{(2)}_{i\ell}\pm
M^{(2)}_{i1}\prod_{\ell=2}^{d(k)}M^{(1)}_{i\ell}\right)^{2}$
$\displaystyle\leq
2\sum_{i=1}^{n}\left(\prod_{\ell=1}^{d(k)}M^{(1)}_{i\ell}-M^{(2)}_{i1}\prod_{\ell=2}^{d(k)}M^{(1)}_{i\ell}\right)^{2}$
$\displaystyle\quad+2\sum_{i=1}^{n}\left(\prod_{\ell=1}^{d(k)}M^{(2)}_{i\ell}-M^{(2)}_{i1}\prod_{\ell=2}^{d(k)}M^{(1)}_{i\ell}\right)^{2}.$

Looking at the first term on the RHS above,

$\displaystyle\sum_{i=1}^{n}\left(\prod_{\ell=1}^{d(k)}M^{(1)}_{i\ell}-M^{(2)}_{i1}\prod_{\ell=2}^{d(k)}M^{(1)}_{i\ell}\right)^{2}$
$\displaystyle=\sum_{i=1}^{n}\left(M^{(1)}_{i1}-M^{(2)}_{i1}\right)^{2}\left(\prod_{\ell=2}^{d(k)}M^{(1)}_{i\ell}\right)^{2}$
$\displaystyle\leq\|\boldsymbol{M}^{(1)}\|_{\max}^{2d_{\max}}\sum_{i=1}^{n}\left(M^{(1)}_{i1}-M^{(2)}_{i1}\right)^{2}$
$\displaystyle\leq\|\boldsymbol{M}^{(1)}\|_{\max}^{2d_{\max}}\|\boldsymbol{M}^{(1)}-\boldsymbol{M}^{(2)}\|^{2}_{2,\infty}.$

Now looking at the second term on the RHS,

$\displaystyle\sum_{i=1}^{n}\left(\prod_{\ell=1}^{d(k)}M^{(2)}_{i\ell}-M^{(2)}_{i1}\prod_{\ell=2}^{d(k)}M^{(1)}_{i\ell}\right)^{2}$
$\displaystyle=\sum_{i=1}^{n}\left(M^{(2)}_{i1}\left(\prod_{\ell=2}^{d(k)}M^{(2)}_{i\ell}-\prod_{\ell=2}^{d(k)}M^{(1)}_{i\ell}\right)\right)^{2}$
$\displaystyle\leq\|\boldsymbol{M}^{(2)}\|_{\max}^{2}\sum_{i=1}^{n}\left(\prod_{\ell=2}^{d(k)}M^{(2)}_{i\ell}-\prod_{\ell=2}^{d(k)}M^{(1)}_{i\ell}\right)^{2}.$

Continuing forward with
$\sum_{i=1}^{n}\left(\prod_{\ell=2}^{d(k)}M^{(2)}_{i\ell}-\prod_{\ell=2}^{d(k)}M^{(1)}_{i\ell}\right)^{2}$
in a recursive manner leads to the following bound for all $k\in[p^{\prime}]$:

$\displaystyle\|b(\boldsymbol{M}^{(1)})_{\cdot,k}-b(\boldsymbol{M}^{(2)})_{\cdot,k}\|^{2}_{2}$
$\displaystyle\leq\|\boldsymbol{M}^{(1)}-\boldsymbol{M}^{(2)}\|^{2}_{2,\infty}\cdot\left(2^{d_{\max}}\cdot\|\boldsymbol{M}^{(1)}\|^{2d_{\max}}_{\max}\cdot\|\boldsymbol{M}^{(2)}\|^{2d_{\max}}_{\max}\right).$

We thus have the desired result. ∎

######  Lemma C.2 ($C_{b}^{\prime\prime}$).

For $b^{\textsc{poly}}$, $C_{b}^{\prime\prime}\leq d_{\max}$.

###### Proof.

Fix $\boldsymbol{M}\in\mathbb{R}^{n\times p}$ with rank $r$. For notational
simplicity, let $M_{i\ell}$ refer to the $\ell$-th element of the product in
$[b^{\textsc{poly}}(\boldsymbol{M})]_{ik}$. Observe that
$b^{\textsc{poly}}(\boldsymbol{M})$ can be equivalently represented as

$b^{\textsc{poly}}(\boldsymbol{M})=\boldsymbol{B}^{(1)}\odot,...,\odot\boldsymbol{B}^{(d_{\max})},$

where $\odot$ means Hadamard product,
$\boldsymbol{B}^{(\ell)}\in\mathbb{R}^{n\times p^{\prime}}$, and for
$\ell\in[d_{\max}],i\in[n],k\in[p^{\prime}]$

$[\boldsymbol{B}^{(\ell)}]_{ik}=\begin{cases}M_{i\ell}&\mbox{if }\ell\leq
d(k)\\\ 1&\mbox{if }\ell>d(k)\end{cases}.$

Since each column of each $\boldsymbol{B}^{(\ell)}$ is either a column of
$\boldsymbol{M}$ or a column of ones, it has rank at most $r$. Finally recall
that the rank of a Hadamard product is bounded by the product of ranks and so

$rank\\{b^{\textsc{poly}}(\boldsymbol{M})\\}\leq\prod_{\ell=1}^{d_{\max}}r=r^{d_{\max}}.$

∎

######  Lemma C.3 ($C_{b}^{\prime\prime\prime}$).

For $b^{\textsc{poly}}$, $C_{b}^{\prime\prime\prime}\leq d_{\max}$.

###### Proof.

Denote $v\in\mathbb{R}^{p}$ with $\|v\|_{\infty}\leq\bar{A}$. Note that each
basis function is of the form

$b^{\textsc{poly}}_{k}(v)=\prod_{\ell=1}^{d(k)}v_{\ell}\leq\prod_{\ell=1}^{d(k)}\bar{A}=\bar{A}^{d(k)}\leq\bar{A}^{d_{\max}}.$

∎

###### Proof of Proposition C.1.

Immediate from Lemmas C.1, C.2, and C.3. ∎

To begin, we state an important observation about the signal approximation
$\boldsymbol{X}^{\textsc{(lr)}}$ that will simplify our subsequent analysis.

######  Lemma C.4 (Bounded signal approximation).

Suppose Assumption 5.1 holds. Without loss of generality,
$\|\boldsymbol{X}^{\textsc{(lr)}}\|_{\max}\leq 3\bar{A}$.

Since $\|\boldsymbol{X}\|_{\max}\leq\bar{A}$ and
$\|\boldsymbol{X}^{\textsc{(lr)}}\|_{\max}\leq 3\bar{A}$, the same constant
$C\bar{A}$ handles both objects.

###### Proof of Lemma C.4.

Suppose we have access to some $\boldsymbol{X}^{\textsc{(lr)}}$ with rank $r$
such that $\|\boldsymbol{X}^{\textsc{(lr)}}\|_{\max}>3\bar{A}$. By reverse
triangle inequality

$\Delta_{E,\boldsymbol{X}^{\textsc{(lr)}}}=\|\boldsymbol{X}^{\textsc{(lr)}}-\boldsymbol{X}\|_{\max}\geq\|\boldsymbol{X}^{\textsc{(lr)}}\|_{\max}-\|\boldsymbol{X}\|_{\max}>2\bar{A}.$

We construct a $\boldsymbol{B}^{\textsc{(lr)}}$ with rank $r$ such that
$\|\boldsymbol{B}^{\textsc{(lr)}}\|_{\max}\leq 3\bar{A}$ and
$\Delta_{E,\boldsymbol{B}^{\textsc{(lr)}}}<\Delta_{E,\boldsymbol{X}^{\textsc{(lr)}}}$.
Set

$\boldsymbol{B}^{\textsc{(lr)}}=\frac{\bar{A}}{\|\boldsymbol{X}^{\textsc{(lr)}}\|_{\max}}\cdot\boldsymbol{X}^{\textsc{(lr)}}.$

Since $\boldsymbol{B}^{\textsc{(lr)}}$ simply scales
$\boldsymbol{X}^{\textsc{(lr)}}$ by a constant, it has the same rank. By
construction $\|\boldsymbol{B}^{\textsc{(lr)}}\|_{\max}\leq\bar{A}$. Finally

$\Delta_{E,\boldsymbol{B}^{\textsc{(lr)}}}=\|\boldsymbol{B}^{\textsc{(lr)}}-\boldsymbol{X}\|_{\max}\leq\|\boldsymbol{B}^{\textsc{(lr)}}\|_{\max}+\|\boldsymbol{X}\|_{\max}\leq
2\bar{A}.$

∎

###### Proof of Proposition C.2.

By definition, $r=rank\\{\boldsymbol{X}^{\textsc{(lr)}}\\}$. The first result
follows directly from Proposition C.1. To see the second result, consider the
case where $d_{\max}=2$. Then any higher order entry of
$b(\boldsymbol{X})-b(\boldsymbol{X}^{\textsc{(lr)}})$ is of the form

$\displaystyle|X_{ij}X_{ik}-X^{\textsc{(lr)}}_{ij}X^{\textsc{(lr)}}_{ik}|$
$\displaystyle\leq|X_{ij}X_{ik}-X^{\textsc{(lr)}}_{ij}X_{ik}|+|X^{\textsc{(lr)}}_{ij}X_{ik}-X^{\textsc{(lr)}}_{ij}X^{\textsc{(lr)}}_{ik}|$
$\displaystyle\leq\bar{A}\Delta_{E}+3\bar{A}\Delta_{E}$

where the final inequality appeals to Lemma C.4. More generally, there are
$d_{\max}$ such terms, and the largest is of the form
$(3\bar{A})^{d_{\max}}\Delta_{E}$. ∎

###  Appendix D Data cleaning

####  D.1 Notation and preliminaries

In this appendix, we replace the symbol $X_{i,\cdot}$ with the symbol
$A_{i,\cdot}$, so that

$Z_{i,\cdot}=(A_{i,\cdot}+H_{i,\cdot})\odot\pi_{i,\cdot}.$

We suppress indexing by the folds $(\textsc{train},\textsc{test})$ to lighten
notation. As in Assumption 5.3, we identify NA with $0$ in $\boldsymbol{Z}$
for the remainder of the appendix. We slightly abuse notation by letting $n$
be the number of observations in train, departing from the notation of the
main text. The entire section is conditional on $\boldsymbol{A}$, which we
omit to lighten notation. We write $\|\cdot\|=\|\cdot\|_{op}$, and abbreviate
law of iterated expectations (LIE). We denote by $C$ an absolute constant.

Recall
$\boldsymbol{A}=\boldsymbol{A}^{\textsc{(lr)}}+\boldsymbol{E}^{\textsc{(lr)}}$
and $r=rank\\{\boldsymbol{A}^{\textsc{(lr)}}\\}$. We denote the SVDs

$\boldsymbol{A}^{\textsc{(lr)}}=\boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{V}^{T},\quad\hat{\boldsymbol{A}}=\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{\Sigma}}_{k}\hat{\boldsymbol{V}}_{k}^{T},\quad\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}=\hat{\boldsymbol{U}}\hat{\boldsymbol{\Sigma}}\hat{\boldsymbol{V}}^{T}.$

The first $k$ left singular vectors of $\boldsymbol{A}^{\textsc{(lr)}}$ are
$\boldsymbol{U}_{k}$. We denote $s_{k}=\Sigma_{kk}$ and
$\hat{s}_{k}=\hat{\Sigma}_{kk}$. Recall that
$\delta=\frac{1}{1-\sqrt{\frac{22\ln(np)}{n\rho_{\min}}}}$.

Define the unit ball $\mathbb{B}^{p}$ and unit sphere $\mathbb{S}^{p-1}$ by

$\displaystyle\mathbb{B}^{p}$
$\displaystyle=\\{v\in\mathbb{R}^{p}:\|v\|_{2}\leq 1\\}$
$\displaystyle\mathbb{S}^{p-1}$
$\displaystyle=\\{v\in\mathbb{R}^{p}:\|v\|_{2}=1\\}$

Recall that $\hat{\boldsymbol{A}}^{\textsc{train}}$ is constructed by taking
train covariates then filling and cleaning them using train alone. In addition
to studying $\hat{\boldsymbol{A}}^{\textsc{train}}$, we introduce and study
the object $\hat{\boldsymbol{A}}^{\textsc{test}}$, is constructed by taking
test covariates, filling them using train, and cleaning them using test. It
turns out that the analysis does not depend on whether
$\operatorname{\hat{\boldsymbol{\rho}}}^{\textsc{train}}$ or
$\operatorname{\hat{\boldsymbol{\rho}}}^{\textsc{test}}$ is used when filling
in missing values. Rather than writing two nearly identical arguments, we
write out one unified argument with formal remarks.

###### Proof of Proposition 4.1.

By LIE,

$\displaystyle\mathbb{E}[\textsc{fill}(Z^{\textsc{test}}_{ij})|A^{\textsc{test}}_{ij},\textsc{train}]$
$\displaystyle=\mathbb{E}[\textsc{fill}(Z^{\textsc{test}}_{ij})|A^{\textsc{test}}_{ij},\pi^{\textsc{test}}_{ij}=1,\textsc{train}]\mathbb{P}(\pi^{\textsc{test}}_{ij}=1|A^{\textsc{test}}_{ij},\textsc{train})$
$\displaystyle\quad+\mathbb{E}[\textsc{fill}(Z^{\textsc{test}}_{ij})|A^{\textsc{test}}_{ij},\pi^{\textsc{test}}_{ij}=0,\textsc{train}]\mathbb{P}(\pi^{\textsc{test}}_{ij}=0|A^{\textsc{test}}_{ij},\textsc{train})$
$\displaystyle=\mathbb{E}[Z^{\textsc{test}}_{ij}/\hat{\rho}_{j}|A^{\textsc{test}}_{ij},\pi^{\textsc{test}}_{ij}=1,\textsc{train}]\cdot\rho_{j}+\mathbb{E}[0|A^{\textsc{test}}_{ij},\pi^{\textsc{test}}_{ij}=1,\textsc{train}]\cdot(1-\rho_{j})$
$\displaystyle=A^{\textsc{test}}_{ij}\frac{\rho_{j}}{\hat{\rho}_{j}}.$

Likewise

$\displaystyle\mathbb{E}[\textsc{fill-as-
means}(Z^{\textsc{test}}_{ij})|A^{\textsc{test}}_{ij},\textsc{train}]$
$\displaystyle=\mathbb{E}[\textsc{fill-as-
means}(Z^{\textsc{test}}_{ij})|A^{\textsc{test}}_{ij},\pi^{\textsc{test}}_{ij}=1,\textsc{train}]\mathbb{P}(\pi^{\textsc{test}}_{ij}=1|A^{\textsc{test}}_{ij},\textsc{train})$
$\displaystyle\quad+\mathbb{E}[\textsc{fill-as-
means}(Z^{\textsc{test}}_{ij})|A^{\textsc{test}}_{ij},\pi^{\textsc{test}}_{ij}=0,\textsc{train}]\mathbb{P}(\pi^{\textsc{test}}_{ij}=0|A^{\textsc{test}}_{ij},\textsc{train})$
$\displaystyle=\mathbb{E}[Z^{\textsc{test}}_{ij}|A^{\textsc{test}}_{ij},\pi^{\textsc{test}}_{ij}=1,\textsc{train}]\cdot\rho_{j}+\mathbb{E}[\bar{Z}_{j}^{\textsc{train}}|A^{\textsc{test}}_{ij},\pi^{\textsc{test}}_{ij}=0,\textsc{train}]\cdot(1-\rho_{j})$
$\displaystyle=A^{\textsc{test}}_{ij}\cdot\rho_{j}+\bar{Z}_{j}^{\textsc{train}}(1-\rho_{j}).$

∎

######  Proposition D.1 (Bound on $\|\hat{\boldsymbol{A}}\|_{\max}$).

Suppose $k=r$ and the corrupted singular values
$\hat{s}_{1},...,\hat{s}_{r}\leq C\sqrt{\frac{np}{r}}$. Assume the following
incoherence conditions for the corrupted singular vectors:
$\|\hat{\boldsymbol{U}}_{r}\|_{\max}\leq Cn^{-1/2}$ and
$\|\hat{\boldsymbol{V}}_{r}\|_{\max}\leq Cp^{-1/2}.$ Then
$\|\hat{\boldsymbol{A}}\|_{\max}\leq Cr^{1/2}.$

The condition $\hat{s}_{1},...,\hat{s}_{r}\leq C\sqrt{\frac{np}{r}}$ can be
proven with high probability from the condition $s_{1},...,s_{r}\leq
C\sqrt{\frac{np}{r}}$ using Weyl’s inequality using an argument similar to
Lemma E.9. The condition $s_{1},...,s_{r}\leq C\sqrt{\frac{np}{r}}$
complements Assumption 5.4. The incoherence conditions can be interpreted by
recognizing that each left singular vector $U_{\cdot,j}\in\mathbb{R}^{n}$ and
each right singular vector $V_{\cdot,j}\in\mathbb{R}^{p}$.

###### Proof.

Write

$\hat{A}_{ij}=\sum_{\ell=1}^{r}\hat{U}_{i\ell}\hat{s}_{\ell}\hat{V}_{j\ell}.$

Hence

$|\hat{A}_{ij}|\leq\sum_{\ell=1}^{r}|\hat{U}_{i\ell}|\cdot|\hat{s}_{\ell}|\cdot|\hat{V}_{j\ell}|\leq
r\cdot Cn^{-1/2}\cdot C\sqrt{\frac{np}{r}}\cdot Cp^{-1/2}=Cr^{1/2}.$

∎

####  D.2 High probability events

Define the following beneficial events. We will show each event holds with
probability $1-\frac{2}{n^{10}p^{10}}$.

$\displaystyle\mathcal{E}_{1}$
$\displaystyle=\bigg{\\{}\|\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho}\|\leq(\sqrt{n}+\sqrt{p})\Delta_{H,op}\bigg{\\}},\quad{\Delta_{H,op}=C\bar{A}(\kappa+K_{a}+\bar{K})\ln^{\frac{3}{2}}(np)};$
$\displaystyle\mathcal{E}_{2}$
$\displaystyle=\bigg{\\{}\max_{j\in[p]}\|Z_{\cdot,j}-\rho_{j}A_{\cdot,j}\|_{2}^{2}\leq
n\Delta_{H}\bigg{\\}},\quad\Delta_{H}=C(K_{a}+\bar{A}\bar{K})^{2}\ln^{2}(np);$
$\displaystyle\mathcal{E}_{3}$
$\displaystyle=\bigg{\\{}\max_{j\in[p]}\|\boldsymbol{U}_{k}\boldsymbol{U}^{T}_{k}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})\|_{2}^{2}\leq
k\Delta_{H}\bigg{\\}};$ $\displaystyle\mathcal{E}_{4}$
$\displaystyle=\Bigg{\\{}\forall
j\in[p],\;\frac{1}{\delta}\rho_{j}\leq\hat{\rho}_{j}\leq\delta\rho_{j}\Bigg{\\}},\quad\delta=\frac{1}{1-\sqrt{\frac{22\ln(np)}{n\rho_{\min}}}};$
$\displaystyle\mathcal{E}_{5}$
$\displaystyle=\bigg{\\{}\max_{j\in[p]}|\hat{\rho}_{j}-\rho_{j}|\leq
C\sqrt{\frac{\ln(np)}{n}}\bigg{\\}}.$

Analyzing $\mathcal{E}_{1}$

######  Lemma D.1.

Under Assumption 5.3,

$\displaystyle\|\mathbb{E}[(\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho})^{T}(\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho})]\|$
$\displaystyle\leq\rho_{\max}(1-\rho_{\min})\left(\max_{j\in[p]}\|A_{\cdot,j}\|_{2}^{2}+{\|diag(\mathbb{E}[\boldsymbol{H}^{T}\boldsymbol{H}])\|}\right)$
$\displaystyle\quad+\rho_{\max}\|\mathbb{E}[\boldsymbol{H}^{T}\boldsymbol{H}]\|,$

where $\rho_{\max}\coloneqq\max_{j\in[p]}\rho_{j}\leq 1$.

###### Proof.

To begin, observe that

$\displaystyle\mathbb{E}[(\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho})^{T}(\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho})]$
$\displaystyle=\sum_{\ell=1}^{n}\mathbb{E}[(Z_{\ell,\cdot}-A_{\ell,\cdot}\boldsymbol{\rho})\otimes(Z_{\ell,\cdot}-A_{\ell,\cdot}\boldsymbol{\rho})].$

Let $\boldsymbol{X}=\boldsymbol{A}+\boldsymbol{H}$. We highlight the following
relations: for any $(\ell,j)\in[n]\times[p]$,

$\displaystyle\mathbb{E}[Z_{\ell j}]$ $\displaystyle=\rho_{j}A_{\ell j}$
$\displaystyle\mathbb{E}[Z_{\ell j}^{2}]$
$\displaystyle=\rho_{j}\mathbb{E}[X_{\ell j}^{2}].$

Now, let us fix a row $\ell\in[n]$ and denote

$\boldsymbol{W}^{(\ell)}=(Z_{\ell,\cdot}-A_{\ell,\cdot}\boldsymbol{\rho})\otimes(Z_{\ell,\cdot}-A_{\ell,\cdot}\boldsymbol{\rho}).$

Using the linearity of expectations, the expected value of the $(i,j)$-th
entry of $\boldsymbol{W}^{(\ell)}$ can be written as

$\displaystyle\mathbb{E}[W_{ij}^{(\ell)}]$ $\displaystyle=\mathbb{E}[Z_{\ell
i}Z_{\ell j}]-\rho_{j}\mathbb{E}[Z_{\ell i}]A_{\ell
j}-\rho_{i}\mathbb{E}[Z_{\ell j}]A_{\ell i}+\rho_{i}\rho_{j}A_{\ell i}A_{\ell
j}.$

Suppose $i=j$, then

$\displaystyle\mathbb{E}[W_{ii}^{(\ell)}]$
$\displaystyle=\rho_{i}\mathbb{E}[X_{\ell i}^{2}]-\rho_{i}^{2}A_{\ell
i}^{2}=\rho_{i}(1-\rho_{i})\mathbb{E}[X_{\ell
i}^{2}]+\rho_{i}^{2}\mathbb{E}[(X_{\ell i}-A_{\ell i})^{2}].$ (7)

On the other hand, if $i\neq j$,

$\displaystyle\mathbb{E}[W_{ij}^{(\ell)}]$
$\displaystyle\leq\sqrt{\rho_{i}\rho_{j}}\mathbb{E}[(X_{\ell i}-A_{\ell
i})(X_{\ell j}-A_{\ell j})].$ (8)

since

$\mathbb{E}[Z_{\ell i}Z_{\ell j}]=\mathbb{E}[\pi_{i\ell}\pi_{\ell
j}]\mathbb{E}[X_{\ell i}X_{\ell j}]\leq\sqrt{\mathbb{E}[\pi^{2}_{\ell
i}]}\sqrt{\mathbb{E}[\pi^{2}_{\ell j}]}\mathbb{E}[X_{\ell i}X_{\ell
j}]=\sqrt{\rho_{i}\rho_{j}}\mathbb{E}[X_{\ell i}X_{\ell j}].$

Therefore, we can bound $\boldsymbol{W}^{(\ell)}$ as the sum of two matrices
where the diagonal components are generated from (7) and the off-diagonal
components are generated from (8). That is,

$\displaystyle\mathbb{E}[\boldsymbol{W}^{(\ell)}]$
$\displaystyle\leq\mathbb{E}\Big{(}\rho_{\max}(1-\rho_{\min})diag(X_{\ell,\cdot}\otimes
X_{\ell,\cdot})+\rho_{\max}^{2}diag(H_{\ell,\cdot}\otimes
H_{\ell,\cdot})\Big{)}$
$\displaystyle\quad+\mathbb{E}\Big{(}\rho_{\max}(H_{\ell,\cdot}\otimes
H_{\ell,\cdot})-\rho_{\max}diag(H_{\ell,\cdot}\otimes H_{\ell,\cdot})\Big{)}$
$\displaystyle\leq\rho_{\max}(1-\rho_{\min})\mathbb{E}[diag(X_{\ell,\cdot}\otimes
X_{\ell,\cdot})]+\rho_{\max}\mathbb{E}[H_{\ell,\cdot}\otimes H_{\ell,\cdot}].$

Taking the sum over all rows $\ell\in[n]$ yields

$\displaystyle\mathbb{E}[(\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho})^{T}(\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho})]$
$\displaystyle\leq\rho_{\max}(1-\rho_{\min})diag(\mathbb{E}[\boldsymbol{X}^{T}\boldsymbol{X}])+\rho_{\max}\mathbb{E}[\boldsymbol{H}^{T}\boldsymbol{H}].$
(9)

To complete the proof, we apply triangle inequality to (9) to obtain

$\displaystyle\left\|\mathbb{E}[(\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho})^{T}(\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho})]\right\|$
$\displaystyle\leq\rho_{\max}(1-\rho_{\min})\left\|diag(\mathbb{E}[\boldsymbol{X}^{T}\boldsymbol{X}])\right\|+\rho_{\max}\left\|\mathbb{E}[\boldsymbol{H}^{T}\boldsymbol{H}]\right\|.$

Since $\boldsymbol{H}$ is zero mean, we have

$\displaystyle\left\|diag(\mathbb{E}[\boldsymbol{X}^{T}\boldsymbol{X}])\right\|$
$\displaystyle=\left\|diag(\boldsymbol{A}^{T}\boldsymbol{A})+diag(\mathbb{E}[\boldsymbol{H}^{T}\boldsymbol{H}])\right\|$
$\displaystyle\leq\left\|diag(\boldsymbol{A}^{T}\boldsymbol{A})\right\|+\left\|diag(\mathbb{E}[\boldsymbol{H}^{T}\boldsymbol{H}])\right\|.$

Collecting terms completes the proof. ∎

######  Lemma D.2 (Lemma H.2 of [Agarwal et al., 2021]).

Suppose that $X\in\mathbb{R}^{n}$ and $P\in\\{0,1\\}^{n}$ are random vectors.
Then for any $a\geq 1$,

$\left\|X\odot P\right\|_{\psi_{a}}\leq\left\|X\right\|_{\psi_{a}}.$

######  Lemma D.3.

Under Assumptions 5.1, 5.2, and 5.3

$\|Z_{i,\cdot}-A_{i,\cdot}\boldsymbol{\rho}\|_{\psi_{a}}\leq
K_{a}+\bar{A}\bar{K}.$

###### Proof.

To begin, write

$\displaystyle\|Z_{i,\cdot}-A_{i,\cdot}\boldsymbol{\rho}\|_{\psi_{a}}$
$\displaystyle=\|X_{i,\cdot}\odot\pi_{i,\cdot}-A_{i,\cdot}\boldsymbol{\rho}\|_{\psi_{a}}$
$\displaystyle=\|X_{i,\cdot}\odot\pi_{i,\cdot}-A_{i,\cdot}\odot\pi_{i,\cdot}+A_{i,\cdot}\odot\pi_{i,\cdot}-A_{i,\cdot}\boldsymbol{\rho}\|_{\psi_{a}}$
$\displaystyle\leq\|(X_{i,\cdot}-A_{i,\cdot})\odot\pi_{i,\cdot}\|_{\psi_{a}}+\|A_{i,\cdot}\odot\pi_{i,\cdot}-A_{i,\cdot}\boldsymbol{\rho}\|_{\psi_{a}}.$

Consider the first term. By Lemma D.2 and Assumption 5.2

$\|(X_{i,\cdot}-A_{i,\cdot})\odot\pi_{i,\cdot}\|_{\psi_{a}}\leq\|(X_{i,\cdot}-A_{i,\cdot})\|_{\psi_{a}}=\|H_{i,\cdot}\|_{\psi_{a}}\leq
K_{a}.$

Consider the second term. By the definition of $\|\cdot\|_{\psi_{a}}$ and
Assumption 5.1

$\displaystyle\|A_{i,\cdot}\odot\pi_{i,\cdot}-A_{i,\cdot}\boldsymbol{\rho}\|_{\psi_{a}}$
$\displaystyle=\sup_{u\in\mathbb{B}^{p}}\left\|\sum_{j=1}^{p}u_{j}A_{ij}(\pi_{ij}-\rho_{j})\right\|_{\psi_{a}}$
$\displaystyle=\bar{A}\sup_{u\in\mathbb{B}^{p}}\left\|\sum_{j=1}^{p}u_{j}\frac{A_{ij}}{\bar{A}}(\pi_{ij}-\rho_{j})\right\|_{\psi_{a}}$

Define the vector with components $v_{j}=u_{j}\frac{A_{ij}}{\bar{A}}$. We
prove $v\in\mathbb{B}^{p}$:

$\|v\|_{2}^{2}=\sum_{j=1}^{p}v_{j}^{2}=\sum_{j=1}^{p}u_{j}^{2}\frac{A^{2}_{ij}}{\bar{A}^{2}}\leq\sum_{j=1}^{p}u_{j}^{2}=\|u\|_{2}^{2}\leq
1.$

Hence,

$\displaystyle\sup_{u\in\mathbb{B}^{p}}\left\|\sum_{j=1}^{p}u_{j}\frac{A_{ij}}{\bar{A}}(\pi_{ij}-\rho_{j})\right\|_{\psi_{a}}$
$\displaystyle\leq\sup_{v\in\mathbb{B}^{p}}\left\|\sum_{j=1}^{p}v_{j}(\pi_{ij}-\rho_{j})\right\|_{\psi_{a}}$
$\displaystyle=\left\|\pi_{i,\cdot}-(\rho_{1},...,\rho_{p})\right\|_{\psi_{a}}$
$\displaystyle\leq\bar{K}.$

The last line holds by Assumption 5.3. In summary,

$\|A_{i,\cdot}\odot\pi_{i,\cdot}-A_{i,\cdot}\boldsymbol{\rho}\|_{\psi_{a}}\leq\bar{A}\bar{K}.$

∎

######  Lemma D.4 (Proposition H.1 of [Agarwal et al., 2021]).

Let $\boldsymbol{W}\in\mathbb{R}^{n\times p}$ be a random matrix whose rows
$\boldsymbol{W}_{i,\cdot}$ are independent $\psi_{a}$-random vectors for some
$a\geq 1$. Then for any $\tau>0$,

$\displaystyle\left\|\boldsymbol{W}\right\|\leq\left\|\mathbb{E}\boldsymbol{W}^{T}\boldsymbol{W}\right\|^{1/2}+\sqrt{(1+\tau)p}\max_{i\in[n]}\left\|\boldsymbol{W}_{i,\cdot}\right\|_{\psi_{a}}\Big{\\{}1+\big{(}2+\tau\big{)}\ln(np)\Big{\\}}^{\frac{1}{a}}\sqrt{\ln(np)}$

with probability at least $1-\frac{2}{n^{1+\tau}p^{\tau}}$.

######  Lemma D.5.

Suppose Assumptions 5.1, 5.2, and 5.3 hold. Then $\forall\tau>0$

$\displaystyle\|\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho}\|$
$\displaystyle\leq C\sqrt{n}\left(\bar{A}+\kappa+K_{a}\right)$
$\displaystyle+\sqrt{1+\tau}\sqrt{p}(K_{a}+\bar{A}\bar{K})\left\\{1+(2+\tau)\ln(np)\right\\}^{\frac{1}{a}}\sqrt{\ln(np)}$

w.p. at least $1-\frac{2}{n^{1+\tau}p^{\tau}}$.

###### Proof.

Appealing to Lemma D.1

$\displaystyle\|\mathbb{E}[(\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho})^{T}(\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho})]\|$
$\displaystyle\leq\rho_{\max}(1-\rho_{\min})\left(\max_{j\in[p]}\|A_{\cdot,j}\|_{2}^{2}+{\|diag(\mathbb{E}[\boldsymbol{H}^{T}\boldsymbol{H}])\|}\right)+\rho_{\max}\|\mathbb{E}[\boldsymbol{H}^{T}\boldsymbol{H}]\|$
$\displaystyle\leq\max_{j\in[p]}\|A_{\cdot,j}\|_{2}^{2}+{\|diag(\mathbb{E}[\boldsymbol{H}^{T}\boldsymbol{H}])\|}+\|\mathbb{E}[\boldsymbol{H}^{T}\boldsymbol{H}]\|.$

Analyzing each term

$\displaystyle\max_{j\in[p]}\|A_{\cdot,j}\|_{2}^{2}$ $\displaystyle\leq
n\bar{A}^{2};$
$\displaystyle\|diag(\mathbb{E}[\boldsymbol{H}^{T}\boldsymbol{H}])\|$
$\displaystyle=\left\|diag\left(\sum_{i\in[n]}\mathbb{E}[H_{i,\cdot}^{T}H_{i,\cdot}]\right)\right\|$
$\displaystyle\leq
n\max_{i\in[n]}\|diag(\mathbb{E}[H_{i,\cdot}^{T}H_{i,\cdot}])\|$
$\displaystyle=n\max_{i\in[n],j\in[p]}|\mathbb{E}[H_{ij}^{2}]|$
$\displaystyle\leq nCK_{a};$
$\displaystyle\|\mathbb{E}[\boldsymbol{H}^{T}\boldsymbol{H}]\|$
$\displaystyle=\left\|\sum_{i\in[n]}\mathbb{E}[H_{i,\cdot}^{T}H_{i,\cdot}]\right\|$
$\displaystyle\leq n\max_{i\in[n]}\|\mathbb{E}[H_{i,\cdot}^{T}H_{i,\cdot}]\|$
$\displaystyle\leq n\kappa^{2}.$

The result follows by plugging in these results as well as Lemma D.3 into
Lemma D.4. ∎

######  Proposition D.2 ($\mathcal{E}_{1}$).

Under Assumptions 5.1, 5.2, and 5.3

$\mathbb{P}(\mathcal{E}_{1}^{c})\leq\frac{2}{n^{11}p^{10}}<\frac{2}{n^{10}p^{10}}.$

###### Proof.

Immediate by Lemma D.5, setting $\tau=10$ and simplifying the bound. ∎

Analyzing $\mathcal{E}_{2}$ and $\mathcal{E}_{3}$

######  Lemma D.6 (Lemma H.4 of [Agarwal et al., 2021]).

Let $X_{1},\ldots,X_{n}$ be independent random variables with mean zero. For
$a\geq 1$,

$\left\|\sum_{i=1}^{n}X_{i}\right\|_{\psi_{a}}\leq
C\left(\sum_{i=1}^{n}\left\|X_{i}\right\|_{\psi_{a}}^{2}\right)^{1/2}.$

######  Lemma D.7.

Under Assumptions 5.1, 5.2, and 5.3

$\|Z_{\cdot,j}-\rho_{j}A_{\cdot,j}\|_{\psi_{a}}\leq C(K_{a}+\bar{A}\bar{K}).$

###### Proof.

Observe that

$\displaystyle\left\|Z_{\cdot,j}-\rho_{j}A_{\cdot,j}\right\|_{\psi_{a}}$
$\displaystyle=\sup_{u\in\mathbb{S}^{n-1}}\left\|u^{T}\big{(}Z_{\cdot,j}-\rho_{j}A_{\cdot,j}\big{)}\right\|_{\psi_{a}}$
$\displaystyle=\sup_{u\in\mathbb{S}^{n-1}}\left\|u^{T}\big{(}\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho}\big{)}e_{j}\right\|_{\psi_{a}}$
$\displaystyle=\sup_{u\in\mathbb{S}^{n-1}}\left\|\sum_{i=1}^{n}u_{i}\big{(}Z_{i,\cdot}-A_{i,\cdot}\boldsymbol{\rho}\big{)}e_{j}\right\|_{\psi_{a}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}C\sup_{u\in\mathbb{S}^{n-1}}\left(\sum_{i=1}^{n}u_{i}^{2}\left\|\big{(}Z_{i,\cdot}-A_{i,\cdot}\boldsymbol{\rho}\big{)}e_{j}\right\|_{\psi_{a}}^{2}\right)^{1/2}$
$\displaystyle\leq
C\max_{i\in[n]}\left\|(Z_{i,\cdot}-A_{i,\cdot}\boldsymbol{\rho})e_{j}\right\|_{\psi_{a}},$

where (a) follows from Lemma D.6. Then the conclusion follows from Lemmas D.2
and D.3. ∎

######  Lemma D.8 (Lemma I.7 of [Agarwal et al., 2021]).

Let $W_{1},\ldots,W_{n}$ be a sequence of $\psi_{a}$-random variables for some
$a\geq 1$. For any $t\geq 0$,

$\mathbb{P}\left(\sum_{i=1}^{n}W_{i}^{2}>t\right)\leq
2\sum_{i=1}^{n}\exp\left\\{-\left(\frac{t}{n\|W_{i}\|_{\psi_{a}}^{2}}\right)^{a/2}\right\\}.$

######  Proposition D.3 ($\mathcal{E}_{2}$).

Under Assumptions 5.1, 5.2, and 5.3

$\mathbb{P}(\mathcal{E}_{2}^{c})\leq\frac{2}{n^{10}p^{10}}$

###### Proof.

Fix $j$. Write

$\|Z_{\cdot,j}-\rho_{j}A_{\cdot,j}\|_{2}^{2}=\sum_{i=1}^{n}W_{i}^{2},\quad
W_{i}=e_{i}^{T}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j}).$

By Lemmas D.2 and D.7,

$\|W_{i}\|_{\psi_{a}}\leq\|Z_{\cdot,j}-\rho_{j}A_{\cdot,j}\|_{\psi_{a}}\leq
C(K_{a}+\bar{K}\bar{A})$

By Lemma D.8, the union bound, and appropriate choice of constant $C$ in the
definition of $\Delta_{H}$, we have

$\displaystyle\mathbb{P}(\mathcal{E}_{2}^{c})$
$\displaystyle\leq\sum_{j=1}^{p}\mathbb{P}\left(\Big{\|}Z_{\cdot,j}-\rho_{j}A_{\cdot,j}\Big{\|}_{2}^{2}>n\Delta_{H}\right)$
$\displaystyle\leq 2\sum_{j=1}^{p}\sum_{i=1}^{n}\exp\left(-11\ln(np)\right)$
$\displaystyle=\frac{2}{n^{10}p^{10}}.$

∎

######  Proposition D.4 ($\mathcal{E}_{3}$).

Under Assumptions 5.1, 5.2, and 5.3

$\mathbb{P}(\mathcal{E}_{3}^{c})\leq\frac{2}{n^{10}p^{10}}.$

###### Proof.

The key equality is

$\|\boldsymbol{U}_{k}\boldsymbol{U}_{k}^{T}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})\|_{2}^{2}=\sum_{i=1}^{k}W_{i}^{2},\quad
W_{i}=u_{i}^{T}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j}).$

To see that it holds, set $v=Z_{\cdot,j}-\rho_{j}A_{\cdot,j}$. Then

$\|\boldsymbol{U}_{k}\boldsymbol{U}_{k}^{T}v\|_{2}^{2}=v^{T}\boldsymbol{U}_{k}\boldsymbol{U}_{k}^{T}\boldsymbol{U}_{k}\boldsymbol{U}_{k}^{T}v=v^{T}\boldsymbol{U}_{k}\boldsymbol{U}_{k}^{T}v=W^{T}W.$

The rest of the argument is analogous to Proposition D.3. ∎

Analyzing $\mathcal{E}_{4}$ and $\mathcal{E}_{5}$

######  Proposition D.5 ($\mathcal{E}_{4}$).

Under Assumption 5.3,

$\mathbb{P}(\mathcal{E}_{4}^{c})\leq\frac{2}{n^{10}p^{10}}.$

###### Proof.

Fix $\delta>1$. Define the event

$\mathcal{E}_{(j)}=\left\\{\frac{1}{\delta}\rho_{j}\leq\hat{\rho}_{j}\leq\delta\rho_{j}\right\\}.$

By the Chernoff bound in for binary random variables [Agarwal et al., 2021,
Lemma I.5]

$\mathbb{P}(\mathcal{E}^{c}_{(j)})\leq
2\exp\left(-\frac{(\delta-1)^{2}}{2\delta^{2}}n\rho_{j}\right)\leq
2\exp\left(-\frac{(\delta-1)^{2}}{2\delta^{2}}n\rho_{\min}\right).$

Hence by De Morgan’s law and the union bound

$\mathbb{P}(\mathcal{E}_{4}^{c})=\mathbb{P}\left(\left\\{\bigcap_{j\in[p]}\mathcal{E}_{(j)}\right\\}^{c}\right)=\mathbb{P}\left(\bigcup_{j\in[p]}\mathcal{E}^{c}_{(j)}\right)\leq
2p\exp\left(-\frac{(\delta-1)^{2}}{2\delta^{2}}n\rho_{\min}\right).$

To arrive at the desired result, solve

$\frac{2}{n^{10}p^{10}}\geq\frac{2}{n^{11}p^{10}}=2p\exp\left(-\frac{(\delta-1)^{2}}{2\delta^{2}}n\rho_{\min}\right)$

for $\delta$. ∎

######  Lemma D.9.

$\rho_{\min}>\frac{23\ln(np)}{n}$ implies $\delta\leq C<\infty$.

###### Proof.

By definition of $\delta$. ∎

######  Proposition D.6 ($\mathcal{E}_{5}$).

Under Assumption 5.3,

$\mathbb{P}(\mathcal{E}_{5}^{c})\leq\frac{2}{n^{10}p^{10}}.$

###### Proof.

Define the event

$\mathcal{E}_{(j)}=\\{|\hat{\rho}_{j}-\rho_{j}|\leq t\\}.$

By Hoeffding’s inequality for bounded random variables

$\mathbb{P}(\mathcal{E}^{c}_{(j)})\leq 2\exp\left(-2nt^{2}\right).$

Hence by De Morgan’s law and the union bound

$\mathbb{P}(\mathcal{E}_{5}^{c})=\mathbb{P}\left(\left\\{\bigcap_{j\in[p]}\mathcal{E}_{(j)}\right\\}^{c}\right)=\mathbb{P}\left(\bigcup_{j\in[p]}\mathcal{E}^{c}_{(j)}\right)\leq
2p\exp\left(-2nt^{2}\right).$

To arrive at the desired result, solve

$\frac{2}{n^{10}p^{10}}\geq\frac{2}{n^{11}p^{10}}=2p\exp\left(-2nt^{2}\right)$

for $t$. ∎

Summary

Define the beneficial event as $\mathcal{E}:=\cap_{k=1}^{5}\mathcal{E}_{k}$
and the adverse event as $\mathcal{E}^{c}=\cup_{k=1}^{5}\mathcal{E}^{c}_{k}$,
where $\mathcal{E}_{1}$ to $\mathcal{E}_{5}$ are defined above.

######  Lemma D.10.

Suppose Assumptions 5.1, 5.2, and 5.3 hold. Then,

$\mathbb{P}(\mathcal{E}^{c})\leq\frac{10}{n^{10}p^{10}}.$

###### Proof.

By the union bound as well as Propositions D.2, D.3, D.4, D.5, and D.6 we have

$\mathbb{P}(\mathcal{E}^{c})\leq\sum_{k=1}^{5}\mathbb{P}(\mathcal{E}_{k}^{c})\leq\frac{10}{n^{10}p^{10}}.$

∎

####  D.3 High probability bound

Recall
$\boldsymbol{A}=\boldsymbol{A}^{\textsc{(lr)}}+\boldsymbol{E}^{\textsc{(lr)}}$
and $r=rank\\{\boldsymbol{A}^{\textsc{(lr)}}\\}$. We denote the SVDs

$\boldsymbol{A}^{\textsc{(lr)}}=\boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{V}^{T},\quad\hat{\boldsymbol{A}}=\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{\Sigma}}_{k}\hat{\boldsymbol{V}}_{k}^{T},\quad\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}=\hat{\boldsymbol{U}}\hat{\boldsymbol{\Sigma}}\hat{\boldsymbol{V}}^{T}$

identifying NA with $0$ in $\boldsymbol{Z}$. We denote $s_{k}=\Sigma_{kk}$ and
$\hat{s}_{k}=\hat{\Sigma}_{kk}$. Recall that
$\delta=\frac{1}{1-\sqrt{\frac{22\ln(np)}{n\rho_{\min}}}}$.

######  Definition D.1 (Thresholded projection operator).

Consider a matrix $\boldsymbol{B}\in\mathbb{R}^{n\times p}$ with the SVD
$\boldsymbol{B}=\sum_{i=1}^{n\wedge p}\sigma_{i}u_{i}v_{i}^{T}$. With a
specific choice of $\lambda\geq 0$, we define a function
$\varphi^{\boldsymbol{B}}_{\lambda}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ as
follows. For any vector $w\in\mathbb{R}^{n}$,

$\varphi^{\boldsymbol{B}}_{\lambda}(w)=\sum_{i=1}^{n\wedge
p}1(\sigma_{i}\geq\lambda)u_{i}u_{i}^{T}w.$

$\varphi^{\boldsymbol{B}}_{\lambda}$ is a linear operator that depends on the
singular values $\\{\sigma_{i}\\}$ and the left singular vectors $\\{u_{i}\\}$
of $\boldsymbol{B}$, as well as the threshold $\lambda$. If $\lambda=0$, then
use the shorthand $\varphi^{\boldsymbol{B}}=\varphi_{0}^{\boldsymbol{B}}$.

######  Lemma D.11 (Eq. 43 of [Agarwal et al., 2021]).

Take $\lambda^{*}=\hat{s}_{k}$, where $k$ is the PCA hyper-parameter. Then

$\hat{A}_{\cdot,j}=\frac{1}{\hat{\rho}_{j}}\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(Z_{\cdot,j}).$

######  Lemma D.12.

Suppose we pick the PCA hyper-parameter $k=r$. Then,

$\|\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}-\boldsymbol{A}^{\textsc{(lr)}}\|~{}\Big{|}~{}\\{\mathcal{E}_{1},\mathcal{E}_{4},\mathcal{E}_{5}\\}\leq
C\frac{\delta}{\rho_{\min}}\left((\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\sqrt{\frac{\ln(np)}{n}}\|\boldsymbol{A}^{\textsc{(lr)}}\|\right).$

###### Proof.

To begin, write

$\displaystyle\|\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}-\boldsymbol{A}^{\textsc{(lr)}}\|$
$\displaystyle={\|\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}-\boldsymbol{A}^{\textsc{(lr)}}\hat{\boldsymbol{\rho}}\hat{\boldsymbol{\rho}}^{-1}\|}$
$\displaystyle\leq{\|\hat{\boldsymbol{\rho}}^{-1}\|\|\boldsymbol{Z}-\boldsymbol{A}^{\textsc{(lr)}}\hat{\boldsymbol{\rho}}\|}$
$\displaystyle=\frac{\|\boldsymbol{Z}-\boldsymbol{A}^{\textsc{(lr)}}\hat{\boldsymbol{\rho}}\|}{\min_{j}\hat{\rho}_{j}}.$

By triangle inequality

$\|\boldsymbol{Z}-\boldsymbol{A}^{\textsc{(lr)}}\hat{\boldsymbol{\rho}}\|\leq\|\boldsymbol{Z}-\boldsymbol{A}^{\textsc{(lr)}}\boldsymbol{\rho}\|+\|\boldsymbol{A}^{\textsc{(lr)}}\|\|\boldsymbol{\rho}-\hat{\boldsymbol{\rho}}\|.$

Focusing on the first term, under $\mathcal{E}_{1}$

$\|\boldsymbol{Z}-\boldsymbol{A}^{\textsc{(lr)}}\boldsymbol{\rho}\|\leq\|\boldsymbol{Z}-\boldsymbol{A}\boldsymbol{\rho}\|+\|\boldsymbol{A}\boldsymbol{\rho}-\boldsymbol{A}^{\textsc{(lr)}}\boldsymbol{\rho}\|\leq(\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|.$

Focusing on the second term, under $\mathcal{E}_{5}$,

$\|\boldsymbol{\rho}-\hat{\boldsymbol{\rho}}\|\leq C\sqrt{\frac{\ln(np)}{n}}.$

Focusing on the denominator, under $\mathcal{E}_{4}$,

$\frac{1}{\hat{\rho}_{j}}\leq\frac{\delta}{\rho_{j}}\leq\frac{\delta}{\rho_{\min}}.$

∎

######  Remark D.1 (train and test).

The proof technique does not depend on whether
$\operatorname{\hat{\boldsymbol{\rho}}}^{\textsc{train}}$ or
$\operatorname{\hat{\boldsymbol{\rho}}}^{\textsc{test}}$ is used with
$\boldsymbol{Z}^{\textsc{train}}$, since $\mathcal{E}_{4}$ and
$\mathcal{E}_{5}$ hold for both empirical scalings.

######  Lemma D.13.

Suppose the conditions of Lemma D.12 hold. Then,

$\|\boldsymbol{U}\boldsymbol{U}^{T}-\hat{\boldsymbol{U}}_{r}\hat{\boldsymbol{U}}_{r}^{T}\|~{}\Big{|}~{}\\{\mathcal{E}_{1},\mathcal{E}_{4},\mathcal{E}_{5}\\}\leq
C\frac{\delta}{\rho_{\min}s_{r}}\left((\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\sqrt{\frac{\ln(np)}{n}}\|\boldsymbol{A}^{\textsc{(lr)}}\|\right).$

###### Proof.

By Wedin’s $\sin\Theta$ Theorem [Davis and Kahan, 1970, Wedin, 1972]

$\|\boldsymbol{U}\boldsymbol{U}^{T}-\hat{\boldsymbol{U}}_{r}\hat{\boldsymbol{U}}_{r}^{T}\|\leq\frac{\|\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}-\boldsymbol{A}^{\textsc{(lr)}}\|}{s_{r}}.$

Finally appeal to Lemma D.12. ∎

######  Lemma D.14.

Suppose $k=r$. Then for any $j\in[p]$

$\displaystyle\left\|\hat{{A}}_{\cdot,j}-A_{\cdot,j}\right\|^{2}_{2}~{}\Big{|}~{}\mathcal{E}$
$\displaystyle\leq\frac{C\delta^{4}}{\rho^{4}_{\min}}\Bigg{(}\frac{(n+p)\Delta_{H,op}^{2}+\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+(\ln(np)/n)\|\boldsymbol{A}^{\textsc{(lr)}}\|^{2}}{s_{r}^{2}}\Bigg{)}\bigg{(}n\Delta_{H}+\left\|A^{\textsc{(lr)}}_{\cdot,j}\right\|^{2}_{2}\bigg{)}$
$\displaystyle\quad+\frac{C\delta^{2}}{\rho^{2}_{\min}}r\Delta_{H}+C\frac{\delta^{2}}{\rho_{\min}^{2}}\frac{\ln(np)}{n}\left\|A_{\cdot,j}\right\|^{2}_{2}+C\left\|E_{\cdot,j}^{\textsc{(lr)}}\right\|^{2}_{2}.$

###### Proof.

We proceed in steps.

  1. 1.

Decomposition

Fix a column index $j\in[p]$. Observe that

$\hat{A}_{\cdot,j}-A_{\cdot,j}=\Big{\\{}\hat{A}_{\cdot,j}-\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}\big{(}A_{\cdot,j}\big{)}\Big{\\}}+\Big{\\{}\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}\big{(}A_{\cdot,j}\big{)}-A_{\cdot,j}\Big{\\}}.$

By hypothesis, $k=r$. Recall that
$\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}:\mathbb{R}^{n}\to\mathbb{R}^{n}$
is the projection operator onto the span of the top $r$ left singular vectors
$\\{\hat{u}_{1},...,\hat{u}_{r}\\}$ of
$\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}$, which are are
also the top $r$ left singular vectors of $\boldsymbol{Z}$ since
$\operatorname{\hat{\boldsymbol{\rho}}}^{-1}$ is diagonal. Hence

$\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(A_{\cdot,j})-A_{\cdot,j}\in
span\\{\hat{u}_{1},\ldots,\hat{u}_{r}\\}^{\perp}.$

By Lemma D.11,

$\hat{A}_{\cdot,j}-\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(A_{\cdot,j})=\frac{1}{\hat{\rho}_{j}}\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(Z_{\cdot,j})-\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(A_{\cdot,j})\in
span\\{\hat{u}_{1},\ldots,\hat{u}_{r}\\}.$

Therefore
$\langle\hat{A}_{\cdot,j}-\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(A_{\cdot,j}),\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(A_{\cdot,j})-A_{\cdot,j}\rangle=0$
and

$\Big{\|}\hat{A}_{\cdot,j}-A_{\cdot,j}\Big{\|}_{2}^{2}=\Big{\|}\hat{A}_{\cdot,j}-\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}\big{(}A_{\cdot,j}\big{)}\Big{\|}_{2}^{2}+\Big{\|}\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}\big{(}A_{\cdot,j}\big{)}-A_{\cdot,j}\Big{\|}_{2}^{2}.$

  2. 2.

First term

Again applying Lemma D.11, we can rewrite

$\displaystyle\hat{A}_{\cdot,j}-\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(A_{\cdot,j})$
$\displaystyle=\frac{1}{\hat{\rho}_{j}}\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(Z_{\cdot,j})-\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(A_{\cdot,j})$
$\displaystyle=\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}\Big{(}\frac{1}{\hat{\rho}_{j}}Z_{\cdot,j}-A_{\cdot,j}\Big{)}$
$\displaystyle=\frac{1}{\hat{\rho}_{j}}\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})+\frac{\rho_{j}-\hat{\rho}_{j}}{\hat{\rho}_{j}}\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(A_{\cdot,j}).$

Using the parallelogram law (or, equivalently, combining Cauchy-Schwartz and
AM-GM inequalities), we obtain

$\displaystyle\left\|\hat{A}_{\cdot,j}-\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(A_{\cdot,j})\right\|_{2}^{2}$
$\displaystyle=\left\|\frac{1}{\hat{\rho}_{j}}\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})+\frac{\rho_{j}-\hat{\rho}_{j}}{\hat{\rho}_{j}}\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(A_{\cdot,j})\right\|_{2}^{2}$
$\displaystyle\leq
2\,\left\|\frac{1}{\hat{\rho}_{j}}\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})\right\|_{2}^{2}+2\,\left\|\frac{\rho_{j}-\hat{\rho}_{j}}{\hat{\rho}_{j}}\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(A_{\cdot,j})\right\|_{2}^{2}$
$\displaystyle\leq\frac{2}{\hat{\rho}_{j}^{2}}\left\|\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})\right\|_{2}^{2}+2\Big{(}\frac{\rho_{j}-\hat{\rho}_{j}}{\hat{\rho}_{j}}\Big{)}^{2}\|A_{\cdot,j}\|_{2}^{2}$
$\displaystyle\leq\frac{2\delta^{2}}{\rho_{j}^{2}}\left\|\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})\right\|_{2}^{2}+C\frac{\delta^{2}}{\rho_{j}^{2}}\frac{\ln(np)}{n}\|A_{\cdot,j}\|_{2}^{2}.$
(10)

Here, we have used the fact that $\mathcal{E}_{4}$ and $\mathcal{E}_{5}$ imply

$\displaystyle\frac{1}{\hat{\rho_{j}}}$
$\displaystyle\leq\frac{\delta}{\rho_{j}},\quad\left(\frac{\rho_{j}-\hat{\rho_{j}}}{\hat{\rho_{j}}}\right)^{2}\leq\frac{\delta^{2}}{\rho_{j}^{2}}(\hat{\rho}_{j}-\rho_{j})^{2}\leq
C\frac{\delta^{2}}{\rho_{j}^{2}}\frac{\ln(np)}{n}.$

The first term of (10) can further be decomposed.

$\displaystyle\left\|\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})\right\|_{2}^{2}$
$\displaystyle\quad\leq
2\,\Big{\|}\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})-\varphi^{\boldsymbol{A}^{\textsc{(lr)}}}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})\Big{\|}_{2}^{2}$
(11)
$\displaystyle\quad+2\,\Big{\|}\varphi^{\boldsymbol{A}^{\textsc{(lr)}}}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})\Big{\|}_{2}^{2}.$

Finally, we bound (11). Given $k=r$, where $k$ is the PCA hyperparameter, we
can represent
$\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(w)=\hat{\boldsymbol{U}}_{r}\hat{\boldsymbol{U}}_{r}^{T}w$
and
$\varphi^{\boldsymbol{A}^{\textsc{(lr)}}}(w)=\boldsymbol{U}\boldsymbol{U}^{T}w$
for $w\in\mathbb{R}^{n}$. By Lemma D.13

$\displaystyle\Big{\|}\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})-\varphi^{\boldsymbol{A}^{\textsc{(lr)}}}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})\Big{\|}_{2}$
$\displaystyle\leq\|\boldsymbol{U}\boldsymbol{U}^{T}-\hat{\boldsymbol{U}}_{r}\hat{\boldsymbol{U}}_{r}^{T}\|\big{\|}Z_{\cdot,j}-\rho_{j}A_{\cdot,j}\big{\|}_{2}$
$\displaystyle\leq
C\frac{\delta}{\rho_{\min}s_{r}}\left((\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\sqrt{\frac{\ln(np)}{n}}\|\boldsymbol{A}^{\textsc{(lr)}}\|\right)\big{\|}Z_{\cdot,j}-\rho_{j}A_{\cdot,j}\big{\|}_{2}.$

Combining the inequalities together, we have

$\displaystyle\Big{\|}\hat{A}_{\cdot,j}-\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}\big{(}A_{\cdot,j}\big{)}\Big{\|}_{2}^{2}$
$\displaystyle\leq\frac{C\delta^{4}}{\rho_{\min}^{2}}\left(\frac{(\sqrt{n}+\sqrt{p})\Delta_{H,op}}{\rho_{\min}s_{r}}+\frac{\|\boldsymbol{E}^{\textsc{(lr)}}\|}{\rho_{\min}s_{r}}+\frac{\sqrt{\ln(np)/n}\|\boldsymbol{A}^{\textsc{(lr)}}\|}{\rho_{\min}s_{r}}\right)^{2}\big{\|}Z_{\cdot,j}-\rho_{j}A_{\cdot,j}\big{\|}_{2}^{2}$
$\displaystyle\quad+\frac{4\delta^{2}}{\rho_{\min}^{2}}\Big{\|}\varphi^{\boldsymbol{A}^{\textsc{(lr)}}}(Z_{\cdot,j}-\rho_{j}A_{\cdot,j})\Big{\|}_{2}^{2}+C\frac{\delta^{2}}{\rho_{\min}^{2}}\frac{\ln(np)}{n}\|A_{\cdot,j}\|_{2}^{2}.$
(12)

  3. 3.

Second term

We now bound the second term. Recalling
$\boldsymbol{A}=\boldsymbol{A}^{\textsc{(lr)}}+\boldsymbol{E}^{\textsc{(lr)}}$

$\displaystyle\left\|\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}\big{(}A_{\cdot,j}\big{)}-A_{\cdot,j}\right\|_{2}^{2}$
$\displaystyle=\left\|\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}\big{(}A^{\textsc{(lr)}}_{\cdot,j}+E^{\textsc{(lr)}}_{\cdot,j}\big{)}-A^{\textsc{(lr)}}_{\cdot,j}-E^{\textsc{(lr)}}_{\cdot,j}\right\|_{2}^{2}$
$\displaystyle\leq
2\,\left\|\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}\big{(}A^{\textsc{(lr)}}_{\cdot,j}\big{)}-A^{\textsc{(lr)}}_{\cdot,j}\right\|_{2}^{2}+2\,\left\|\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}\big{(}E^{\textsc{(lr)}}_{\cdot,j}\big{)}-E^{\textsc{(lr)}}_{\cdot,j}\right\|_{2}^{2}$
$\displaystyle=2\,\left\|\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}\big{(}A^{\textsc{(lr)}}_{\cdot,j}\big{)}-\varphi^{\boldsymbol{A}^{\textsc{(lr)}}}\big{(}A^{\textsc{(lr)}}_{\cdot,j}\big{)}\right\|_{2}^{2}+2\,\left\|\varphi^{\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}}_{\lambda^{*}}\big{(}E^{\textsc{(lr)}}_{\cdot,j}\big{)}-E^{\textsc{(lr)}}_{\cdot,j}\right\|_{2}^{2}$
$\displaystyle\leq
2\,\|\boldsymbol{U}\boldsymbol{U}^{T}-\hat{\boldsymbol{U}}_{r}\hat{\boldsymbol{U}}_{r}^{T}\|^{2}\left\|A^{\textsc{(lr)}}_{\cdot,j}\right\|_{2}^{2}+2\,\left\|E^{\textsc{(lr)}}_{\cdot,j}\right\|_{2}^{2}$
$\displaystyle\leq
C\delta^{2}\left(\frac{(\sqrt{n}+\sqrt{p})\Delta_{H,op}}{\rho_{\min}s_{r}}+\frac{\|\boldsymbol{E}^{\textsc{(lr)}}\|}{\rho_{\min}s_{r}}+\frac{\sqrt{\ln(np)/n}\|\boldsymbol{A}^{\textsc{(lr)}}\|}{\rho_{\min}s_{r}}\right)^{2}\left\|A^{\textsc{(lr)}}_{\cdot,j}\right\|_{2}^{2}+2\,\left\|E^{\textsc{(lr)}}_{\cdot,j}\right\|_{2}^{2}.$
(13)

where the final inequality appeals to Lemma D.13.

Inserting (12) and (13) back into the decomposition, plugging the bounds in
events $\mathcal{E}_{2},\mathcal{E}_{3}$, and combining terms completes the
proof.

∎

######  Remark D.2 (train and test).

Since $\\{\hat{u}_{1},...,\hat{u}_{r}\\}$ are the left singular vectors of
$\boldsymbol{Z}^{\textsc{train}}$,
$\boldsymbol{Z}^{\textsc{train}}\operatorname{\hat{\boldsymbol{\rho}}}^{\textsc{train}}$,
and
$\boldsymbol{Z}^{\textsc{train}}\operatorname{\hat{\boldsymbol{\rho}}}^{\textsc{test}}$,
the argument holds for both cases of interest.

######  Lemma D.15.

Suppose $k=r$. Let Assumptions 5.1 and 5.4 hold. If
$\rho_{\min}>\frac{23\ln(np)}{n}$ then

$\displaystyle\left\|\hat{\boldsymbol{A}}-\boldsymbol{A}\right\|^{2}_{2,\infty}~{}\Big{|}~{}\mathcal{E}$
$\displaystyle\leq\frac{C(K_{a}+\bar{K}\bar{A})^{2}}{\rho^{4}_{\min}}\bigg{(}r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}\bigg{)}\ln^{2}(np)+C\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}_{2,\infty}.$

###### Proof.

By Lemma D.14,

$\displaystyle\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{2}_{2,\infty}~{}\Big{|}~{}\mathcal{E}$
$\displaystyle\leq\frac{C\delta^{4}}{\rho^{4}_{\min}}\Bigg{(}\frac{(n+p)\Delta_{H,op}^{2}+\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+(\ln(np)/n)\|\boldsymbol{A}^{\textsc{(lr)}}\|^{2}}{s_{r}^{2}}\Bigg{)}\bigg{(}n\Delta_{H}+\left\|A^{\textsc{(lr)}}_{\cdot,j}\right\|^{2}_{2}\bigg{)}$
$\displaystyle\quad+\frac{C\delta^{2}}{\rho^{2}_{\min}}r\Delta_{H}+C(\delta-1)^{2}\left\|A_{\cdot,j}\right\|^{2}_{2}+C\left\|E_{\cdot,j}^{\textsc{(lr)}}\right\|^{2}_{2}$

By Lemma D.9

$\displaystyle\Delta_{H}$
$\displaystyle=C(K_{a}+\bar{K}\bar{A})^{2}\ln^{2}(np),\quad\delta=\frac{1}{1-\sqrt{\frac{22\ln(np)}{n\rho_{\min}}}}\leq
C.$

By Assumption 5.1 and Lemma C.4,

$\displaystyle\|\boldsymbol{A}^{\textsc{(lr)}}\|^{2}_{2,\infty}$
$\displaystyle\leq
Cn\bar{A}^{2},\quad\|\boldsymbol{A}^{\textsc{(lr)}}\|^{2}\leq Cnp\bar{A}^{2}.$

The definition of $\delta$ implies

$\displaystyle
C\frac{\delta^{2}}{\rho_{\min}^{2}}\frac{\ln(np)}{n}\left\|A_{\cdot,j}\right\|^{2}_{2}~{}\leq~{}C\frac{\ln(np)}{n\rho^{2}_{\min}}\left\|A_{\cdot,j}\right\|^{2}_{2}~{}\leq~{}C\bar{A}^{2}\frac{\ln(np)}{\rho^{2}_{\min}}.$

The second term dominates the third. Within the first term, $n\Delta_{H}$
dominates $\left\|A^{\textsc{(lr)}}_{\cdot,j}\right\|^{2}_{2}$. Distribute the
$n$, then factor out $\frac{\Delta_{H}}{\rho^{4}_{\min}}$ to combine the first
term with the second. ∎

######  Lemma D.16.

Let the conditions of Lemma D.15 hold. Then

$\displaystyle\left\|\hat{\boldsymbol{A}}-\boldsymbol{A}\right\|^{2}_{2,\infty}~{}\Big{|}~{}\mathcal{E}$
$\displaystyle\leq
C\bar{A}^{4}(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}\cdot\frac{r\ln^{5}(np)}{\rho_{\min}^{4}}\left(1+\frac{n}{p}+n\Delta_{E}^{2}\right).$

###### Proof.

We simplify Lemma D.15 appealing to Assumption 5.4. Recall

$\displaystyle\left\|\hat{\boldsymbol{A}}-\boldsymbol{A}\right\|^{2}_{2,\infty}~{}\Big{|}~{}\mathcal{E}$
$\displaystyle\leq\frac{C\bar{A}^{2}(K_{a}+\bar{K})^{2}}{\rho^{4}_{\min}}\bigg{(}r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}\bigg{)}\ln^{2}(np)$
$\displaystyle\quad+C\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}_{2,\infty}.$

Note that

$\displaystyle s_{r}^{2}$ $\displaystyle\geq
C\frac{np}{r},\quad\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}\leq
np\Delta_{E}^{2},\quad\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}_{2,\infty}\leq
n\Delta_{E}^{2},\quad\Delta_{H,op}^{2}\leq
C\cdot\bar{A}^{2}(\kappa+\bar{K}+K_{a})^{2}\ln^{3}(np).$

Then

$\displaystyle\left\|\hat{\boldsymbol{A}}-\boldsymbol{A}\right\|^{2}_{2,\infty}~{}\Big{|}~{}\mathcal{E}$
$\displaystyle\leq\frac{C\bar{A}^{2}(K_{a}+\bar{K})^{2}}{\rho^{4}_{\min}}\bigg{(}r+\frac{n(n+p)\cdot\bar{A}^{2}(\kappa+\bar{K}+K_{a})^{2}\ln^{3}(np)+n\cdot
np\Delta_{E}^{2}}{\frac{np}{r}}\bigg{)}\ln^{2}(np)$
$\displaystyle\quad+Cn\Delta_{E}^{2}$ $\displaystyle\leq
C(K_{a}+\bar{K})^{2}\bar{A}^{4}(\kappa+\bar{K}+K_{a})^{2}\cdot\frac{r\ln^{5}(np)}{\rho_{\min}^{4}}\left(1+\frac{n}{p}+n\Delta_{E}^{2}\right).$

∎

####  D.4 Main result

######  Lemma D.17.

Suppose Assumptions 5.1, 5.2, and 5.3 hold. Then

$\mathbb{E}\left[\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{2}_{2,\infty}\operatorname{\mathbbm{1}}\\{\mathcal{E}^{c}\\}\right]\leq\Delta_{adv}\frac{1}{n^{2}p^{5}},\quad\Delta_{adv}:=C\Big{\\{}\bar{A}^{2}+K_{a}^{2}\ln^{2}(np)\Big{\\}}.$

###### Proof.

By Cauchy-Schwarz

$\displaystyle\mathbb{E}\left[\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{2}_{2,\infty}\operatorname{\mathbbm{1}}\\{\mathcal{E}^{c}\\}\right]$
$\displaystyle\leq\sqrt{\mathbb{E}\left[\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{4}_{2,\infty}\right]}\sqrt{\mathbb{E}\left[\operatorname{\mathbbm{1}}^{2}\\{\mathcal{E}^{c}\\}\right]}.$

Consider the first factor. Note that

$\displaystyle\max_{j\in[p]}\|\hat{A}_{\cdot,j}-A_{\cdot,j}\|_{2}$
$\displaystyle\leq\max_{j\in[p]}\|\hat{A}_{\cdot,j}\|_{2}+\max_{j\in[p]}\,\|A_{\cdot,j}\|_{2}.$

In the first term,

$\displaystyle\max_{j\in[p]}\|\hat{A}_{\cdot,j}\|_{2}$
$\displaystyle\leq\max_{j\in[p]}\frac{1}{\hat{\rho}_{j}}\|Z_{\cdot,j}\|_{2}$
$\displaystyle\leq n~{}\max_{j\in[p]}\|Z_{\cdot,j}\|_{2}$ $\displaystyle\leq
n\cdot\sqrt{n}\max_{i\in[n],j\in[p]}|Z_{ij}|$ $\displaystyle\leq
n\cdot\sqrt{n}(\bar{A}+\max_{i,j}|H_{ij}|).$

In the second term

$\displaystyle\max_{j\in[p]}\,\|A_{\cdot,j}\|_{2}$
$\displaystyle\leq\sqrt{n}\bar{A}.$

Collecting results

$\displaystyle\mathbb{E}\left[\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{4}_{2,\infty}\right]$
$\displaystyle\leq\mathbb{E}[\\{n^{\frac{3}{2}}(\bar{A}+\max_{i,j}|H_{ij}|)+\sqrt{n}\bar{A}\\}^{4}]$
$\displaystyle\leq\mathbb{E}[\\{n^{\frac{3}{2}}(2\bar{A}+\max_{i,j}|H_{ij}|)\\}^{4}]$
$\displaystyle\leq Cn^{6}(\bar{A}^{4}+\mathbb{E}[\max_{i,j}|H_{ij}|^{4}])$
$\displaystyle\leq Cn^{6}\\{\bar{A}^{4}+K_{a}^{4}\ln^{4}(np)\\}.$

The final inequality holds because for any $a>0$ and $\theta\geq 1$, if
$H_{ij}$ is a $\psi_{a}$-random variable then $\big{|}H_{ij}\big{|}^{\theta}$
is a $\psi_{a/\theta}$-random variable. With the choice of $\theta=4$, we have
that

$\mathbb{E}[\max_{i,j}|H_{ij}|^{4}]\leq CK_{a}^{4}\ln^{\frac{4}{a}}(np).$

By Lemma D.10,

$\mathbb{E}\left[\operatorname{\mathbbm{1}}^{2}\\{\mathcal{E}^{c}\\}\right]=\mathbb{E}\left[\operatorname{\mathbbm{1}}\\{\mathcal{E}^{c}\\}\right]=\mathbb{P}(\mathcal{E}^{c})\leq\frac{C}{n^{10}p^{10}}.$

Collecting results, we find that

$\displaystyle\mathbb{E}\left[\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{2}_{2,\infty}\operatorname{\mathbbm{1}}\\{\mathcal{E}^{c}\\}\right]$
$\displaystyle\leq
C\sqrt{n^{6}(\bar{A}^{4}+K_{a}^{4}\ln^{4}(np))}\sqrt{\frac{1}{n^{10}p^{10}}}$
$\displaystyle=C\sqrt{\bar{A}^{4}+K_{a}^{4}\ln^{4}(np)}\sqrt{\frac{1}{n^{4}p^{10}}}$
$\displaystyle\leq
C\Big{(}\bar{A}^{2}+K_{a}^{2}\ln^{2}(np)\Big{)}\frac{1}{n^{2}p^{5}}.$

∎

######  Remark D.3 (train and test).

The result holds for both $\hat{\boldsymbol{A}}^{\textsc{train}}$ and
$\hat{\boldsymbol{A}}^{\textsc{test}}$ because
$\hat{\rho}^{\textsc{train}}_{j},\hat{\rho}^{\textsc{test}}_{j}\geq\frac{1}{n}$.

###### Proof of Theorem 5.1.

Define $\mathcal{E}:=\cap_{k=1}^{5}\mathcal{E}_{k}$ where $\mathcal{E}_{1}$ to
$\mathcal{E}_{5}$ are given above.

$\displaystyle\mathbb{E}\Big{[}\left\|\hat{\boldsymbol{A}}-\boldsymbol{A}\right\|^{2}_{2,\infty}\Big{]}$
$\displaystyle=\mathbb{E}\bigg{[}\left\|\hat{\boldsymbol{A}}-\boldsymbol{A}\right\|^{2}_{2,\infty}\cdot\operatorname{\mathbbm{1}}\\{\mathcal{E}\\}\bigg{]}+\mathbb{E}\left[\left\|\hat{\boldsymbol{A}}-\boldsymbol{A}\right\|^{2}_{2,\infty}\cdot\operatorname{\mathbbm{1}}\\{\mathcal{E}^{c}\\}\right].$

Focusing on the former term, by Lemma D.16

$\displaystyle\mathbb{E}\left[\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{2}_{2,\infty}\operatorname{\mathbbm{1}}\\{\mathcal{E}\\}\right]$
$\displaystyle\leq
C\bar{A}^{4}(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}\cdot\frac{r\ln^{5}(np)}{\rho_{\min}^{4}}\left(1+\frac{n}{p}+n\Delta_{E}^{2}\right).$

Focusing on the latter term

$\displaystyle\mathbb{E}\left[\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{2}_{2,\infty}\operatorname{\mathbbm{1}}\\{\mathcal{E}^{c}\\}\right]$
$\displaystyle\leq\Delta_{adv}\frac{1}{n^{2}p^{5}},\quad\Delta_{adv}=C\Big{(}\bar{A}^{2}+K_{a}^{2}\ln^{2}(np)\Big{)}.$

which is dominated by the former term.

Throughout this section, the arguments given are conditional on
$\boldsymbol{A}$. They imply the same rate unconditional on $\boldsymbol{A}$
by the law of iterated expectations. ∎

######  Corollary D.1 (Finite sample data cleaning rate).

Suppose the conditions of Theorem 5.1 hold, as well as Assumption C.1. Then

$\frac{1}{m}\mathbb{E}\|b(D,\hat{\boldsymbol{A}})-b(D,\boldsymbol{A})\|^{2}_{2,\infty}\leq
C_{b}^{\prime}C_{1}\cdot\frac{r\ln^{5}(mp)}{\rho_{\min}^{4}}\left(\frac{1}{m}+\frac{1}{p}+\Delta_{E}^{2}\right)$

where $C_{1}=C\cdot\bar{A}^{4}(K_{a}+\bar{K})^{2}(\kappa+K_{a}+\bar{K})^{2}$.

###### Proof of Corollary D.1.

Immediate from Theorem 5.1 and the definition of $C_{b}^{\prime}$ in
Assumption C.1. ∎

###  Appendix E Error-in-variable regression

The outline of the argument is as follows

  1. 1.

define train, test, and general error

  2. 2.

establish orthogonality properties

  3. 3.

analyze train error (more precisely, $\|\hat{\beta}-\beta^{*}\|_{2}$)

  4. 4.

analyze test error (more precisely,
$\|\hat{\boldsymbol{A}}^{\textsc{test}}\hat{\beta}-\boldsymbol{A}^{\textsc{test}}\beta^{*}\|_{2}^{2}$)

  5. 5.

analyze general error (more precisely,
$\|\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\beta}-\gamma_{0}(\boldsymbol{A}^{\textsc{test}})\|_{2}^{2}$)

####  E.1 Notation and preliminaries

As in Appendix D, we identify NA with $0$ in $\boldsymbol{Z}$ for the
remainder of the appendix. We also use the notation $\boldsymbol{A}$ rather
than $\boldsymbol{X}$. Recall that
$(\operatorname{\hat{\boldsymbol{\rho}}},\hat{\beta})$ are calculated from
train. We slightly abuse notation by letting $n$ be the number of observations
in train (and also test), departing from the notation of the main text. We
write $\|\cdot\|=\|\cdot\|_{op}$. We write the proofs without nonlinear
dictionaries for clarity. Then we extend our results to allow for nonlinear
dictionaries in subsequent remarks. We also let
$\bar{A}^{\prime}=\bar{A}^{d_{\max}}$ and
$\rho^{\prime}_{\min}=\frac{\rho_{\min}}{d_{\max}\bar{A}^{\prime}}$. Finally,
to lighten notation, we abbreviate $b(D_{i},A_{i,\cdot})$ as $b(A_{i,\cdot})$
when it is contextually clear.

#####  E.1.1 Errors

Consider the following quantities:

$\displaystyle\tilde{\textsc{train}}\textsc{ error}$
$\displaystyle=\frac{1}{n}\mathbb{E}\left[\sum_{i\in\textsc{train}}\\{\hat{A}_{i,\cdot}\hat{\beta}-\gamma_{0}(A_{i,\cdot})\\}^{2}\right]$
$\displaystyle\tilde{\textsc{test}}\textsc{ error}$
$\displaystyle=\frac{1}{n}\mathbb{E}\left[\sum_{i\in\textsc{test}}\\{\hat{A}_{i,\cdot}\hat{\beta}-\gamma_{0}(A_{i,\cdot})\\}^{2}\right]$
general error
$\displaystyle=\frac{1}{n}\mathbb{E}\left[\sum_{i\in\textsc{test}}\\{\hat{\gamma}_{i}-\gamma_{0}(A_{i,\cdot})\\}^{2}\right],\quad\hat{\gamma}_{i}=Z_{i,\cdot}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\beta}=Z_{i,\cdot}\tilde{\beta}.$

The $\tilde{\textsc{train}}\textsc{ error}$ is standard for PCR. The
$\tilde{\textsc{test}}\textsc{ error}$ is similar to [Agarwal et al., 2020a].
The general error is a new quantity introduced in this paper, specific to our
variant of PCR that does not involve cleaning test. As we will see, post
multiplying by $\tilde{\beta}$ performs a kind of implicit cleaning. By
avoiding explicit cleaning, we preserve independence across rows in test,
which is critical for our inference argument. Therefore the key result is
about general error. En route, we will analyze quantities we refer to as train
error and test error, which are closely related to
$\tilde{\textsc{train}}\textsc{ error}$ and $\tilde{\textsc{test}}\textsc{
error}$. When using a dictionary, the updated estimator is
$\hat{\gamma}_{i}=b(D_{i},Z_{i,\cdot}\operatorname{\hat{\boldsymbol{\rho}}}^{-1})\hat{\beta}=b(D_{i},Z_{i,\cdot})\tilde{\beta}$
for an updated definition of $\tilde{\beta}$.

###### Proof of Proposition 4.2.

For $i\in\textsc{test}$

$\displaystyle\hat{\gamma}(D_{i},Z_{i,\cdot})$
$\displaystyle=b(D_{i},Z_{i,\cdot}\operatorname{\hat{\boldsymbol{\rho}}}^{-1})\hat{\beta}$
$\displaystyle=\begin{bmatrix}D_{i}Z_{i,\cdot}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}&(1-D_{i})Z_{i,\cdot}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\end{bmatrix}\begin{bmatrix}\hat{\beta}^{\textsc{treat}}\\\
\hat{\beta}^{\textsc{untreat}}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}D_{i}Z_{i,\cdot}&(1-D_{i})Z_{i,\cdot}\end{bmatrix}\begin{bmatrix}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\beta}^{\textsc{treat}}\\\
\operatorname{\hat{\boldsymbol{\rho}}}^{-1}\hat{\beta}^{\textsc{untreat}}\end{bmatrix}.$

Finally, independence holds conditional on train since
$(\operatorname{\hat{\boldsymbol{\rho}}},\hat{\beta})$ are calculated from
train, so the only randomness that remains is in $(D_{i},Z_{i,\cdot})$ and
$(D_{j},Z_{j,\cdot})$ which are i.n.i.d. ∎

#####  E.1.2 SVDs

Recall that the fill operator rescales using
$\operatorname{\hat{\boldsymbol{\rho}}}$ calculated from train. Denote the
SVDs

$\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}=\boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{V}^{T},\quad\textsc{fill}(\boldsymbol{Z}^{\textsc{train}})=\boldsymbol{Z}^{\textsc{train}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}=\hat{\boldsymbol{U}}\hat{\boldsymbol{\Sigma}}\hat{\boldsymbol{V}}^{T},\quad\hat{\boldsymbol{A}}^{\textsc{train}}=\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{\Sigma}}_{k}\hat{\boldsymbol{V}}_{k}^{T}.$

In this notation, $\boldsymbol{V}$ is an orthonormal basis for
$\textsc{row}\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\}$. Let
$\boldsymbol{V}_{\perp}$ be an orthonormal basis for the orthogonal complement
to $\textsc{row}\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\}$. In other
words, for any element $v\in\textsc{row}(\boldsymbol{V}^{T})$,
$\boldsymbol{V}^{T}_{\perp}v=0$. Likewise we define
$\hat{\boldsymbol{V}}_{k,\perp}$. Define $s_{k}$ and $\hat{s}_{k}$ as the
$k$-th singular values of $\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}$ and
$\hat{\boldsymbol{A}}^{\textsc{train}}$, respectively.

Next, denote the SVDs

$\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}=\boldsymbol{U}^{\prime}\boldsymbol{\Sigma}^{\prime}(\boldsymbol{V}^{\prime})^{T},\quad\textsc{fill}(\boldsymbol{Z}^{\textsc{test}})=\boldsymbol{Z}^{\textsc{test}}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}=\hat{\boldsymbol{U}}^{\prime}\hat{\boldsymbol{\Sigma}}^{\prime}(\hat{\boldsymbol{V}}^{\prime})^{T},\quad\hat{\boldsymbol{A}}^{\textsc{test}}=\hat{\boldsymbol{U}}^{\prime}_{k}\hat{\boldsymbol{\Sigma}}^{\prime}_{k}(\hat{\boldsymbol{V}}^{\prime}_{k})^{T}.$

We define $\boldsymbol{V}^{\prime}_{\perp}$ and
$\hat{\boldsymbol{V}}^{\prime}_{\perp}$ analogously to
$\boldsymbol{V}_{\perp}$. Define $s^{\prime}_{k}$ and $\hat{s}^{\prime}_{k}$
as the $k$-th singular values of
$\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}$ and
$\hat{\boldsymbol{A}}^{\textsc{test}}$, respectively.

Finally, denote the SVD of the row-wise concatenation of
$\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}$ and
$\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}$ as

$\begin{bmatrix}\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\\
\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\end{bmatrix}=\tilde{\boldsymbol{U}}\tilde{\boldsymbol{\Sigma}}\tilde{\boldsymbol{V}}^{T}.$

We define $\tilde{\boldsymbol{V}}_{\perp}$ analogously to
$\boldsymbol{V}_{\perp}$ but with respect to the row-wise concatenation of
$\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}$ and
$\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}$.

######  Remark E.1 (Dictionary).

As discussed in Assumption C.2, to simplify our dictionary discussion, we
impose that $r^{\prime}=k^{\prime}$. Given the alternative definitions of
$(\beta^{*},\hat{\beta})$, our analysis requires that we consider the
alternative SVDs

$b\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\}=\boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{V}^{T},\quad
b(\hat{\boldsymbol{A}}^{\textsc{train}})=\hat{\boldsymbol{U}}_{r^{\prime}}\hat{\boldsymbol{\Sigma}}_{r^{\prime}}\hat{\boldsymbol{V}}_{r^{\prime}}^{T}$

and

$b\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\\}=\boldsymbol{U}^{\prime}\boldsymbol{\Sigma}^{\prime}(\boldsymbol{V}^{\prime})^{T},\quad
b(\hat{\boldsymbol{A}}^{\textsc{test}})=\hat{\boldsymbol{U}}^{\prime}_{r^{\prime}}\hat{\boldsymbol{\Sigma}}^{\prime}_{r^{\prime}}(\hat{\boldsymbol{V}}^{\prime}_{r^{\prime}})^{T}.$

We slightly abuse notation and depart from the main text by re-using the SVD
symbols. In particular, we denote the $r^{\prime}$-th singular value of
$\hat{\boldsymbol{\Sigma}}_{r^{\prime}}$ by $\hat{s}_{r^{\prime}}$.

####  E.2 Orthogonality

The goal of this section is to establish orthogonality properties for the
analysis to follow. We begin by verifying that Assumption 5.6 holds with high
probability under auxiliary assumptions. In particular, Proposition E.1
provides intuition for how Assumption 5.6 can hold even with i.n.i.d. data.
The auxiliary conditions of Proposition E.1 impose more structure than we need
for the main argument.

######  Lemma E.1 (Two sided bound on sub-Gaussian matrices; Theorem 4.6.1 of
[Vershynin, 2018]).

Let $\boldsymbol{U}\in\mathbb{R}^{m\times r}$ whose rows
$U_{i,\cdot}\in\mathbb{R}^{r}$ are independent, mean zero, sub-Gaussian, and
isotropic with $\|U_{i,\cdot}\|_{\psi_{2}}\leq K_{u}$. Then for any $t\geq 0$,
w.p. $1-2e^{-t^{2}}$

$\sqrt{m}-CK_{u}^{2}(\sqrt{r}+t)\leq s_{r}(\boldsymbol{U})\leq
s_{1}(\boldsymbol{U})\leq\sqrt{m}+CK_{u}^{2}(\sqrt{r}+t).$

######  Proposition E.1 (Verifying row space inclusion).

By hypothesis, $rank\\{\boldsymbol{A}^{\textsc{(lr)}}\\}=r$, so it admits a
representation $A^{\textsc{(lr)}}_{ij}=\langle u_{i},v_{j},\rangle$ where
$u_{i},v_{j}\in\mathbb{R}^{r}$. Suppose $\\{u_{i}\\}$ are independent, mean
zero, sub-Gaussian, and isotropic (i.e. $\mathbb{V}(u_{i})=I_{r}$) with
$\|u_{i}\|_{\psi_{2}}\leq K_{u}$. Suppose $m\gg K_{u}^{4}\cdot r\ln(mp)$. Then
with probability $1-O\\{(mp)^{-10}\\}$,
$\textsc{row}\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\}=\textsc{row}\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\\}$.

###### Proof.

Consider $\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}$. Let $\boldsymbol{U}$
have rows $\\{U_{i,\cdot}\\}$. By Lemma E.1 with $t=\ln^{\frac{1}{2}}(mp)$,

$s_{r}(\boldsymbol{U})\geq\sqrt{m}-CK_{u}^{2}\\{\sqrt{r}+\ln^{\frac{1}{2}}(mp)\\}\gg
0.$

With high probability, $s_{r}(\boldsymbol{U})\gg 0$, implying that
$\\{U_{i,\cdot}\\}$ are full rank so that
$\textsc{row}(\boldsymbol{U})=\mathbb{R}^{r}$.

Now consider $\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}$. Let
$\boldsymbol{U}^{\prime}$ have rows $\\{U^{\prime}_{i,\cdot}\\}$. Fix
$i\in\textsc{test}$. Since
$U^{\prime}_{i,\cdot}\in\mathbb{R}^{r}=\textsc{row}(\boldsymbol{U})$, there
exists some $\lambda\in\mathbb{R}^{r}$ such that
$U^{\prime}_{i,\cdot}=\sum_{k=1}^{r}\lambda_{k}U_{k,\cdot}$. Therefore

$A^{\textsc{(lr)},\textsc{test}}_{ij}=\langle
U^{\prime}_{i,\cdot},V_{\cdot,j}\rangle=\left\langle\sum_{k=1}^{r}\lambda_{k}U_{k,\cdot},V_{\cdot,j}\right\rangle=\sum_{k=1}^{r}\lambda_{k}\langle
U_{k,\cdot},V_{\cdot,j}\rangle=\sum_{k=1}^{r}\lambda_{k}A^{\textsc{(lr)},\textsc{train}}_{kj}.$

In summary, for any $i\in\textsc{test}$,
$A^{\textsc{(lr)},\textsc{test}}_{i,\cdot}\in\textsc{row}\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\}$.
Therefore
$\textsc{row}\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\\}\subset\textsc{row}\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\}$.
Likewise for the other direction. ∎

Next, we turn to the orthogonality properties of interest. In order to
formalize these orthogonality properties, we formally define $\beta^{*}$. To
begin, consider the case without a dictionary. We define
$\beta^{*}\in\mathbb{R}^{p}$ as the unique solution to the following
optimization problem across train and test:

$\min_{\beta\in\mathbb{R}^{p}}\|\beta\|_{2}\text{ s.t.
}\beta\in\operatorname*{\arg\\!\min}\left\|\begin{bmatrix}\gamma_{0}(\boldsymbol{A}^{\textsc{train}})\\\
\gamma_{0}(\boldsymbol{A}^{\textsc{test}})\end{bmatrix}-\begin{bmatrix}\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\\
\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\end{bmatrix}\beta\right\|_{2}^{2}.$

$\beta^{*}$ is not the quantity of interest, but rather a theoretical device.
It defines the unique, minimal-norm, low-rank, linear approximation to the
regression $\gamma_{0}$. The theoretical device $\beta^{*}$ generalizes the
target quantity of [Agarwal et al., 2020a], who study error-in-variables
regression in the exactly linear, exactly low rank, no dictionary special case
(i.e. $\phi^{\textsc{(lr)}}_{i}=0$). Our ultimate goal is to define and
analyze an estimator close to $\gamma_{0}(A_{i,\cdot})$ in generalized mean
square error while adhering to the conditional independence criterion of
Proposition 4.2.

######  Remark E.2 (Dictionary).

When using a dictionary, we update our definition of
$\beta^{*}\in\mathbb{R}^{p^{\prime}}$ as the unique solution to the following
optimization problem across train and test:

$\min_{\beta\in\mathbb{R}^{p^{\prime}}}\|\beta\|_{2}\text{ s.t.
}\beta\in\operatorname*{\arg\\!\min}\left\|\begin{bmatrix}\gamma_{0}(\boldsymbol{A}^{\textsc{train}})\\\
\gamma_{0}(\boldsymbol{A}^{\textsc{test}})\end{bmatrix}-\begin{bmatrix}b\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\}\\\
b\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\\}\end{bmatrix}\beta\right\|_{2}^{2}.$

######  Lemma E.2 (Orthogonality).

Suppose Assumption 5.6 holds. Then,

$\hat{\boldsymbol{V}}_{k,\perp}^{T}\hat{\beta}=0,\quad\boldsymbol{V}_{\perp}^{T}\beta^{*}=(\boldsymbol{V}_{\perp}^{\prime})^{T}\beta^{*}=0.$

###### Proof.

We show each result

  1. 1.

$\hat{\boldsymbol{V}}_{k,\perp}^{T}\hat{\beta}=0$. By [Agarwal et al., 2020a,
Property 4.1],
$\hat{\beta}\in\textsc{row}(\hat{\boldsymbol{A}}^{\textsc{train}})=\textsc{row}(\hat{\boldsymbol{V}}_{k}^{T})=\textsc{col}(\hat{\boldsymbol{V}}_{k}).$
Recall that $\hat{\boldsymbol{V}}_{k,\perp}$ is the basis of
$\textsc{null}(\hat{\boldsymbol{V}}_{k})$. Therefore by orthogonality of
$\textsc{col}(\hat{\boldsymbol{V}}_{k})$ and
$\textsc{null}(\hat{\boldsymbol{V}}_{k})$, the result holds.

  2. 2.

$\boldsymbol{V}_{\perp}^{T}\beta^{*}=(\boldsymbol{V}_{\perp}^{\prime})^{T}\beta^{*}=0$.

Using the definition of $\beta^{*}$ as the minimal $\ell_{2}$-norm solution,
and an identical argument to the one above, we have
$\beta^{*}\in\textsc{col}(\tilde{\boldsymbol{V}})$.

Moreover by Assumption 5.6,

$\textsc{row}\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\}=\textsc{row}\\{\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\\}=\textsc{row}\left\\{\begin{bmatrix}\boldsymbol{A}^{\textsc{(lr)},\textsc{train}}\\\
\boldsymbol{A}^{\textsc{(lr)},\textsc{test}}\end{bmatrix}\right\\}.$

Therefore
$\textsc{row}(\boldsymbol{V}^{T})=\textsc{row}\\{(\boldsymbol{V}^{\prime})^{T}\\}=\textsc{row}(\tilde{\boldsymbol{V}}^{T})$
i.e.
$\textsc{col}(\boldsymbol{V})=\textsc{col}(\boldsymbol{V}^{\prime})=\textsc{col}(\tilde{\boldsymbol{V}})$.
In summary,
$\beta^{*}\in\textsc{col}(\boldsymbol{V})=\textsc{col}(\boldsymbol{V}^{\prime})$.

Recall that $\boldsymbol{V}_{\perp}$ is the basis of
$\textsc{null}(\boldsymbol{V})$ and likewise $\boldsymbol{V}^{\prime}_{\perp}$
is the basis of $\textsc{null}(\boldsymbol{V}^{\prime})$. Therefore by
orthogonality of $\textsc{col}(\boldsymbol{V})$ and
$\textsc{null}(\boldsymbol{V})$ as well as orthogonality of
$\textsc{col}(\boldsymbol{V}^{\prime})$ and
$\textsc{null}(\boldsymbol{V}^{\prime})$, the result holds.

∎

######  Remark E.3 (Dictionary).

Lemma E.2 continues to hold with the updated definitions of the SVDs in Remark
E.1.

####  E.3 Training error

Recall
$Y_{i}=A^{\textsc{(lr)}}_{i,\cdot}\beta^{*}+\phi_{i}^{\textsc{(lr)}}+\varepsilon_{i}$.
Denote by $Y^{\textsc{train}}\in\mathbb{R}^{n}$ the concatenation of
$(Y_{i})_{i\in\textsc{train}}$. Likewise for $\varepsilon^{\textsc{train}}$
and $\phi^{\textsc{(lr)},\textsc{train}}$. In the argument for train error,
all objects correspond to train. For this reason, we suppress superscipt
train.

#####  E.3.1 Decomposition

######  Lemma E.3.

Deterministically,

$\|\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}\|^{2}_{2}\leq
C\left\\{\|\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}}\|^{2}_{2,\infty}\|\beta^{*}\|^{2}_{1}\
\vee\ \|\phi^{\textsc{(lr)}}\|^{2}_{2}\ \vee\
\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle\right\\}.$

###### Proof.

Write

$\displaystyle\|\hat{\boldsymbol{A}}\hat{\beta}-Y\|_{2}^{2}$
$\displaystyle=\|\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}-\phi^{\textsc{(lr)}}-\varepsilon\|_{2}^{2}$
$\displaystyle=\|\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}-\phi^{\textsc{(lr)}}\|_{2}^{2}+\|\varepsilon\|_{2}^{2}-2\langle\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*},\varepsilon\rangle+2\langle\phi^{\textsc{(lr)}},\varepsilon\rangle.$
(14)

By optimality of $\hat{\beta}$, we have

$\displaystyle\|\hat{\boldsymbol{A}}\hat{\beta}-Y\|_{2}^{2}$
$\displaystyle\leq\|\hat{\boldsymbol{A}}\beta^{*}-Y\|_{2}^{2}$
$\displaystyle=\|(\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}})\beta^{*}-\phi^{\textsc{(lr)}}-\varepsilon\|_{2}^{2}$
$\displaystyle=\|(\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}})\beta^{*}-\phi^{\textsc{(lr)}}\|_{2}^{2}+\|\varepsilon\|_{2}^{2}-2\langle(\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}})\beta^{*},\varepsilon\rangle+2\langle\phi^{\textsc{(lr)}},\varepsilon\rangle.$
(15)

From (E.3.1) and (15), we have

$\displaystyle\|\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}-\phi^{\textsc{(lr)}}\|_{2}^{2}$
$\displaystyle\leq\|(\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}})\beta^{*}-\phi^{\textsc{(lr)}}\|_{2}^{2}+2\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle.$
(16)

Now consider

$\displaystyle\|\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}-\phi^{\textsc{(lr)}}\|_{2}^{2}$
$\displaystyle=\|\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}\|_{2}^{2}+\|\phi^{\textsc{(lr)}}\|_{2}^{2}-2\langle\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*},\phi^{\textsc{(lr)}}\rangle;$
(17)
$\displaystyle\|(\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}})\beta^{*}-\phi^{\textsc{(lr)}}\|_{2}^{2}$
$\displaystyle=\|(\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}})\beta^{*}\|_{2}^{2}+\|\phi^{\textsc{(lr)}}\|_{2}^{2}-2\langle(\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}})\beta^{*},\phi^{\textsc{(lr)}}\rangle.$
(18)

Combining (16), (17), and (18)

$\displaystyle\|\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}\|_{2}^{2}\leq\|(\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}})\beta^{*}\|_{2}^{2}+2\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\phi^{\textsc{(lr)}}\rangle+2\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle.$
(19)

By Cauchy-Schwarz

$\displaystyle\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\phi^{\textsc{(lr)}}\rangle\leq\|\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*})\|_{2}\cdot\|\phi^{\textsc{(lr)}}\|_{2}.$
(20)

Focusing on the former factor

$\displaystyle\|\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*})\|_{2}\leq\|\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}\|_{2}+\|\hat{\boldsymbol{A}}\beta^{*}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}\|_{2}.$
(21)

Let
$a=\|\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}\|^{2}_{2}$
and
$b=\|\hat{\boldsymbol{A}}\beta^{*}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}\|^{2}_{2}$.
Then (19), (20), and (21) imply

$\displaystyle a\leq
b+2(\sqrt{a}+\sqrt{b})\|\phi^{\textsc{(lr)}}\|_{2}+2\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle=2\sqrt{a}\|\phi^{\textsc{(lr)}}\|_{2}+c$
(22)

where
$c=b+2\sqrt{b}\|\phi^{\textsc{(lr)}}\|_{2}+2\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle$.
We now analyze the expression $a\leq 2\sqrt{a}\|\phi^{\textsc{(lr)}}\|_{2}+c$.
Note $a\geq 0$. There are three possible cases.

  1. 1.

$a\geq 0$, $c\geq 0$, $2\sqrt{a}\|\phi^{\textsc{(lr)}}\|_{2}\geq c$:

$a\leq 4\sqrt{a}\|\phi^{\textsc{(lr)}}\|_{2}\implies a\leq
16\|\phi^{\textsc{(lr)}}\|_{2}^{2}.$

  2. 2.

$a\geq 0$, $c\geq 0$, $2\sqrt{a}\|\phi^{\textsc{(lr)}}\|_{2}<c$:

$a\leq 2c.$

  3. 3.

$a\geq 0$, $c<0$:

$a<2\sqrt{a}\|\phi^{\textsc{(lr)}}\|_{2}\implies
a<4\|\phi^{\textsc{(lr)}}\|_{2}^{2}.$

(22) and the three cases above imply

$\displaystyle a\leq 2c\vee 16\|\phi^{\textsc{(lr)}}\|_{2}^{2}.$ (23)

Let $d\coloneqq
2b+4\sqrt{b}\|\phi^{\textsc{(lr)}}\|_{2}+2\|\phi^{\textsc{(lr)}}\|_{2}^{2}$.
Then

$\displaystyle
d=2b+4\sqrt{b}\|\phi^{\textsc{(lr)}}\|_{2}+2\|\phi^{\textsc{(lr)}}\|^{2}_{2}=2\\{\sqrt{b}+\|\phi^{\textsc{(lr)}}\|_{2}\\}^{2}\leq
4\\{b+\|\phi^{\textsc{(lr)}}\|^{2}_{2}\\}.$ (24)

Note $2c\leq
d+4\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle$.
This together with (23) and (24) together implies

$a\leq C\left\\{b\ \vee\ \|\phi^{\textsc{(lr)}}\|^{2}_{2}\ \vee\
\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle\right\\}.$

Finally note
$b\leq\|\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}}\|^{2}_{2,\infty}\|\beta^{*}\|^{2}_{1}$.
∎

######  Remark E.4 (Dictionary).

The generalization of Lemma E.3 is

$\|b(\hat{\boldsymbol{A}})\hat{\beta}-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\beta^{*}\|^{2}_{2}\leq
C\left\\{\|b(\hat{\boldsymbol{A}})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\|\beta^{*}\|^{2}_{1}\
\vee\ \|\phi^{\textsc{(lr)}}\|^{2}_{2}\ \vee\ \langle
b(\hat{\boldsymbol{A}})(\hat{\beta}-\beta^{*}),\varepsilon\rangle\right\\}.$

#####  E.3.2 Parameter

######  Lemma E.4.

Let the conditions of Lemma E.2 hold. Then

$\displaystyle\|\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}(\hat{\beta}-\beta^{*})\|_{2}^{2}\leq\frac{C}{\hat{s}_{k}^{2}}\Big{\\{}\|\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}}\|^{2}_{2,\infty}\|\beta^{*}\|^{2}_{1}\
\vee\ \|\phi^{\textsc{(lr)}}\|^{2}_{2}\ \vee\
\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle\Big{\\}}$

###### Proof.

To begin, note that

$\displaystyle\|\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}(\hat{\beta}-\beta^{*})\|_{2}^{2}$
$\displaystyle=\|\hat{\boldsymbol{V}}_{k}^{T}(\hat{\beta}-\beta^{*})\|_{2}^{2},$
(25)

since $\hat{\boldsymbol{V}}_{k}$ is an isometry. Recall that
$\hat{\boldsymbol{A}}=\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{\Sigma}}_{k}\hat{\boldsymbol{V}}_{k}^{T}$.
Therefore,

$\displaystyle\|\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*})\|_{2}^{2}$
$\displaystyle=(\hat{\beta}-\beta^{*})^{T}\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{\Sigma}}_{k}^{2}\hat{\boldsymbol{V}}_{k}^{T}(\hat{\beta}-\beta^{*})$
$\displaystyle\geq\hat{s}_{k}^{2}\|\hat{\boldsymbol{V}}_{k}^{T}(\hat{\beta}-\beta^{*})\|_{2}^{2}.$
(26)

Next, consider

$\displaystyle\|\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*})\|_{2}^{2}$
$\displaystyle\leq
2\|\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}\|_{2}^{2}+2\|\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}-\hat{\boldsymbol{A}}\beta^{*}\|_{2}^{2}$
$\displaystyle\leq
2\|\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}\|_{2}^{2}+2\|\boldsymbol{A}^{\textsc{(lr)}}-\hat{\boldsymbol{A}}\|_{2,\infty}^{2}\|\beta^{*}\|_{1}^{2}.$
(27)

Using (25), (26), and (27), we have

$\|\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}(\hat{\beta}-\beta^{*})\|_{2}^{2}\leq\frac{2}{\hat{s}_{k}^{2}}\Big{\\{}\|\hat{\boldsymbol{A}}\hat{\beta}-\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}\|_{2}^{2}+\|\boldsymbol{A}^{\textsc{(lr)}}-\hat{\boldsymbol{A}}\|_{2,\infty}^{2}\|\beta^{*}\|_{1}^{2}\Big{\\}}.$

Finally using Lemma E.3, we conclude that

$\displaystyle\|\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}(\hat{\beta}-\beta^{*})\|_{2}^{2}$
$\displaystyle\leq\frac{C}{\hat{s}_{k}^{2}}\Big{\\{}\|\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}}\|^{2}_{2,\infty}\|\beta^{*}\|^{2}_{1}\
\vee\ \|\phi^{\textsc{(lr)}}\|^{2}_{2}\ \vee\
\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle\Big{\\}}.$
(28)

∎

######  Remark E.5 (Dictionary).

The generalization of Lemma E.4 is

$\displaystyle\|\hat{\boldsymbol{V}}_{r^{\prime}}\hat{\boldsymbol{V}}_{r^{\prime}}^{T}(\hat{\beta}-\beta^{*})\|_{2}^{2}\leq\frac{C}{\hat{s}_{r^{\prime}}^{2}}\Big{\\{}\|b(\hat{\boldsymbol{A}})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\|\beta^{*}\|^{2}_{1}\
\vee\ \|\phi^{\textsc{(lr)}}\|^{2}_{2}\ \vee\ \langle
b(\hat{\boldsymbol{A}})(\hat{\beta}-\beta^{*}),\varepsilon\rangle\Big{\\}}$

where the SVDs are as in Remark E.1 and $\hat{s}_{r^{\prime}}$ is defined
accordingly.

######  Lemma E.5.

Let the conditions of Lemma E.2 hold. Then,

$\displaystyle\|\hat{\beta}-\beta^{*}\|^{2}_{2}$ $\displaystyle\quad\leq
C\left[\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}\|^{2}\|\beta^{*}\|^{2}_{2}+\frac{1}{\hat{s}_{k}^{2}}\Big{\\{}\|\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}}\|^{2}_{2,\infty}\|\beta^{*}\|^{2}_{1}\
\vee\ \|\phi^{\textsc{(lr)}}\|^{2}_{2}\ \vee\
\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle\Big{\\}}\right].$

###### Proof.

Write

$\displaystyle\|\hat{\beta}-\beta^{*}\|_{2}^{2}$
$\displaystyle=\|\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}(\hat{\beta}-\beta^{*})+\hat{\boldsymbol{V}}_{k,\perp}\hat{\boldsymbol{V}}_{k,\perp}^{T}(\hat{\beta}-\beta^{*})\|_{2}^{2}$
$\displaystyle=\|\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}(\hat{\beta}-\beta^{*})\|_{2}^{2}+\|\hat{\boldsymbol{V}}_{k,\perp}\hat{\boldsymbol{V}}_{k,\perp}^{T}(\hat{\beta}-\beta^{*})\|_{2}^{2}$
$\displaystyle=\|\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}(\hat{\beta}-\beta^{*})\|_{2}^{2}+\|\hat{\boldsymbol{V}}_{k,\perp}\hat{\boldsymbol{V}}_{k,\perp}^{T}\beta^{*}\|_{2}^{2}.$
(29)

In the last equality we have used Lemma E.2. Next, we bound the two terms in
(29).

  1. 1.

Bounding
$\|\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}(\hat{\beta}-\beta^{*})\|_{2}^{2}$.

The bound follows from Lemma E.4.

  2. 2.

Bounding
$\|\hat{\boldsymbol{V}}_{k,\perp}\hat{\boldsymbol{V}}_{k,\perp}^{T}\beta^{*}\|_{2}^{2}$.

Write

$\displaystyle\|\hat{\boldsymbol{V}}_{k,\perp}\hat{\boldsymbol{V}}_{k,\perp}^{T}\beta^{*}\|_{2}^{2}$
$\displaystyle=\|(\hat{\boldsymbol{V}}_{k,\perp}\hat{\boldsymbol{V}}_{k,\perp}^{T}\beta^{*}-\boldsymbol{V}_{\perp}\boldsymbol{V}_{\perp}^{T})\beta^{*}\|_{2}^{2}$
$\displaystyle\leq\|\hat{\boldsymbol{V}}_{k,\perp}\hat{\boldsymbol{V}}_{k,\perp}^{T}-\boldsymbol{V}_{\perp}\boldsymbol{V}_{\perp}^{T}\|^{2}\|\beta^{*}\|_{2}^{2}$
$\displaystyle=\|(\boldsymbol{I}-\boldsymbol{V}_{\perp}\boldsymbol{V}_{\perp}^{T})-(\boldsymbol{I}-\hat{\boldsymbol{V}}_{k,\perp}\hat{\boldsymbol{V}}_{k,\perp}^{T})\|^{2}\|\beta^{*}\|_{2}^{2}$
$\displaystyle=\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}\|^{2}\|\beta^{*}\|_{2}^{2}.$

Here we have used
$(\boldsymbol{V}_{\perp}\boldsymbol{V}_{\perp}^{T})\beta^{*}=0$ by Lemma E.2.

∎

######  Remark E.6 (Dictionary).

The generalization of Lemma E.5 is

$\displaystyle\|\hat{\beta}-\beta^{*}\|^{2}_{2}$ $\displaystyle\quad\leq
C\left[\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{r^{\prime}}\hat{\boldsymbol{V}}_{r^{\prime}}^{T}\|^{2}\|\beta^{*}\|^{2}_{2}+\frac{1}{\hat{s}_{r^{\prime}}^{2}}\Big{\\{}\|b(\hat{\boldsymbol{A}})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\|\beta^{*}\|^{2}_{1}\
\vee\ \|\phi^{\textsc{(lr)}}\|^{2}_{2}\ \vee\ \langle
b(\hat{\boldsymbol{A}})(\hat{\beta}-\beta^{*}),\varepsilon\rangle\Big{\\}}\right]$

where the SVDs are as in Remark E.1 and $\hat{s}_{r^{\prime}}$ is defined
accordingly.

#####  E.3.3 High probability events

######  Lemma E.6 (Weyl’s Inequality).

Assume $\boldsymbol{A},\boldsymbol{B}\in\mathbb{R}^{n\times p}$. Let $s_{k}$
and $\hat{s}_{k}$ be the $k$-th singular values of $\boldsymbol{A}$ and
$\boldsymbol{B}$, respectively, in decreasing order and repeated by
multiplicities. Then for all $k\in[n\wedge p]$,

$|s_{k}-\hat{s}_{k}|\leq\|\boldsymbol{A}-\boldsymbol{B}\|.$

######  Lemma E.7.

Suppose the conditions of Lemma D.12 hold. Then,

$|s_{r}-\hat{s}_{r}|~{}\Big{|}~{}\\{\mathcal{E}_{1},\mathcal{E}_{4},\mathcal{E}_{5}\\}\leq
C\frac{\delta}{\rho_{\min}}\left\\{(\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\sqrt{\frac{\ln(np)}{n}}\|\boldsymbol{A}^{\textsc{(lr)}}\|\right\\}.$

###### Proof.

By Weyl’s inequality as in Lemma E.6, we obtain

$|s_{r}-\hat{s}_{r}|\leq\|\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\boldsymbol{A}^{\textsc{(lr)}}\|.$

Apply Lemma D.12 to complete the proof. ∎

######  Remark E.7 (Dictionary).

The generalization of Lemma E.7 is

$|s_{r^{\prime}}-\hat{s}_{r^{\prime}}|~{}\Big{|}~{}\\{\mathcal{E}_{1},\mathcal{E}_{4},\mathcal{E}_{5}\\}\leq
C\frac{\delta}{\rho^{\prime}_{\min}}\left((\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\sqrt{\frac{\ln(np)}{n}}\|\boldsymbol{A}^{\textsc{(lr)}}\|\right).$

where $\rho^{\prime}_{\min}=\frac{\rho_{\min}}{\bar{A}^{d_{\max}}d_{\max}}$.

###### Proof.

We proceed in steps.

  1. 1.

Decomposition

With updated SVDs as in Remark E.1, Weyl’s inequality implies

$|s_{r^{\prime}}-\hat{s}_{r^{\prime}}|\leq\|b(\hat{\boldsymbol{A}})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|\leq\|b(\hat{\boldsymbol{A}})-b(\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1})\|+\|b(\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|.$

  2. 2.

Former term

For a polynomial dictionary with uncorrupted nonlinearity (Definition C.2),
the former term simplifies as

$\displaystyle\|b(\hat{\boldsymbol{A}})-b(\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1})\|$
$\displaystyle=\|\\{0,0,...,0,(\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\hat{\boldsymbol{A}}),diag(D)(\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\hat{\boldsymbol{A}}),...,diag(D)^{d_{\max}-1}(\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\hat{\boldsymbol{A}})\\}\|$
$\displaystyle\leq\|\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\hat{\boldsymbol{A}}\|+\bar{A}\|\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\hat{\boldsymbol{A}}\|+...+\bar{A}^{d_{\max}-1}\|\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\hat{\boldsymbol{A}}\|$
$\displaystyle\leq\bar{A}^{d_{\max}}d_{\max}\|\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\hat{\boldsymbol{A}}\|.$

Next observe that by Lemma E.7, under the beneficial events,

$\|\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\hat{\boldsymbol{A}}\|=\hat{s}_{r+1}=\hat{s}_{r+1}-s_{r+1}\leq
C\frac{\delta}{\rho_{\min}}\left\\{(\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\sqrt{\frac{\ln(np)}{n}}\|\boldsymbol{A}^{\textsc{(lr)}}\|\right\\}.$

  3. 3.

Latter term

By a similar argument,

$\|b(\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|\leq\bar{A}^{d_{\max}}d_{\max}\|\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\boldsymbol{A}^{\textsc{(lr)}}\|.$

By Lemma D.12, under the beneficial events,

$\|\boldsymbol{Z}\hat{\boldsymbol{\rho}}^{-1}-\boldsymbol{A}^{\textsc{(lr)}}\|\leq
C\frac{\delta}{\rho_{\min}}\left((\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\sqrt{\frac{\ln(np)}{n}}\|\boldsymbol{A}^{\textsc{(lr)}}\|\right).$

∎

######  Lemma E.8.

Suppose $k=r.$ Then

$\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}\|~{}\Big{|}~{}\\{\mathcal{E}_{1},\mathcal{E}_{4},\mathcal{E}_{5}\\}\leq
C\frac{\delta}{\rho_{\min}s_{r}}\left\\{(\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\sqrt{\frac{\ln(np)}{n}}\|\boldsymbol{A}^{\textsc{(lr)}}\|\right\\}.$

###### Proof.

Similar to Lemma D.13, we apply Wedin’s $\sin\Theta$ Theorem [Davis and Kahan,
1970, Wedin, 1972]) to arrive at the following inequality:

$\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}\|\leq\frac{\|\boldsymbol{Z}\operatorname{\hat{\boldsymbol{\rho}}}^{-1}-\boldsymbol{A}^{\textsc{(lr)}}\|}{s_{r}}.$

Apply Lemma D.12 to complete the proof. ∎

######  Remark E.8 (Dictionary).

The generalization is

$\displaystyle\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{r^{\prime}}\hat{\boldsymbol{V}}_{r^{\prime}}^{T}\|~{}\Big{|}~{}\\{\mathcal{E}_{1},\mathcal{E}_{4},\mathcal{E}_{5}\\}$
$\displaystyle
C\frac{\delta}{\rho^{\prime}_{\min}s_{r^{\prime}}}\left((\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\sqrt{\frac{\ln(np)}{n}}\|\boldsymbol{A}^{\textsc{(lr)}}\|\right).$

###### Proof.

Wedin’s $\sin\Theta$ Theorem gives

$\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{r^{\prime}}\hat{\boldsymbol{V}}_{r^{\prime}}^{T}\|\leq\frac{\|b(\hat{\boldsymbol{A}})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|}{s_{r^{\prime}}}.$

The numerator is handled in the proof of Remark E.7. ∎

######  Lemma E.9.

Suppose Assumptions 5.1, 5.2, 5.3, and 5.4 hold, and $k=r$. If

$\rho_{\min}\gg\tilde{C}\sqrt{r}\ln^{\frac{3}{2}}(np)\left(\frac{1}{\sqrt{p}}\vee\frac{1}{\sqrt{n}}\vee\Delta_{E}\right),\quad\tilde{C}:=C\bar{A}\Big{(}\kappa+\bar{K}+K_{a}\Big{)},$

then with probability at least $1-O\\{1/(np)^{10}\\}$, $\hat{s}_{r}\gtrsim
s_{r}.$

###### Proof.

The argument is as follows.

  1. 1.

By Lemma E.7, $|\hat{s}_{r}-s_{r}|\leq\Delta$, hence $\hat{s}_{r}\geq
s_{r}-\Delta$, where $\Delta$ is defined below.

  2. 2.

We want to show $\Delta=o(s_{r})$, i.e. $\Delta\leq c_{n}s_{r}$ where
$c_{n}\rightarrow 0$; it is sufficient to show
$\frac{\Delta}{s_{r}}\rightarrow 0$.

  3. 3.

In such case, $\hat{s}_{r}\geq s_{r}-\Delta\geq
s_{r}-c_{n}s_{r}=(1-c_{n})s_{r}$, i.e. $\hat{s}_{r}\gtrsim s_{r}$.

By Lemma D.10 and Lemma E.7, with probability at least $1-O\\{1/(np)^{10}\\}$

$\displaystyle\Delta$
$\displaystyle:=C\frac{\delta}{\rho_{\min}}\left\\{(\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\sqrt{\frac{\ln(np)}{n}}\|\boldsymbol{A}^{\textsc{(lr)}}\|\right\\}$
$\displaystyle\leq
C\frac{1}{\rho_{\min}}\left\\{\bar{A}\Big{(}\kappa+\bar{K}+K_{a}\Big{)}\Big{(}\sqrt{n}+\sqrt{p}\Big{)}\ln^{\frac{3}{2}}(np)+\sqrt{np}\Delta_{E}+\sqrt{\frac{\ln(np)}{n}}\sqrt{np}\bar{A}\right\\}$
$\displaystyle\leq
C\frac{\bar{A}\Big{(}\kappa+\bar{K}+K_{a}\Big{)}}{\rho_{\min}}\ln^{\frac{3}{2}}(np)\left(\sqrt{n}+\sqrt{p}+\sqrt{np}\Delta_{E}\right).$

Moreover by Assumption 5.4

$s_{r}\geq C\sqrt{\frac{np}{r}}.$

Therefore a sufficient condition for the lemma statement to hold is

$\frac{\Delta}{s_{r}}\leq
C\frac{\bar{A}\Big{(}\kappa+\bar{K}+K_{a}\Big{)}}{\rho_{\min}}\cdot\sqrt{r}\ln^{\frac{3}{2}}(np)\cdot\left(\frac{1}{\sqrt{p}}+\frac{1}{\sqrt{n}}+\Delta_{E}\right)\rightarrow
0$

i.e.

$\rho_{\min}\gg\tilde{C}\sqrt{r}\ln^{\frac{3}{2}}(np)\left(\frac{1}{\sqrt{p}}\vee\frac{1}{\sqrt{n}}\vee\Delta_{E}\right),\quad\tilde{C}:=C\bar{A}\Big{(}\kappa+\bar{K}+K_{a}\Big{)}.$

∎

######  Remark E.9 (Dictionary).

The generalization of Lemma E.9 is

$\rho^{\prime}_{\min}:=\frac{\rho_{\min}}{\bar{A}^{d_{\max}}d_{\max}}\gg\tilde{C}\sqrt{r^{\prime}}\ln^{\frac{3}{2}}(np)\left(\frac{1}{\sqrt{p}}\vee\frac{1}{\sqrt{n}}\vee\Delta_{E}\right).$

###### Proof.

By Remark E.7,

$\displaystyle\Delta$
$\displaystyle:=C\frac{\delta}{\rho^{\prime}_{\min}}\left((\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\sqrt{\frac{\ln(np)}{n}}\|\boldsymbol{A}^{\textsc{(lr)}}\|\right).$

Moreover by the generalized Assumption 5.4

$s_{r^{\prime}}\geq C\sqrt{\frac{np}{r^{\prime}}}.$

∎

######  Lemma E.10.

Suppose Assumption 5.5 holds. Recall $k$ is the PCA hyperparameter. Then

$\mathbb{E}\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle\leq\bar{\sigma}^{2}k.$

###### Proof.

Note that

$\hat{\beta}=\hat{\boldsymbol{A}}^{\dagger}Y=\hat{\boldsymbol{A}}^{\dagger}\\{\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}+\varepsilon+\phi^{\textsc{(lr)}}\\}.$

Since $\varepsilon$ is independent of $\hat{\boldsymbol{A}}$,
$\boldsymbol{A}^{\textsc{(lr)}}$, $\beta^{*}$, and $\phi^{\textsc{(lr)}}$ we
have

$\displaystyle\mathbb{E}\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle$
$\displaystyle=\mathbb{E}\left\langle\hat{\boldsymbol{A}}\left[\hat{\boldsymbol{A}}^{\dagger}\\{\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}+\varepsilon+\phi^{\textsc{(lr)}}\\}-\beta^{*}\right],\varepsilon\right\rangle$
$\displaystyle=\mathbb{E}\langle\hat{\boldsymbol{A}}\hat{\boldsymbol{A}}^{\dagger}\boldsymbol{A}^{\textsc{(lr)}}\beta^{*},\varepsilon\rangle+\mathbb{E}\langle\hat{\boldsymbol{A}}\hat{\boldsymbol{A}}^{\dagger}\varepsilon,\varepsilon\rangle+\mathbb{E}\langle\hat{\boldsymbol{A}}\hat{\boldsymbol{A}}^{\dagger}\phi^{\textsc{(lr)}},\varepsilon\rangle-\mathbb{E}\langle\hat{\boldsymbol{A}}\beta^{*},\varepsilon\rangle$
$\displaystyle=\mathbb{E}\langle\hat{\boldsymbol{A}}\hat{\boldsymbol{A}}^{\dagger}\varepsilon,\varepsilon\rangle.$

Observe that
$\mathbb{E}\langle\hat{\boldsymbol{A}}\hat{\boldsymbol{A}}^{\dagger}\varepsilon,\varepsilon\rangle$
is a scalar. By properties of trace algebra, independence of $\varepsilon$
from $\hat{\boldsymbol{A}}$, Assumption 5.5, and the fact that
$\hat{\boldsymbol{A}}$ is rank $k$ we obtain

$\displaystyle\mathbb{E}\langle\hat{\boldsymbol{A}}\hat{\boldsymbol{A}}^{\dagger}\varepsilon,\varepsilon\rangle$
$\displaystyle=\mathbb{E}\left[trace\left(\varepsilon^{T}\hat{\boldsymbol{A}}\hat{\boldsymbol{A}}^{\dagger}\varepsilon\right)\right]$
$\displaystyle=\mathbb{E}\left[trace\left(\hat{\boldsymbol{A}}\hat{\boldsymbol{A}}^{\dagger}\varepsilon\varepsilon^{T}\right)\right]$
$\displaystyle=trace\left(\mathbb{E}\left[\hat{\boldsymbol{A}}\hat{\boldsymbol{A}}^{\dagger}\right]\mathbb{E}\left[\varepsilon\varepsilon^{T}\right]\right)$
$\displaystyle\leq\bar{\sigma}^{2}trace\left(\mathbb{E}\left[\hat{\boldsymbol{A}}\hat{\boldsymbol{A}}^{\dagger}\right]\right)$
$\displaystyle=\bar{\sigma}^{2}k.$

∎

######  Remark E.10 (Dictionary).

The generalization of Lemma E.10 is

$\mathbb{E}\langle
b(\hat{\boldsymbol{A}})(\hat{\beta}-\beta^{*}),\varepsilon\rangle\leq\bar{\sigma}^{2}r^{\prime}.$

######  Lemma E.11 (Modified Hoeffding Inequality; Lemma A.3 of [Agarwal et
al., 2020a]).

Let $X\in\mathbb{R}^{n}$ be random vector with independent mean-zero sub-
Gaussian random coordinates with $\left\|X_{i}\right\|_{\psi_{2}}\leq K$. Let
$a\in\mathbb{R}^{n}$ be another random vector that satisfies
$\left\|a\right\|_{2}\leq b$ almost surely for some constant $b\geq 0$. Then
for all $t\geq 0$,

$\displaystyle\mathbb{P}\Big{(}\Big{|}\sum_{i=1}^{n}a_{i}X_{i}\Big{|}\geq
t\Big{)}\leq 2\exp\Big{(}-\frac{ct^{2}}{K^{2}b^{2}}\Big{)},$

where $c>0$ is a universal constant.

######  Lemma E.12 (Modified Hanson-Wright Inequality; Lemma A.4 of [Agarwal
et al., 2020a]).

Let $X\in\mathbb{R}^{n}$ be a random vector with independent mean-zero sub-
Gaussian coordinates with $\left\|X_{i}\right\|_{\psi_{2}}\leq K$. Let
$\boldsymbol{B}\in\mathbb{R}^{n\times n}$ be a random matrix satisfying
$\left\|\boldsymbol{B}\right\|\leq a$ and
$\left\|\boldsymbol{B}\right\|_{Fr}^{2}\,\leq b$ almost surely for some
$a,b\geq 0$. Then for any $t\geq 0$,

$\displaystyle\mathbb{P}\left(|X^{T}\boldsymbol{B}X-\mathbb{E}[X^{T}\boldsymbol{B}X]|\geq
t\right)$ $\displaystyle\leq
2\cdot\exp\Big{\\{}-c\min\Big{(}\frac{t^{2}}{K^{4}b},\frac{t}{K^{2}a}\Big{)}\Big{\\}}.$

######  Lemma E.13.

Suppose Assumptions 5.1 and 5.5 hold, and that $k=r$. Given
$\hat{\boldsymbol{A}}$, the following holds with probability at least
$1-O\\{1/(np)^{10}\\}$ with respect to randomness in $\varepsilon$:

$\displaystyle\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle$
$\displaystyle\leq
C\bar{\sigma}^{2}\ln(np)\left\\{r+\|\phi^{\textsc{(lr)}}\|_{2}+\|\beta^{*}\|_{1}(\sqrt{n}\bar{A}+\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|_{2,\infty})\right\\}.$

###### Proof.

We proceed in steps.

  1. 1.

Decomposition

We need to bound
$\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle$. To
that end, we recall that
$\hat{\beta}=\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{\Sigma}}_{k}^{-1}\hat{\boldsymbol{U}}_{k}^{T}Y$,
$\hat{\boldsymbol{A}}=\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{\Sigma}}_{k}\hat{\boldsymbol{V}}_{k}^{T}$,
and
$Y=\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}+\phi^{\textsc{(lr)}}+\varepsilon$.
Thus,

$\hat{\boldsymbol{A}}\hat{\beta}=\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{\Sigma}}_{k}\hat{\boldsymbol{V}}_{k}^{T}\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{\Sigma}}_{k}^{-1}\hat{\boldsymbol{U}}_{k}^{T}Y=\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}+\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\phi^{\textsc{(lr)}}+\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\varepsilon.$

Therefore,

$\displaystyle\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle$
$\displaystyle=\langle\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\boldsymbol{A}^{\textsc{(lr)}}\beta^{*},\varepsilon\rangle+\langle\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\phi^{\textsc{(lr)}},\varepsilon\rangle+\langle\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\varepsilon,\varepsilon\rangle-\langle\hat{\boldsymbol{A}}\beta^{*},\varepsilon\rangle.$
(30)

  2. 2.

First Hoeffding

To obtain a high probability bound of the first term, we use Lemma E.11. Note
that

$\|\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}\|_{2}\leq\|\boldsymbol{A}^{\textsc{(lr)}}\beta^{*}\|_{2}\leq\|\boldsymbol{A}^{\textsc{(lr)}}\|_{2,\infty}\|\beta^{*}\|_{1}\leq
3\sqrt{n}\bar{A}\|\beta^{*}\|_{1}$

since $\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}$ is a projection
matrix and $\|\boldsymbol{A}^{\textsc{(lr)}}\|_{2,\infty}\leq
3\sqrt{n}\bar{A}$ due to Lemma C.4.

It follows that for any $t>0$

$\displaystyle\mathbb{P}\left(\langle\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\boldsymbol{A}^{\textsc{(lr)}}\beta^{*},\varepsilon\rangle\geq
t\right)$
$\displaystyle\leq\exp\Big{(}-\frac{ct^{2}}{n\bar{A}^{2}\|\beta^{*}\|_{1}^{2}\bar{\sigma}^{2}}\Big{)}.$
(31)

  3. 3.

Second Hoeffding

To obtain a high probability bound of the second term, we use Lemma E.11. Note
that

$\|\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\phi^{\textsc{(lr)}}\|_{2}\leq\|\phi^{\textsc{(lr)}}\|_{2}$

since $\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}$ is a projection
matrix.

It follows that for any $t>0$

$\displaystyle\mathbb{P}\left(\langle\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\phi^{\textsc{(lr)}},\varepsilon\rangle\geq
t\right)$
$\displaystyle\leq\exp\Big{(}-\frac{ct^{2}}{\|\phi^{\textsc{(lr)}}\|_{2}^{2}\bar{\sigma}^{2}}\Big{)}.$
(32)

  4. 4.

Third Hoeffding

To obtain a high probability bound of the fourth term, we use Lemma E.11. Note
that

$\displaystyle\|\hat{\boldsymbol{A}}\beta^{*}\|_{2}$
$\displaystyle\leq\|(\hat{\boldsymbol{A}}-\boldsymbol{A})\beta^{*}\|_{2}+\|\boldsymbol{A}\beta^{*}\|_{2}$
$\displaystyle\leq\big{(}\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|_{2,\infty}+\|\boldsymbol{A}\|_{2,\infty}\big{)}\|\beta^{*}\|_{1}$
$\displaystyle\leq\big{(}\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|_{2,\infty}+\sqrt{n}\bar{A}\big{)}\|\beta^{*}\|_{1}$

since $\|\boldsymbol{A}\|_{2,\infty}\leq\sqrt{n}\bar{A}$ due to Assumption
5.1.

Therefore, for any $t>0$

$\displaystyle\mathbb{P}\left(\langle\hat{\boldsymbol{A}}\beta^{*},\varepsilon\rangle\geq
t\right)\leq\exp\left(-\frac{ct^{2}}{\bar{\sigma}^{2}(n\bar{A}^{2}+\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{2}_{2,\infty})\|\beta^{*}\|_{1}^{2}}\right).$
(33)

  5. 5.

Hanson-Wright

To obtain a high probability bound of the third term, we use Lemma E.12.
$\varepsilon$ is independent of
$\hat{\boldsymbol{U}}_{k},\hat{\boldsymbol{\Sigma}}_{k},\hat{\boldsymbol{V}}_{k}$
since $\hat{\boldsymbol{A}}$ is determined by $\boldsymbol{Z}$, which is
independent of $\varepsilon$. As a result,

$\displaystyle\mathbb{E}\big{[}\langle\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\varepsilon,\varepsilon\rangle\big{]}$
$\displaystyle=\mathbb{E}\big{[}\varepsilon^{T}\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\varepsilon\big{]}$
$\displaystyle=\mathbb{E}\big{[}trace(\varepsilon^{T}\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\varepsilon)\big{]}$
$\displaystyle=\mathbb{E}\big{[}trace(\varepsilon\varepsilon^{T}\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T})\big{]}$
$\displaystyle=trace(\mathbb{E}\big{[}\varepsilon\varepsilon^{T}\big{]}\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T})$
$\displaystyle\leq
trace(\bar{\sigma}^{2}\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T})$
$\displaystyle=\bar{\sigma}^{2}trace(\hat{\boldsymbol{U}}_{k}^{T}\hat{\boldsymbol{U}}_{k})$
$\displaystyle=\bar{\sigma}^{2}k.$ (34)

Since $\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}$ is a projection
matrix,

$\displaystyle\|\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\|$
$\displaystyle\leq
1,\quad\|\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\|^{2}_{Fr}=trace(\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T})=trace(\hat{\boldsymbol{U}}_{k}^{T}\hat{\boldsymbol{U}}_{k})=k.$

Finally, using Lemma E.12 and (34), it follows that for any $t>0$

$\displaystyle\mathbb{P}\left(\langle\hat{\boldsymbol{U}}_{k}\hat{\boldsymbol{U}}_{k}^{T}\varepsilon,\varepsilon\rangle\geq\bar{\sigma}^{2}k+t\right)$
$\displaystyle\leq\exp\Big{\\{}-c\min\Big{(}\frac{t^{2}}{k\bar{\sigma}^{4}},\frac{t}{\bar{\sigma}^{2}}\Big{)}\Big{\\}}.$
(35)

  6. 6.

Simplification.

Set the RHSs of (31), (32), (33), and (35) equal to $1/(np)^{10}$ and solve
for $t$. Combining these results with (1),

$\displaystyle\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle$
$\displaystyle\leq\bar{\sigma}^{2}r+C\bar{\sigma}\sqrt{\ln(np)}\,\big{\\{}{\bar{\sigma}}\sqrt{r}+\bar{\sigma}\sqrt{\ln(np)}+\|\phi^{\textsc{(lr)}}\|_{2}+\|\beta^{*}\|_{1}(\sqrt{n}\bar{A}+\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|_{2,\infty})\big{\\}}$
$\displaystyle\leq
C\bar{\sigma}^{2}\ln(np)\left\\{r+\|\phi^{\textsc{(lr)}}\|_{2}+\|\beta^{*}\|_{1}(\sqrt{n}\bar{A}+\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|_{2,\infty})\right\\}.$

∎

######  Remark E.11 (Dictionary).

The generalization of Lemma E.13 is

$\displaystyle\langle
b(\hat{\boldsymbol{A}})(\hat{\beta}-\beta^{*}),\varepsilon\rangle$
$\displaystyle\leq
C\bar{\sigma}^{2}\ln(np)\left\\{r^{\prime}+\|\phi^{\textsc{(lr)}}\|_{2}+\|\beta^{*}\|_{1}(\sqrt{n}\bar{A}^{\prime}+\|b(\hat{\boldsymbol{A}})-b(\boldsymbol{A})\|_{2,\infty})\right\\}.$

#####  E.3.4 Collecting results

######  Lemma E.14.

Suppose the conditions of Theorem 5.1 hold. Further suppose Assumptions 5.5
and 5.6 hold. With probability at least $1-O\\{(np)^{-10}\\}$,
$\|\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}(\hat{\beta}-\beta^{*})\|^{2}_{2}\leq(2)$
where

$\displaystyle(2)$
$\displaystyle=\frac{C(K_{a}+\bar{K}\bar{A})^{2}}{\rho^{4}_{\min}}\frac{\bar{\sigma}^{2}\ln^{3}(np)}{\hat{s}_{r}^{2}}$
$\displaystyle\quad\cdot\left[\
\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\left\\{\frac{\sqrt{n}}{\|\beta^{*}\|_{1}}+r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}_{2,\infty}\right\\}\right].$

###### Proof.

By Lemma E.4

$\displaystyle\|\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}(\hat{\beta}-\beta^{*})\|_{2}^{2}\leq\frac{C}{\hat{s}_{k}^{2}}\Big{\\{}\|\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}}\|^{2}_{2,\infty}\|\beta^{*}\|^{2}_{1}\
\vee\ \|\phi^{\textsc{(lr)}}\|^{2}_{2}\ \vee\
\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle\Big{\\}}.$

Note that

$\|\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}}\|^{2}_{2,\infty}\leq
C\left\\{\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{2}_{2,\infty}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}_{2,\infty}\right\\}.$

By Lemma E.13, with probability at least $1-O\\{(np)^{-10}\\}$

$\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle\leq
C\bar{\sigma}^{2}\ln(np)\left\\{r+\|\phi^{\textsc{(lr)}}\|_{2}+\|\beta^{*}\|_{1}(\sqrt{n}\bar{A}+\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|_{2,\infty})\right\\}.$

Simplifying, with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\|\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}(\hat{\beta}-\beta^{*})\|^{2}_{2}$
$\displaystyle\quad\leq
C\frac{\bar{\sigma}^{2}\ln(np)}{\hat{s}_{r}^{2}}\left[r+\
\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\left\\{\sqrt{n}\bar{A}\frac{1}{\|\beta^{*}\|_{1}}+\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|^{2}_{2,\infty}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}_{2,\infty}\right\\}\right].$

Note that we have taken $x\vee x^{2}\leq x^{2}$ for
$x\in\\{\|\phi^{\textsc{(lr)}}\|_{2},\|\hat{\boldsymbol{A}}-\boldsymbol{A}\|_{2,\infty}\|\beta^{*}\|_{1}\\}$.
To justify this simplification, one may consider redefining $\tilde{x}=x\vee
1$, since the objects taken as $x$ are diverging.

By Lemma D.10 and Lemma D.15, with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\left\|\hat{\boldsymbol{A}}-\boldsymbol{A}\right\|^{2}_{2,\infty}$
$\displaystyle\leq\frac{C(K_{a}+\bar{K}\bar{A})^{2}}{\rho^{4}_{\min}}\bigg{(}r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}\bigg{)}\ln^{2}(np)+C\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}_{2,\infty}.$

In summary, with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\|\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}(\hat{\beta}-\beta^{*})\|^{2}_{2}$
$\displaystyle\leq\frac{C(K_{a}+\bar{K}\bar{A})^{2}}{\rho^{4}_{\min}}\frac{\bar{\sigma}^{2}\ln^{3}(np)}{\hat{s}_{r}^{2}}$
$\displaystyle\cdot\left[\
\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\left\\{\frac{\sqrt{n}}{\|\beta^{*}\|_{1}}+r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}_{2,\infty}\right\\}\right].$

∎

######  Lemma E.15.

Suppose the conditions of Lemma E.14 hold. With probability at least
$1-O\\{(np)^{-10}\\}$, $\|\hat{\beta}-\beta^{*}\|^{2}_{2}\leq(1)+(2)$ where

$\displaystyle(1)$
$\displaystyle=C\frac{\|\beta^{*}\|^{2}_{2}}{\rho^{2}_{\min}s_{r}^{2}}\left\\{(n+p)\Delta^{2}_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}+\bar{A}^{2}\ln(np)p\right\\}$

and (2) is defined above.

###### Proof.

By Lemma E.5

$\displaystyle\|\hat{\beta}-\beta^{*}\|^{2}_{2}$ $\displaystyle\leq
C\left[\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{k}\hat{\boldsymbol{V}}_{k}^{T}\|^{2}\|\beta^{*}\|^{2}_{2}+\frac{1}{\hat{s}_{k}^{2}}\Big{\\{}\|\hat{\boldsymbol{A}}-\boldsymbol{A}^{\textsc{(lr)}}\|^{2}_{2,\infty}\|\beta^{*}\|^{2}_{1}\
\vee\ \|\phi^{\textsc{(lr)}}\|^{2}_{2}\ \vee\
\langle\hat{\boldsymbol{A}}(\hat{\beta}-\beta^{*}),\varepsilon\rangle\Big{\\}}\right].$

By Lemma E.14, it suffices to focus on the first term, since the latter is
bounded by $(2)$. By Proposition D.10, Lemma E.8, and since $\delta\leq C$ and
$\|\boldsymbol{A}^{\textsc{(lr)}}\|\leq\bar{A}\sqrt{np}$, with probability at
least $1-O\\{(np)^{-10}\\}$

$\displaystyle\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}\|$
$\displaystyle\leq
C\frac{\delta}{\rho_{\min}s_{r}}\left\\{(\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\sqrt{\frac{\ln(np)}{n}}\|\boldsymbol{A}^{\textsc{(lr)}}\|\right\\}$
$\displaystyle\leq\frac{C}{\rho_{\min}s_{r}}\left\\{(\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\bar{A}\sqrt{\ln(np)}\sqrt{p}\right\\}.$

Simplifying, with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\|\hat{\beta}-\beta^{*}\|^{2}_{2}\leq
C\frac{\|\beta^{*}\|^{2}_{2}}{\rho^{2}_{\min}s_{r}^{2}}\left\\{(n+p)\Delta^{2}_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}+\bar{A}^{2}\ln(np)p\right\\}+(2)$

∎

######  Remark E.12 (Dictionary).

In the generalization of Lemmas E.14 and E.15, note the new appearance of
$C_{b}^{\prime}$ in (2):

$\displaystyle(1)$
$\displaystyle=C\frac{\|\beta^{*}\|^{2}_{2}}{(\rho^{\prime}_{\min})^{2}s_{r^{\prime}}^{2}}\left[(n+p)\Delta_{H,op}^{2}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}+\bar{A}^{2}\ln(np)\cdot
p\right]$ $\displaystyle(2)$
$\displaystyle=\frac{CC_{b}^{\prime}(K_{a}+\bar{K}\bar{A})^{2}}{(\rho^{\prime}_{\min})^{4}}\frac{\bar{\sigma}^{2}\ln^{3}(np)}{\hat{s}_{r^{\prime}}^{2}}$
$\displaystyle\cdot\bigg{[}\
\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\bigg{\\{}\frac{\sqrt{n}}{\|\beta^{*}\|_{1}}+r^{\prime}+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}$
$\displaystyle\quad+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}_{2,\infty}+\|b(\boldsymbol{A})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\bigg{\\}}\bigg{]}.$

###### Proof.

For simplicity, we prove the result by focusing on
$\|\hat{\beta}-\beta^{*}\|^{2}_{2}$. By Lemma E.6

$\displaystyle\|\hat{\beta}-\beta^{*}\|^{2}_{2}$ $\displaystyle\leq
C\left[\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{r^{\prime}}\hat{\boldsymbol{V}}_{r^{\prime}}^{T}\|^{2}\|\beta^{*}\|^{2}_{2}+\frac{1}{\hat{s}_{r^{\prime}}^{2}}\Big{\\{}\|b(\hat{\boldsymbol{A}})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\|\beta^{*}\|^{2}_{1}\
\vee\ \|\phi^{\textsc{(lr)}}\|^{2}_{2}\ \vee\ \langle
b(\hat{\boldsymbol{A}})(\hat{\beta}-\beta^{*}),\varepsilon\rangle\Big{\\}}\right].$

By Remark E.8 and analogous algebra,

$\displaystyle\|\boldsymbol{V}\boldsymbol{V}^{T}-\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}\|$
$\displaystyle\leq\frac{C}{\rho^{\prime}_{\min}s_{r^{\prime}}}\left\\{(\sqrt{n}+\sqrt{p})\Delta_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|+\bar{A}\sqrt{\ln(np)}\sqrt{p}\right\\}.$

Note that

$\|b(\hat{\boldsymbol{A}})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\leq
C\left\\{\|b(\hat{\boldsymbol{A}})-b(\boldsymbol{A})\|^{2}_{2,\infty}+\|b(\boldsymbol{A})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\right\\}.$

By Remark E.11, with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\langle
b(\hat{\boldsymbol{A}})(\hat{\beta}-\beta^{*}),\varepsilon\rangle$
$\displaystyle\leq
C\bar{\sigma}^{2}\ln(np)\left\\{r^{\prime}+\|\phi^{\textsc{(lr)}}\|_{2}+\|\beta^{*}\|_{1}(\sqrt{n}\bar{A}^{\prime}+\|b(\hat{\boldsymbol{A}})-b(\boldsymbol{A})\|_{2,\infty})\right\\}.$

Simplifying, with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\|\hat{\beta}-\beta^{*}\|^{2}_{2}$ $\displaystyle\quad\leq
C\frac{\|\beta^{*}\|^{2}_{2}}{(\rho^{\prime}_{\min})^{2}s_{r^{\prime}}^{2}}\left\\{(n+p)\Delta^{2}_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}+\bar{A}^{2}\ln(np)p\right\\}$
$\displaystyle\quad+C\frac{\bar{\sigma}^{2}\ln(np)}{\hat{s}_{r^{\prime}}^{2}}\left[r^{\prime}+\
\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\left\\{\sqrt{n}\bar{A}^{\prime}\frac{1}{\|\beta^{*}\|_{1}}+\|b(\hat{\boldsymbol{A}})-b(\boldsymbol{A})\|^{2}_{2,\infty}+\|b(\boldsymbol{A})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\right\\}\right].$

By Lemma D.10 and Lemma D.15, with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\left\|b(\hat{\boldsymbol{A}})-b(\boldsymbol{A})\right\|^{2}_{2,\infty}$
$\displaystyle\leq\frac{CC_{b}^{\prime}(K_{a}+\bar{K}\bar{A})^{2}}{\rho^{4}_{\min}}\bigg{(}r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}\bigg{)}\ln^{2}(np)+C\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}_{2,\infty}.$

In summary, with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\|\hat{\beta}-\beta^{*}\|^{2}_{2}$ $\displaystyle\leq
C\frac{\|\beta^{*}\|^{2}_{2}}{(\rho^{\prime}_{\min})^{2}s_{r^{\prime}}^{2}}\left\\{(n+p)\Delta^{2}_{H,op}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}+\bar{A}^{2}\ln(np)p\right\\}$
$\displaystyle+\frac{CC_{b}^{\prime}(K_{a}+\bar{K}\bar{A})^{2}}{(\rho^{\prime}_{\min})^{4}}\frac{\bar{\sigma}^{2}\ln^{3}(np)}{\hat{s}_{r^{\prime}}^{2}}$
$\displaystyle\cdot\bigg{[}\
\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\bigg{\\{}\frac{\sqrt{n}}{\|\beta^{*}\|_{1}}+r^{\prime}+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}$
$\displaystyle\quad+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}_{2,\infty}+\|b(\boldsymbol{A})-b\\{\boldsymbol{A}^{\textsc{(lr)}}\\}\|^{2}_{2,\infty}\bigg{\\}}\bigg{]}.$

∎

######  Proposition E.2 (Projected train error).

Suppose conditions of Theorem 5.1 hold. Further suppose Assumptions 5.5 and
5.6 hold. Let $k=r$ and

$\rho_{\min}\gg\tilde{C}\sqrt{r}\ln^{\frac{3}{2}}(np)\left(\frac{1}{\sqrt{p}}\vee\frac{1}{\sqrt{n}}\vee\Delta_{E}\right),\quad\tilde{C}:=C\bar{A}\Big{(}\kappa+\bar{K}+K_{a}\Big{)}.$

Then with probability at least $1-O\\{(np)^{-10}\\}$

$\displaystyle\|\hat{\boldsymbol{V}}_{r}\hat{\boldsymbol{V}}_{r}^{T}(\hat{\beta}-\beta^{*})\|^{2}_{2}$
$\displaystyle\leq
C\bar{A}^{4}(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}\frac{\bar{\sigma}^{2}}{\rho^{4}_{\min}}\cdot
r\ln^{6}(np)$ $\displaystyle\quad\cdot\left\\{\
\frac{1}{np}\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\left(\frac{\sqrt{n}}{\|\beta^{*}\|_{1}np}+\frac{r}{np}+\frac{r}{p^{2}}+\frac{r}{p}\Delta_{E}^{2}\right)\right\\}.$

###### Proof.

We proceed in steps.

  1. 1.

Recall the inequalities

$\displaystyle s_{r}^{2}$ $\displaystyle\geq
C\frac{np}{r},\quad\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}\leq
np\Delta_{E}^{2},\quad\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}_{2,\infty}\leq
n\Delta_{E}^{2}.$

Further,

$\Delta_{H,op}^{2}\leq
C\cdot\bar{A}^{2}(\kappa+\bar{K}+K_{a})^{2}\ln^{3}(np).$

Moreover, $(n+p)\Delta_{H,op}^{2}$ dominates $\ln(np)p\bar{A}^{2}$.

  2. 2.

Simplifying the RHS of the bound in Lemma E.14

$\displaystyle(2)$
$\displaystyle:=\frac{C(K_{a}+\bar{K}\bar{A})^{2}}{\rho^{4}_{\min}}\frac{\bar{\sigma}^{2}\ln^{3}(np)}{\hat{s}_{r}^{2}}$
$\displaystyle\cdot\left[\
\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\left\\{\frac{\sqrt{n}}{\|\beta^{*}\|_{1}}+r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}_{2,\infty}\right\\}\right].$

Bounding its latter factor

$\displaystyle\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\left\\{\frac{\sqrt{n}}{\|\beta^{*}\|_{1}}+r+\frac{n(n+p)\Delta_{H,op}^{2}+n\left\|\boldsymbol{E}^{\textsc{(lr)}}\right\|^{2}+\ln(np)np\bar{A}^{2}}{s_{r}^{2}}+\|\boldsymbol{E}^{\textsc{(lr)}}\|^{2}_{2,\infty}\right\\}$
$\displaystyle\leq\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\left\\{\frac{\sqrt{n}}{\|\beta^{*}\|_{1}}+r+\frac{n(n+p)\Delta_{H,op}^{2}+n^{2}p\Delta_{E}^{2}}{s_{r}^{2}}+n\Delta_{E}^{2}\right\\}$
$\displaystyle\leq\
\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\left\\{\frac{\sqrt{n}}{\|\beta^{*}\|_{1}}+r+\frac{r}{p}(n+p)\Delta^{2}_{H,op}+rn\Delta_{E}^{2}\right\\}.$

Hence

$\displaystyle(2)$ $\displaystyle\leq
C\bar{A}^{4}(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}\ln^{6}(np)\frac{\bar{\sigma}^{2}}{\rho^{4}_{\min}\hat{s}_{r}^{2}}$
$\displaystyle\quad\cdot\left\\{\
\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\left(\frac{\sqrt{n}}{\|\beta^{*}\|_{1}}+r+\frac{rn}{p}+rn\Delta_{E}^{2}\right)\right\\}.$

  3. 3.

By Lemma E.9,

$\hat{s}^{2}_{r}\gtrsim s^{2}_{r}\geq C\frac{np}{r}$

so as long as the regularity condition holds, we can further bound

$\displaystyle\frac{1}{\hat{s}_{r}^{2}}\left\\{\
\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\left(\frac{\sqrt{n}}{\|\beta^{*}\|_{1}}+r+\frac{rn}{p}+rn\Delta_{E}^{2}\right)\right\\}$
$\displaystyle\leq r\left\\{\
\frac{1}{np}\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\frac{1}{np}\|\beta^{*}\|^{2}_{1}\left(\frac{\sqrt{n}}{\|\beta^{*}\|_{1}}+r+\frac{rn}{p}+rn\Delta_{E}^{2}\right)\right\\}$
$\displaystyle=r\left\\{\
\frac{1}{np}\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\left(\frac{\sqrt{n}}{\|\beta^{*}\|_{1}np}+\frac{r}{np}+\frac{r}{p^{2}}+\frac{r}{p}\Delta_{E}^{2}\right)\right\\}.$

In summary

$\displaystyle(2)$ $\displaystyle\leq
C\bar{A}^{4}(K_{a}+\bar{K})^{2}(\kappa+\bar{K}+K_{a})^{2}\bar{\sigma}^{2}\frac{r\ln^{6}(np)}{\rho^{4}_{\min}}$
$\displaystyle\left\\{\
\frac{1}{np}\|\phi^{\textsc{(lr)}}\|^{2}_{2}+\|\beta^{*}\|^{2}_{1}\left(\frac{\sqrt{n}}{\|\beta^{*}\|_{1}np}+\frac{r}{np}+\frac{r}{p^{2}}+\frac{r}{p}\Delta_{E}^{2}\right)\right\\}.$

∎

######  Remark E.13 (Dictionary).

The generalization of Proposition E.2 is as follows. Suppose