# Adversarial Tradeoffs in Linear Inverse Problems and Robust State Estimation

Bruce D. Lee , Thomas T.C.K. Zhang11footnotemark: 1 , Hamed Hassani, and
Nikolai Matni Equal contribution

(Department of Electrial and Systems Engineering, University of Pennsylvania)

###### Abstract

Adversarially robust training has been shown to reduce the susceptibility of
learned models to targeted input data perturbations. However, it has also been
observed that such adversarially robust models suffer a degradation in
accuracy when applied to unperturbed data sets, leading to a robustness-
accuracy tradeoff. In this paper, we provide sharp and interpretable
characterizations of such robustness-accuracy tradeoffs for linear inverse
problems. In particular, we provide an algorithm to find the optimal
adversarial perturbation given data, and develop tight upper and lower bounds
on the adversarial loss in terms of the standard (non-adversarial) loss and
the spectral properties of the resulting estimator. Further, motivated by the
use of adversarial training in reinforcement learning, we define and analyze
the _adversarially robust Kalman Filtering problem._ We apply a refined
version of our general theory to this problem, and provide the first
characterization of robustness-accuracy tradeoffs in a setting where the data
is generated by a dynamical system. In doing so, we show a natural connection
between a filter’s robustness to adversarial perturbation and underlying
control theoretic properties of the system being observed, namely the spectral
properties of its observability gramian.

##  1 Introduction

It has been demonstrated across various application areas that contemporary
learned models, despite their impressive nominal performance, can be extremely
susceptible to small, adversarially designed input perturbations (Carlini and
Wagner, 2016; Goodfellow et al., 2014; Szegedy et al., 2013; Huang et al.,
2017). In order to mitigate the effects of such attacks, various adversarially
robust training algorithms (Carlini and Wagner, 2016, 2017; Madry et al.,
2017; Xie et al., 2020; Deka et al., 2020) have been developed. However, it
was soon noticed that while adversarial training could be used to improve
model robustness, it often came with a corresponding decrease in accuracy on
nominal (unperturbed) data. Further, various simplified theoretical models
(Tsipras et al., 2018; Zhang et al., 2019; Nakkiran, 2019; Raghunathan et al.,
2019; Chen et al., 2020; Javanmard et al., 2020), have been used to explain
this phenomena, and to argue that such _robustness-accuracy tradeoffs_ are
unavoidable.

In this paper, we continue the study of such robustness-accuracy tradeoffs,
with a focus on linear inverse problems. Such problems are ubiquitous in
machine learning and engineering, with application areas spanning medical
imaging (Ribes and Schmitt, 2008), systems biology (Engl et al., 2009),
econometrics (Carrasco et al., 2007), recommender systems (Recht et al.,
2010), communications (Candes and Tao, 2005), and others. We show that due to
the convexity of both the nominal and adversarial linear inverse problems,
robustness-accuracy tradeoffs can be sharply and interpretably characterized
in terms of the spectral properties of a given linear model. We then define
and analyze an _adversarially robust Kalman Filtering problem_ by applying a
refined version of our general tools. Motivated by applications of adversarial
robustness in the reinforcement literature (Lutter et al., 2021; Pinto et al.,
2017; Mandlekar et al., 2017), we provide the first theoretical analysis of
robustness-accuracy tradeoffs in a setting where data is generated by a
_dynamical system_ , and in doing so establish connections to natural control
theoretic properties of the underlying system.

Our specific contributions can be summarized as follows:

  * •

We propose a simple and computationally efficient algorithm that provably
finds the worst-case optimal $\ell^{2}$ norm-bounded adversarial perturbation
for a given linear model and data-set. This allows us to efficiently compute
and explore the Pareto-optimal robustness-accuracy tradeoff curve.

  * •

We derive interpretable upper and lower bounds on the gap between the
adversarial and standard (unperturbed) risks in terms of the spectral
properties of a given linear model. We also show that our bounds are tight in
the one-dimensional setting, recovering the results of (Javanmard et al.,
2020), and for matrices with full column rank and orthogonal columns.

  * •

We define and analyze an _adversarially robust Kalman Filtering_ problem, and
show that upper and lower bounds on the gap between the adversarial and
standard (unperturbed) risk can be controlled in terms of the spectral
properties of the _observability gramian_ (Zhou and Doyle, 1998) of the
underlying system.

  * •

We empirically demonstrate through extensive numerical experiments that our
results qualitatively and quantitatively predict robustness-accuracy tradeoffs
in linear inverse problems as a function of underlying spectral properties of
the optimal nominal solution.

The rest of this paper is organized as follows: in Section 2, we present the
general linear inverse problem along with an algorithm that solves the problem
in an adversarial setting. We then derive tight upper and lower bounds on the
adversarial risk, providing an interpretable characterization of the optimal
tradeoff between robustness and accuracy. In Section 3, we pose the
adversarially robust Kalman Filtering problem as a linear inverse problem, and
refine the general bounds developed in the previous section, revealing that
for the setting where data is generated by a dynamical system, robustness-
accuracy tradeoffs are dictated by natural control theoretic properties of the
underlying system (namely, the observability gramian). In Section 4, we
provide empirical evidence to support the trends predicted by our bounds, and
we end with conclusions and a discussion of future work in Section 5.

###  1.1 Related Work

Our work makes connections between adversarial robustnesss and robust
estimation and control. We now provide a brief overview of work most directly
related to ours from these two areas.

Robustness-accuracy tradeoffs: We draw inspiration from recent work offering
theoretical characterizations of robustnesss-accuracy tradeoffs: Tsipras et
al. (2018) and Zhang et al. (2019) posit that high standard accuracy is
fundamentally at odds with high robust accuracy by considering classification
problems, whereas Nakkiran (2019) suggests an alternative explanation that
classifiers that are simultaneously robust and accurate are complex, and may
not be contained in current function classes. However, Raghunathan et al.
(2019) shows that the tradeoff is not due to optimization or representation
issues by showing that such tradeoffs exist even for a problem with a convex
loss where the optimal predictor achieves 100% standard and robust accuracy.
In contrast to previous work, we provide sharp and interpretable
characterizations of the robustness-accuracy tradeoffs that may arise in
regression problems, albeit restricted to linear models. Most closely related
to our work, Javanmard et al. (2020) derive a formula for the exact tradeoff
between standard and robust accuracy in the linear regression setting, which
can be viewed as a 1-d linear inverse problem. We generalize these results to
the matrix-valued setting, and further apply these tools to the adversarially
robust Kalman Filtering problem, wherein data is generated by a dynamical
system.

Robust estimation and control: Robustness in estimation and control has
traditionally been studied from a worst-case induced gain perspective (Hassibi
et al., 1999; Zhou and Doyle, 1998). When perturbations are restricted to be
$\ell^{2}$-bounded, this gives rise to so-called $\mathcal{H}_{\infty}$
estimation and control problems. Although widely known, and celebrated for
their applications in robust control, $\mathcal{H}_{\infty}$-based methods are
often overly conservative. This conservatism can be reduced by using mixed
$\mathcal{H}_{2}/\mathcal{H}_{\infty}$ methods (Khargonekar et al., 1996),
which blend gaussian disturbance assumptions with worst case disturbances.
While such an approach is related to the adversarially robust Kalman Filtering
problem that we pose, we note that it decouples the adversarial and stochastic
inputs during design, leading to a fundamentally different tradeoff. We leave
characterizing a connection between traditional and adversarial robustness to
future work. More recently, Al Makdah et al. (2020) have considered the
robustness-accuracy tradeoff in data-driven perception-based control. However,
the adversary in (Al Makdah et al., 2020) perturbs the covariance of the noise
distribution, which is assumed to remain gaussian, whereas our adversary
additively attacks each measurement, which is more aligned to the standard
adversarial perturbations considered in machine learning contexts.
Additionally, (Al Makdah et al., 2020) does not quantitatively analyze the
severity of tradeoffs, but rather proves the existence of tradeoffs.

##  2 The Linear Inverse Problem

We consider the following linear inverse problem, where given data
$x\in\mathbb{R}^{n}$, measurements $y\in\mathbb{R}^{p}$ are generated by

$y=A_{\star}x+w$ (1)

where $w\in\mathbb{R}^{p}$ is a noise vector and $A_{\star}$ is an unknown
ground-truth matrix. Our goal is to estimate the ground truth matrix
$A_{\star}$ through an estimator $\hat{A}$.

In the following subsection, we introduce the fundamental tradeoff between
accuracy of the resulting estimator $\hat{A}$ under an assumed noise
distribution, and the robustness of this estimator to adversarial attacks. In
§2.2, we show how to solve for the worst-case adversarial perturbations, which
provides a means of computing the performance of the estimator in the face of
adversarial attacks. §2.3 provides upper and lower bounds on the gap between
the robust performance and the nominal performance, which allow for prediction
of the severity of the tradeoffs based on properties of the underlying
problem.

###  2.1 Optimal Robustness-Accuracy Tradeoffs

When the noise vector $w$ in equation (1) is assumed to be stochastic, then
the minimum mean square estimator can be found by solving the following
stochastic optimization problem:

$\displaystyle\hat{A}$
$\displaystyle=\operatorname*{argmin}_{A\in\mathbb{R}^{p\times
n}}\;\mathbb{E}_{x,w}\left[\left\|y-Ax\right\|_{2}^{2}\right]=:\operatorname*{argmin}_{A\in\mathbb{R}^{p\times
n}}\;\operatorname{SR}(A).$ (2)

where $\left\|\cdot\right\|_{2}$ is the Euclidean norm, and we use
$\operatorname{SR}(A)$ to denote the _standard risk of $A$_, i.e.,
$\operatorname{SR}(A)$ is the mean squared error incurred by a matrix $A$. We
then consider the same problem but with the inclusion of an $\ell^{2}$-norm
bounded adversary:

$\displaystyle\hat{A}(\varepsilon)$
$\displaystyle=\operatorname*{argmin}_{A\in\mathbb{R}^{p\times
n}}\;\mathbb{E}_{x,w}\left[\max_{\left\|\delta\right\|_{2}\leq\varepsilon}\left\|y-A(x+\delta)\right\|_{2}^{2}\right]=:\operatorname*{argmin}_{A\in\mathbb{R}^{p\times
n}}\;\operatorname{AR}(A),$ (3)

where $\operatorname{AR}(A)$ denotes the _adversarial risk of $A$_.

Our objective in this section is to precisely characterize the optimal
robustness-accuracy tradeoff curve defined by the adversarial and standard
risks. We refer to the set of all points
$(\operatorname{SR}(A),\operatorname{AR}(A))$ over all
$A\in\mathbb{R}^{p\times n}$ as the $(\operatorname{SR},\operatorname{AR})$
region. The optimal tradeoff between standard and adversarial risks is
characterized via the so-called Pareto boundary of this region, which we
denote
$\left\\{(\operatorname{SR}(A_{\lambda}),\operatorname{AR}(A_{\lambda})):\lambda\geq
0\right\\}$. Using standard results in multi-objective optimization,
$A_{\lambda}$ are computed by solving the regularized optimization problem

$\displaystyle A_{\lambda}$
$\displaystyle:=\operatorname*{argmin}_{A}\;\operatorname{SR}(A)+\lambda\operatorname{AR}(A).$
(4)

Varying the regularization parameter $\lambda$ in problem (4) thus allows us
to characterize the aforementioned Pareto boundary by interpolating between
the solution to the standard (i.e., $A_{0}$) and adversarial (i.e.,
$A_{\infty}$) linear inverse problems. Our first contribution is to show that
the solution $A_{\lambda}$ to the regularized optimization problem (4) can be
computed efficiently using stochastic optimization.

In what follows, we assume that the noise $w\sim{}\mathcal{N}(0,\Sigma_{w})$,
$\Sigma_{w}\succ 0$, and that the data $x\sim{}\mathcal{N}(0,\Sigma_{x})$,
$\Sigma_{x}\succ 0$. It is simple to verify that under these assumptions, the
standard risk $\operatorname{SR}(A)$ is given by

$\displaystyle\operatorname{SR}(A)$
$\displaystyle=\mathbb{E}_{x,w}\left[\left\|(y-A_{\star}x)+(A_{\star}-A)x\right\|_{2}^{2}\right]=\operatorname{\mathrm{tr}}(\Sigma_{w})+\operatorname{\mathrm{tr}}\left((A-A_{\star})\Sigma_{x}(A-A_{\star})^{\top}\right)$
(5)

However, due to the inner maximization in the adversarial risk in equation
(5), no such closed-form expression exists for $\operatorname{AR}(A)$. We show
next that despite the non-convexity of the the inner maximization problem, it
can be solved efficiently. This allows us to apply stochastic gradient descent
to solve $\min_{A}\operatorname{AR}(A)$. In particular, note that
$\operatorname{AR}(A)$ is the linear combination of a point-wise supremum of
convex functions in $A$, and hence convex in $A$ itself (Boyd and
Vandenberghe, 2004). Next observe that we can draw samples of
$x\sim\mathcal{N}(0,\Sigma_{x})$ and $w\sim\mathcal{N}(0,\Sigma_{w})$, and
apply the solution to the inner maximization problem to solve for realizations
of
$\max_{\left\|\delta\right\|_{2}\leq\epsilon}\left\|y-A(x+\delta)\right\|_{2}^{2}$.
Taking the gradient of these realizations with respect to $A$ provides a
stochastic descent direction. As the overall expression is convex in $A$,
stochastic gradient descent with an appropriately decaying stepsize converges
to the optimal solution (Bottou et al., 2018).

###  2.2 Solving the Inner Maximization

To the best of our knowledge, no closed-form expression exists for the
adversarial risk: indeed, even in the scalar case studied in (Javanmard et
al., 2020), it is characterized by a recursive relationship. Further, the
techniques used to derive that recursion do not extend to the multi-variable
case.

To address this challenge, we show how to efficiently compute solutions to the
inner maximization of the adversarial risk $\operatorname{AR}(A)$. We observe
that the inner maximization
$\max_{\left\|\delta\right\|_{2}\leq\varepsilon}\left\|y-A(x+\delta)\right\|_{2}^{2}$
can be expanded and re-written as the following (non-convex) quadratically-
constrained quadratic maximization problem:

$\displaystyle\operatorname*{maximize}_{\delta\in\mathbb{R}^{n}}$
$\displaystyle\quad\delta^{\top}A^{\top}A\delta-2\delta^{\top}A^{\top}b$ (P)
$\displaystyle\operatorname{subject\ to}$
$\displaystyle\quad\delta^{\top}\delta\leq\varepsilon^{2},$

where we set $b:=y-Ax$. Let $A=U\Sigma V^{\top}\in\mathbb{R}^{p\times n}$ be
the full singular-value decomposition of $A$, with $U\in\mathbb{R}^{p\times
p}$, $\Sigma\in\mathbb{R}^{p\times n}$, $V\in\mathbb{R}^{n\times n}$, and
$\Sigma=\mathrm{diag}(\sigma_{1},\dots,\sigma_{\min\left\\{n,p\right\\}})$,
$\sigma_{1}\geq\cdots\geq\sigma_{\min\left\\{n,p\right\\}}\geq 0$ the nonzero
singular values of $A$. We also denote the columns of $U$ and $V$ by $u_{i}$
and $v_{i}$, respectively. It is known that (P) satisfies strong duality (Boyd
and Vandenberghe, 2004) and the optimal primal-dual pair
$(\delta^{*},\lambda^{*})$ can be characterized by the KKT conditions:

$\displaystyle 2(\lambda^{*}I-A^{\top}A)\delta^{*}+2A^{\top}b$
$\displaystyle=0$
$\displaystyle\lambda^{*}({\delta^{*}}^{\top}\delta^{*}-\varepsilon^{2})$
$\displaystyle=0$ $\displaystyle(\lambda^{*}I-A^{\top}A)$
$\displaystyle\succeq 0.$

The KKT conditions can then be leveraged to solve for the optimal dual
solution $\lambda^{*}$ and subsequently the optimal perturbation $\delta^{*}$.
The full procedure is summarized in Algorithm 1.

We note that Boyd and Vandenberghe (2004) show how to solve (P) via
semidefinite programming. Algorithm 1, however, allows us to recycle the SVD
of $A$ to solve (P) for various values of $b$ simply by solving a root finding
problem for each $b$. This enables efficient batching when applying SGD to the
outer minimization problem.

Algorithm 1 Inner Maximization Solution

given $A=U\Sigma V^{\top}\in\mathbb{R}^{p\times n}$, $b\in\mathbb{R}^{p}$,
perturbation bound $\varepsilon>0$

if
$\sum_{i:\sigma_{i}<\sigma_{1}}\frac{(b^{\top}u_{i})^{2}\sigma_{i}^{2}}{(\sigma_{1}^{2}-\sigma_{i}^{2})^{2}}<\varepsilon^{2}$
then

$c=\sqrt{\varepsilon^{2}-\sum_{i:\sigma_{i}<\sigma_{1}}\frac{(b^{\top}u_{i})^{2}\sigma_{i}^{2}}{(\sigma_{1}^{2}-\sigma_{i}^{2})^{2}}}$

Set $v$ as any unit vector lying in the null-space of
$\left(\sigma_{1}^{2}I-\Sigma^{\top}\Sigma\right)V^{\top}$, i.e.
$v\in\textbf{span}\left\\{v_{i}:\sigma_{i}=\sigma_{1}\right\\}$

$\delta^{*}=-V(\sigma_{1}^{2}I-\Sigma^{\top}\Sigma)^{\dagger}\Sigma^{\top}U^{\top}b+cv$

else

solve
$\sum_{i=1}^{m}\frac{(b^{\top}u_{i})^{2}\sigma_{i}^{2}}{(\lambda-\sigma_{i}^{2})^{2}}=\varepsilon^{2}$
for $\lambda$, e.g. by Newton’s method

$\delta^{*}=-V(\lambda^{*}I-\Sigma^{\top}\Sigma)^{-1}\Sigma^{\top}U^{\top}b$

end if

return $\delta^{*}$

The proof of correctness for Algorithm 1 is detailed in Appendix A.1.

###  2.3 Lower and Upper Bounds on $\operatorname{AR}(A)-\operatorname{SR}(A)$

Although no closed-form expression exists for the adversarial risk
$\operatorname{AR}(A)$, we show now that interepretable upper and lower bounds
on the robustness-accuracy tradeoff, as characterized by the gap
$\operatorname{AR}(A)-\operatorname{SR}(A)$, can be derived. Such bounds
predict the severity of the robustness-accuracy traeoff based upon underlying
properties of specific linear inverse problems. We further show that these
bounds are tight in the sense that they are exact for certain classes of
matrices $A$, and strong in the sense that the lower and upper bounds differ
only in higher-order terms with respect to the adversarial budget
$\varepsilon$.

######  Theorem 2.1.

Given any $A\in\mathbb{R}^{p\times n}$, we have the following lower bound on
$\operatorname{AR}(A)-\operatorname{SR}(A)$:

$\displaystyle\operatorname{AR}(A)-\operatorname{SR}(A)\geq
2\varepsilon\;\mathbb{E}_{x,w}\left[\left\|A^{\top}(y-Ax)\right\|_{2}\right]+\varepsilon^{2}\lambda_{\min}A^{\top}A),$
(6)

and a corresponding upper bound

$\displaystyle\operatorname{AR}(A)-\operatorname{SR}(A)\leq
2\varepsilon\;\mathbb{E}_{x,w}\left[\left\|A^{\top}(y-Ax)\right\|_{2}\right]+\varepsilon^{2}\lambda_{\max}(A^{\top}A),$
(7)

where $\lambda_{\min}(A^{\top}A)$ and $\lambda_{\max}(A^{\top}A)$ are the
minimum and maximum eigenvalues of $A^{\top}A$, respectively.

The proof of these bounds relies on turning the inner maximization of the
adversarial risk into various equivalent optimization problems, and utilizing
the properties of Schur complements and the S-lemma. The full proof is
relegated to Appendix A.2.

We note that when $A^{\top}\in\mathbb{R}^{n}$, equation (7) recovers the exact
characterization of the gap $\operatorname{AR}(A)-\operatorname{SR}(A)$
provided in (Javanmard et al., 2020, Lemma 3.1); thus when $p=1$, the
inequality in equation (7) is in fact an equality. We also note that the upper
and lower bounds differ only in the $\mathcal{O}(\varepsilon^{2})$ terms. This
leads immediately to the following corollary.

######  Corollary 2.1.

If $p\geq n$ and $A$ has orthogonal columns, then bounds (6) and (7) match.

###### Proof.

If $p\geq n$ and $A$ has orthogonal columns, then
$\lambda_{\min}(A^{\top}A)=\lambda_{\max}(A^{\top}A)$. ∎

The terms involving the eigenvalues of $A^{\top}A$ in our bounds also support
the intuition that adversarial robustness is a form of implicit
regularization, which is visualized in Figure 1. In the one-dimensional linear
classification setting, this phenomenon is well-understood (Tsipras et al.,
2018; Dobriban et al., 2020), where robustness to adversarial perturbations
prevent a robust feature vector from relying on an aggregate of small
features.

Figure 1: Optimizing for adversarial robustness induces an implicit
regularization, which is visualized in this heatmap of a $5\times 5$ nominal
solution $A_{\star}$ (left) and adversarially robust solution
$\hat{A}(\varepsilon)$ (right), where $\varepsilon=0.5$,
$x\sim\mathcal{N}(0,0.5I)$, and $w\sim\mathcal{N}(0,0.1I)$.

Leveraging bounds (6) and (7) from Theorem 3.5, we can bound both the
susceptibility and robustness of a particular linear model to adversarial
perturbations. In particular, the solution to the standard risk problem, which
is $A_{\star}$ (as seen from (5)), provides key insights into the properties
of the problem.

######  Corollary 2.2.

Assume that $w\sim{}\mathcal{N}(0,\sigma_{w}^{2}I_{p})$. Then

$\displaystyle 2\varepsilon\sigma_{w}\sqrt{\frac{2}{\pi
p}}\operatorname{\mathrm{tr}}\left(\left(A_{\star}^{\top}A_{\star}\right)^{\frac{1}{2}}\right)+\varepsilon^{2}\lambda_{\min}(A_{\star}^{\top}A_{\star})\leq\;\operatorname{AR}(A_{\star})-\operatorname{SR}(A_{\star})\leq\;2\varepsilon\sigma_{w}\sqrt{\operatorname{\mathrm{tr}}\left(A_{\star}^{\top}A_{\star}\right)}+\varepsilon^{2}\lambda_{\max}(A_{\star}^{\top}A_{\star}).$

Corollary 2.2 highlights that the spectral properties of the ground truth
model $A_{\star}$ influences both the susceptibility and robustness of a
nominal model to adversarial perturbations. A more refined analysis akin to
Corollary 2.2 will form the basis of our analysis for the adversarially robust
Kalman Filtering problem posed in the next section.

##  3 Adversarially Robust Kalman Filtering

We consider a modification to the standard Kalman Filtering problem (reviewed
in §3.1) to incorporate adversarial robustness. We then extend and refine the
tools developed in §2.3 to this setting, with the goal of relating control
theoretic properties of the underlying linear dynamical system to the
robustness-accuracy tradeoffs that it induces.

###  3.1 State Estimation and Observability

State estimation, which is central to control theory, can be viewed as an
inverse problem: the goal is to recover an estimate of the underlying state of
a dynamical system given noisy partial observations thereof. A particularly
interesting example of a state estimator is the Kalman Filter, which is
designed for the setting where the underlying dynamical system is linear, and
disturbances are Gaussian. In particular, consider a linear-time-invariant
(LTI) autonomous system with state and measurement disturbances: let
$x_{t}\in\mathbb{R}^{n}$ be the system state, $w_{t}\in\mathbb{R}^{n}$ the
process noise, $y_{t}\in\mathbb{R}^{p}$ the measurement, and
$v_{t}\in\mathbb{R}^{p}$ the measurement noise. The initial condition, process
noise, and measurement noise are assumed to be i.i.d. zero-mean Gaussians:
$x_{0}\sim{}\mathcal{N}(0,\Sigma_{0})$,
$w_{t}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,\Sigma_{w})$,
$v_{t}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,\Sigma_{v})$. The LTI
system is then defined by the following equations:

$\displaystyle x_{t+1}$ $\displaystyle=Ax_{t}+w_{t},$ (8) $\displaystyle
y_{t}$ $\displaystyle=Cx_{t}+v_{t}.$

Finite horizon state estimation determines an estimate for the state of the
system at time $k$ given some sequence of measurements $y_{0},\dots,y_{N}$.
This problem encompasses smoothing ($k<N$), filtering ($k=N$), and prediction
($k>N$). When the measurement and process noise satisfy the assumptions above,
the optimal state estimator is the celebrated Kalman Filter (or
smoother/predictor), which produces state estimates that are a linear function
of the observations. Therefore, the optimal estimate $\hat{x}_{k}$ of the
state $x_{k}$ at time $k$ can be written as111We note that state-space
representations for the Kalman Filter (see Appendix B) also exist Hassibi et
al. (1999), but for our purposes it is more convenient to view it as a linear
map. $\hat{x}_{k}:=LY_{N}$, where $L\in\mathbb{R}^{n\times p(N+1)}$ is some
matrix and $Y_{N}$ is a vector of stacked observations

$Y_{N}:=\begin{bmatrix}y_{0}\\\ \vdots\\\
y_{N}\end{bmatrix}\in\mathbb{R}^{p(N+1)}.$

We similarly define the stacked process and measurement noise vectors as

$W_{N}:=\begin{bmatrix}w_{0}\\\ \vdots\\\
w_{N-1}\end{bmatrix}\in\mathbb{R}^{nN}\mbox{ and
}V_{N}:=\begin{bmatrix}v_{0}\\\ \vdots\\\
v_{N}\end{bmatrix}\in\mathbb{R}^{p(N+1)}.$

Furthermore, suppose $k\leq N$ and let

$\displaystyle\mathcal{O}_{N}$ $\displaystyle=\begin{bmatrix}C\\\ CA\\\
\vdots\\\ CA^{N}\end{bmatrix}\in\mathbb{R}^{p(N+1)\times
n},\quad\tau_{N}=\begin{bmatrix}0&&&&\\\ C&0&&\\\ CA&C&&&\\\
\vdots&&\ddots&0&\\\
CA^{N-1}&\ldots&&C&0\end{bmatrix}\in\mathbb{R}^{p(N+1)\times nN},$
$\displaystyle\Gamma_{k}$
$\displaystyle=\begin{bmatrix}A^{k-1}&A^{k-2}&\ldots&I&0&\ldots&0\end{bmatrix}\in\mathbb{R}^{n\times
n(N+1)}$

so that $Y_{N}=\mathcal{O}_{N}x_{0}+\tau_{N}W_{N}$ and
$x_{k}=A^{k}x_{0}+\Gamma_{k}W_{N}$. Here $\mathcal{O}_{N}$ is the $N$-step
observability matrix, which is a quantity of interest in our analysis.

We now introduce some background on the observability of a LTI system and its
implications on state estimation.

######  Definition 3.1.

The LTI system (8) is observable if when the disturbances are zero, i.e.
$v_{t}=0$ and $w_{t}=0$ for all $t\geq 0$, it is possible to recover the
initial state $x_{0}$ from a sequence of $n$ measurements $y_{0},y_{1},\dots
y_{n-1}$.

######  Lemma 3.1.

A system of the form (8) is _observable_ if and only if the observability
matrix $\mathcal{O}_{n-1}$ has rank $n$.

Throughout the remainder of the paper we make the following assumption:

######  Assumption 3.1.

The LTI system (8) is observable and $N\geq n-1$.

As stated, observability is a binary notion that determines whether state
consistent estimation is possible. However, observability does not capture the
conditioning of the linear inverse problem defining the Kalman Filter. A more
refined, non-binary notion of observability can be defined in terms of the
_observability gramian_ of a system.

######  Definition 3.2.

The _$N$ -step observability gramian_ is defined as
$W_{o}(N):=\mathcal{O}_{N}^{\top}\mathcal{O}_{N}$. If the spectral radius of
$A$ is less than one, then taking the limit as $N\to\infty$ results in the
_observability gramian_
$W_{o}(\infty)=\sum_{t=0}^{\infty}\left(A^{t}\right)^{\top}C^{\top}CA^{t}$.

######  Lemma 3.2.

An LTI system (8) is observable if and only if $W_{o}(\infty)$ is positive
definite.

The observability gramian provides significantly more information about the
difficulty of state estimation than the rank condition of Lemma 3.1. In
particular, the ellipsoid $\left\\{x\,|\,x^{\top}W_{o}(\infty)x\leq
1\right\\}$ contains the initial states $x$ that lead to measurement signals
with $\ell^{2}$ norm bounded by $1$ in the absense of process and measurement
noise. In particular, letting $x_{0}=x$, we have
$x_{0}^{\top}W_{o}(\infty)x_{0}=\sum_{t=0}^{\infty}x_{0}^{\top}\left(A^{t}\right)^{\top}C^{\top}CA^{t}x_{0}=\sum_{t=0}^{\infty}x_{t}^{\top}C^{\top}Cx_{t}=\sum_{t=0}^{\infty}\left\|y_{t}\right\|_{2}^{2}$.
As such, small singular values of the observability gramian imply that a large
subset of the state space leads to relatively small impacts on future
measurements. This makes it difficult to use measurements to distinguish
states in this region in the presence of process and measurement noise, as
high-gain estimators are required.

###  3.2 Kalman Filtering and Smoothing

We begin by reviewing relevant results from standard Kalman Filtering and
Smoothing. We make the following simplifying assumption for presentation
purposes going forward.

######  Assumption 3.2.

$\Sigma_{0}=\sigma_{0}^{2}I$, $\Sigma_{w}=\sigma_{w}^{2}I$,
$\Sigma_{v}=\sigma_{v}^{2}I$. We further assume that the system matrix $A=\rho
Q$, $\rho\in\mathbb{R}$ is a scaled orthogonal matrix, such that $\rho$
controls the stability of the system.

A generalization of our subsequent results to generic dynamics $A$ and
positive definite covariance matrices can be found in Appendix C: although
more notationally cumbersome and difficult to interpret, they nevertheless
convey the same overall trends.

#### Standard State Estimation

Under Assumption 3.2, we define the minimum mean square estimator for the
state $x_{k}$ as

$\displaystyle\hat{L}_{k}=\operatorname*{argmin}_{L\in\mathbb{R}^{n\times
p(N+1)}}\mathbb{E}\left[\left\|x_{k}-LY_{N}\right\|_{2}^{2}\right].$ (9)

We note that the optimal solution to this problem is precisely the Kalman
Filter ($k=N$) or Smoother ($k<N$). We explicitly solve for the minimum mean
square estimator $\hat{L}_{k}$ in the following lemma, which is standard, but
included for completeness.

######  Lemma 3.3.

Suppose $k\leq N$. The finite horizon Kalman state estimator is the solution
to optimization problem (9), and is given by

$\displaystyle\hat{L}_{k}=$
$\displaystyle\left(\sigma_{0}^{2}A^{k}\mathcal{O}_{N}^{\top}+\sigma_{w}^{2}\Gamma_{k}\tau_{N}^{\top}\right)\left(\sigma_{0}^{2}\mathcal{O}_{N}\mathcal{O}_{N}^{\top}+\sigma_{w}^{2}\tau_{N}\tau_{N}^{\top}+\sigma_{v}^{2}I\right)\operatorname{{}^{-1}}.$

#### Adversarially Robust State Estimation

We now modify the standard filtering problem (9) to allow adversarial
perturbations to enter through sensor measurements.222We choose to restrict
our attention to adversarial sensor measurements because it is a more direct
analog to the traditional adversarial robustness literature, which considers
perturbations to image data, and not to the image data-generating distribution
(Szegedy et al., 2013; Goodfellow et al., 2014; Carlini and Wagner, 2016). In
particular, for some $\varepsilon>0$, the adversarially robust state estimator
is defined by

$\displaystyle\hat{L}_{k}(\varepsilon):=\operatorname*{argmin}_{L\in\mathbb{R}^{n\times
p(N+1)}}\mathbb{E}\left[\max_{\left\|\delta\right\|_{2}\leq\varepsilon}\left\|x_{k}-L(Y_{N}+\delta)\right\|_{2}^{2}\right],$

where the assumptions on the initial condition, process disturbance and
measurement disturbance are as in Assumption 3.2.

###  3.3 Robustness-Accuracy Tradeoffs in Kalman Filtering

The Kalman state estimation problem and adversarial state estimation problems
can be viewed as standard and adversarial linear inverse problems by defining

$\displaystyle\operatorname{SR}(L)$
$\displaystyle:=\mathbb{E}\left[\left\|x_{k}-LY_{N}\right\|_{2}^{2}\right],$
$\displaystyle\operatorname{AR}(L)$
$\displaystyle:=\mathbb{E}\left[\max_{\left\|\delta\right\|_{2}\leq\varepsilon}\left\|x_{k}-L(Y_{N}+\delta)\right\|_{2}^{2}\right].$

As in §2, our goal is to characterize robustness-accuracy trade-offs for this
linear inverse problem. As previewed in §2, we show that a refined analysis
allows for the the gap $\operatorname{SR}(L)-\operatorname{AR}(L)$ to be
bounded in terms of the spectral properties of the observability gramian of
the system, establishing a natural connection to the robust control and
estimation literature (Hassibi et al., 1999; Zhou and Doyle, 1998). In
particular, our results indicate the robustness-accuracy tradeoff is more
severe for systems with “uniformly low observability,” as characterized by the
Frobenius norm of the observability gramian.

To begin, we present a closed form for the standard risk
$\operatorname{SR}(L)$.

######  Lemma 3.4.

For any $L\in\mathbb{R}^{n\times p(N+1)}$, our standard risk is

$\displaystyle\operatorname{SR}(L)=\mathbb{E}\left[\left\|x_{k}-LY_{N}\right\|_{2}^{2}\right]=\sigma_{0}^{2}\left\|A^{k}-L\mathcal{O}_{N}\right\|_{F}^{2}+\sigma_{w}^{2}\left\|\Gamma_{k}-L\tau_{N}\right\|_{F}^{2}+\sigma_{v}^{2}\left\|L\right\|_{F}^{2}.$

Lemma 3.4 makes clear that the noise terms act as a regularizer: if
$\sigma_{w}^{2}=\sigma_{v}^{2}=0$, then $\min_{L}\operatorname{SR}(L)=0$ and
is achieved by $L=A^{k}(W_{o}(N))^{-1}\mathcal{O}_{N}^{\top}$. This closed-
form expression suggests that the spectral properties of $W_{o}(N)$ may play
an important role in the robustness-accuracy tradeoffs satisfied by an LTI
system (8). We formalize this intuition next.

###  3.4 Bounding $\operatorname{AR}-\operatorname{SR}$ for State Estimation

As in §2, we do not have a closed-form for the adversarial risk. Upper and
lower bounds on the gap between the adversarial risk and standard risk,
however, still highlight the role control theoretic quantities play in
robustness-accuracy tradeoffs.

######  Lemma 3.5.

For any $L\in\mathbb{R}^{n\times p(N+1)}$, the gap between
$\operatorname{AR}(L)$ and $\operatorname{SR}(L)$ admits the following lower
bound:

$\displaystyle\operatorname{AR}(L)-\operatorname{SR}(L)\geq
2\sqrt{\frac{2}{\pi}}\frac{\varepsilon}{\sqrt{n}}\sigma_{v}\left\|L\right\|_{F}^{2}$
(10)

We now turn our attention to studying the tradeoffs enjoyed by the Kalman
Filter/Smoother $L=\hat{L}_{k}$ defined in Lemma 3.3. This choice is made
because the Kalman estimator is the optimal estimator in the nominal setting,
and is commonly used in practice. To simplify notation in the subsequent
results, we will denote
$\sigma_{\vee}^{2}=\max\left\\{\sigma_{0}^{2},\sigma_{w}^{2}\right\\}$,
$\sigma_{\wedge}^{2}=\min\left\\{\sigma_{0}^{2},\sigma_{w}^{2}\right\\}$ and

$r_{k}(\rho)=\begin{cases}k,\quad&\rho=1\\\
\frac{1-\rho^{2(k+1)}}{1-\rho^{2}},\quad&\rho\neq 1.\end{cases}$ (11)

With these definitions, we have the following theorem.

######  Theorem 3.1.

Suppose that $\hat{L}_{k}$ is the Kalman estimator from Lemma 3.3. We have the
following bound on the gap between $\operatorname{AR}$ and
$\operatorname{SR}$.

$\displaystyle\operatorname{AR}(\hat{L}_{k})$
$\displaystyle-\operatorname{SR}(\hat{L}_{k})\geq
2\sqrt{\frac{2}{\pi}}\frac{\varepsilon}{\sqrt{n}}\sigma_{v}\left\|C\right\|_{F}^{2}\left(\frac{\rho^{2k}\sigma_{0}^{2}+r_{k}(\rho)\;\sigma_{w}^{2}}{(N+1)\sigma_{\vee}^{2}\left\|W_{o}(N)\right\|_{F}+\sigma_{v}^{2}}\right)^{2}.$
(12)

We see that the lower bound increases as the Frobenius norm of the
observability gramian decreases. This indicates that as observability becomes
uniformly low, i.e., if all eigenvalues of $W_{o}(N)$ are small, then a
nominal state estimator $\hat{L}_{k}$ will have a large gap
$\operatorname{AR}(\hat{L}_{k})-\operatorname{SR}(\hat{L}_{k})$. Observe that
increasing $\sigma_{w}$ will increase the lower bound shown above when
$\sigma_{w}\leq\sigma_{0}$.

We now derive an upper bound on the gap between the standard and adversarial
risk for any given $L$. This bound follows from the upper bound in Theorem
2.1.

######  Lemma 3.6.

For any $L\in\mathbb{R}^{n\times p(N+1)}$, the following bound holds

$\displaystyle\operatorname{AR}(L)-\operatorname{SR}(L)\leq
2\varepsilon\left\|L\right\|_{2}\left\|\Sigma^{1/2}\right\|_{F}+\varepsilon^{2}\left\|L\right\|_{2}^{2}$

where $\Sigma^{1/2}$ is the symmetric square root of the covariance of
$x_{k}-LY_{N}$.

Again, we consider how this upper bound looks for the Kalman estimator
$\hat{L}_{k}$.

######  Theorem 3.2.

Suppose that $\hat{L}_{k}$ is the Kalman state estimator from Lemma 3.3. Then

$\displaystyle\operatorname{AR}(\hat{L}_{k})-\operatorname{SR}(\hat{L}_{k})$
$\displaystyle\leq\varepsilon\left(\frac{\rho^{2k}\sigma_{0}^{2}+r_{k}(\rho)\;\sigma_{w}^{2}}{\sigma_{\wedge}^{2}\lambda_{\min}(W_{o}(N))^{1/2}}\right)$
$\displaystyle\quad\times\Bigg{[}2\sqrt{n}\left(\sigma_{\vee}^{2}+\left(\frac{\sigma_{v}}{\sigma_{\wedge}^{2}\lambda_{\min}(W_{o}(N))^{1/2}}\right)^{2}\right)^{1/2}+\varepsilon\left(\frac{1}{\sigma_{\wedge}^{2}\lambda_{\min}(W_{o}(N))^{1/2}}\right)\Bigg{]}.$

Furthermore, when
$\lambda_{\min}(W_{o}(N))^{1/2}\geq\frac{\sigma_{v}}{\sigma_{\wedge}^{2}}$, we
have

$\displaystyle\operatorname{AR}(\hat{L}_{k})-\operatorname{SR}(\hat{L}_{k})$
$\displaystyle\leq\varepsilon\left(\frac{\sigma_{\wedge}^{2}\lambda_{\min}(W_{o}(N))^{1/2}}{\sigma_{\wedge}^{4}\lambda_{\min}(W_{o}(N))+\sigma_{v}^{2}}\left(\rho^{2k}\sigma_{0}^{2}+r_{k}(\rho)\;\sigma_{w}^{2}\right)\right)$
$\displaystyle\quad\times\Bigg{[}2\sqrt{n}\left(\sigma_{\vee}^{2}+\sigma_{v}^{2}\left(\frac{\sigma_{\wedge}^{2}\lambda_{\min}(W_{o}(N))^{1/2}}{\sigma_{\wedge}^{4}\lambda_{\min}(W_{o}(N))+\sigma_{v}^{2}}\right)^{2}\right)^{1/2}$
$\displaystyle\quad\quad\quad+\varepsilon\left(\frac{\sigma_{\wedge}^{2}\lambda_{\min}(W_{o}(N))^{1/2}}{\sigma_{\wedge}^{4}\lambda_{\min}(W_{o}(N))+\sigma_{v}^{2}}\right)\Bigg{]}.$

The upper bound on the gap decreases as the minimum eigenvalue of the
observability gramian increases. This indicates that as the observability of
the system becomes uniformly large, the gap between standard and adversarial
risk for the nominal Kalman estimator will decrease. Perhaps counter-
intuitively, when observability is poor in some direction, i.e. when
$\lambda_{\min}\left(W_{o}(N)\right)$ is small, increasing the sensor noise
$\sigma_{v}$ will actually _decrease_ the above upper bound, as long as
$\lambda_{\min}\left(W_{o}(N)\right)\geq\frac{\sigma_{v}}{\sigma_{\wedge}^{2}}$.
This aligns with results demonstrating that injecting artificial noise can
improve the robustness of state observers (Doyle and Stein, 1979), and is
further consistent with our interpretation of noise as a regularizer following
Lemma 3.4.

##  4 Numerical Results

Figure 2: Approximation of Pareto boundaries of
$(\operatorname{SR},\operatorname{AR})$ arising in the general linear inverse
problem for random normalized matrices of different condition numbers,
$\kappa$. As the condition number increases, the tradeoff becomes more severe.

(a)

(b)

Figure 3: Pareto boundaries of $(\operatorname{SR},\operatorname{AR})$ for
initial and final state estimation. The observability of a the system is
determined by $\alpha$. When $\alpha$ approaches one, observability decreases
and the tradeoff between $\operatorname{SR}$ and $\operatorname{AR}$ becomes
more severe.

We now demonstrate that the theoretical results shown in the previous two
sections predict the tradeoffs arising in linear inverse problems.

Figure 4: $\operatorname{SR}$ vs $\operatorname{AR}$ for a nominal Kalman
smoother and an adversarially robust smoother, where observability of the
underlying system increases in the direction of the arrows. For any fixed
value of the standard risk, the adversarially robust smoother achieves a lower
adversarial risk than the nominal smoother. On the right side of the plot,
when observability is low, the adversarial risk of the adversarially robust
smoother is much lower than that of the nomimal smoother. This difference
shrinks as we move to the left and observability increases.

#### Adversarial Linear Inverse Problems

In Figure 2, we approximate the $(\operatorname{SR},\operatorname{AR})$ Pareto
boundary for a linear inverse problem, where $A_{\star}\in\mathbb{R}^{4\times
4}$ is generated randomly by multiplying a prescribed positive diagonal matrix
on the left and right by random orthogonal matrices, such that it has
condition number $1$, $3$, or $10$. The positive diagonal matrices are
normalized to have $\ell^{2}$ norm $1$ such that the resulting $A_{\star}$ all
have the same Frobenius norm, regardless of their condition number. We also
set $\Sigma_{x}=I$, $\Sigma_{w}=0.1I$, and provide the adversary a budget of
$\varepsilon=0.5$. We see that the severity of the tradeoff depends on the
condition number of the nominal solution $A_{\star}$.

#### Pareto Curves for Adversarial Kalman Filtering

In this experiment we compute the Pareto-optimal frontier for adversarially
robust Kalman filtering on systems with varying observability. We consider the
system defined by the tuple
$\left(A,C,\Sigma_{0},\Sigma_{w},\Sigma_{v},N\right)=\left(\begin{bmatrix}\alpha&\beta\\\
-\beta&\alpha\end{bmatrix},\begin{bmatrix}1&0\end{bmatrix},I,0.1I,0.1,5\right)$
where $\alpha^{2}+\beta^{2}=1$, and we vary $\alpha$. As $\alpha$ approaches
one the minimum eigenvalues of the observability gramian become small. In
particular, for $\alpha=0.95$, $\alpha=0.98$, $\alpha=0.99$, the minimum
eigenvalues of the observability gramian are given by $1.22,0.81$ and $0.58$
respectively. The adversarial budget is set to $\varepsilon=0.5$. Figure 3
shows the resulting tradeoff curves which demonstrate that as observability
decreases, both $\operatorname{SR}$ and $\operatorname{AR}$ increase, as do
the distance between the extremes of the Pareto curve. The results therefore
support §3.4, where we showed shrinking the eigenvalues of $W_{o}(N)$
increases the severity of the tradeoff between $\operatorname{SR}$ and
$\operatorname{AR}$.

#### Tradeoffs of Kalman Smoother versus Adversarially Robust Kalman Smoother

In Figure 4, we demonstrate the impact of adversaries on the risk incurred by
an estimator optimized for $\operatorname{SR}$ versus $\operatorname{AR}$. We
consider initial state estimation of a system defined by the tuple
$(A,C,\Sigma_{0},\Sigma_{w},\Sigma_{v},N)=\left(\begin{bmatrix}1&\rho\\\
0&1\end{bmatrix},\begin{bmatrix}1&0\end{bmatrix},I,0.1I,0.1,5\right)$, where
we vary $\rho$ from $0.1$ to $\sqrt{10}$, such that the eigenvalues of
$W_{o}(N)$ increase as $\rho$ increases. The adversarial budget is fixed at
$\varepsilon=0.5$. Evaluating the nominal and robust estimators on this class
of systems, we see that the adversarially robust smoother has significantly
smaller adversarial risk compared to the nominal Kalman smoother when
observability is low. As observability increases, this advantage shrinks. This
suggests that considering the tradeoffs from adversarially robust state
estimation is most important when observability is low.

#### Tradeoffs with Nonlinear State Estimators

In Figure 5, we demonstrate empirically that the fundamental tradeoffs are not
overcome by using nonlinear state estimators. In particular, we consider the
system defined by
$(A,\Sigma_{0},\Sigma_{w},\Sigma_{v},N)=\left(\begin{bmatrix}1&1\\\
0&1\end{bmatrix},I,0.1I,0.1,5\right)$, and $C$ as in the legend of the plots.
We set the adversarial budget to $\epsilon=0.5$. We solve for the Pareto
boundary for the linear estimator as in Figure 3. We also consider a two layer
network with ten neurons per layer and ReLU activation functions. To train
this network, we perform an SGD procedure similar to that used in the linear
case, with the exception being that we do not solve the exact adversary
corresponding to each data point, but rather apply 100 steps of gradient
ascent to find the adversarial perturbation. Once the neural network is
trained, this same approach to find the adversary is used again to estimate
the adversarial risk of the resultant estimator. As a result, the tradeoff
curves shown for the neural network are an under approximation to the true
values of $\operatorname{AR}$ achieved . As such, it appears that the neural
network is getting roughly the same tradeoff curves as the linear estimator,
suggesting that linear estimators may be optimal for minimizing the
adversarial risk.

(a)

(b)

Figure 5: Pareto boundaries of $(\operatorname{SR},\operatorname{AR})$ for
initial state estimation for a variety of measurement matrices $C$ by both a
linear state estimator and a neural network (Lower bound on
$\operatorname{AR}$ plotted for NN). As the first entry of $C$ decreases, the
tradeoff curve becomes more severe. The trade-offs are not alleviated by a
nonlinear estimator.

##  5 Conclusion

We analyzed the robustness-accuracy tradeoffs arising in linear inverse
problems. We did this in two parts. We first provided an algorithm to solve
for the optimal adversarial perturbation, which can be used to trace out the
Pareto boundary. We then bounded the gap between the adversarial and standard
risk in terms of the spectral properties of the underlying linear model. These
bounds generalize the robustness-accuracy tradeoffs arising in the
classification and linear regression settings. We then specialized these
general results to study the tradeoffs arising in adversarial Kalman Filtering
for linear systems, where we demonstrated that the accuracy decrease of the
nominal Kalman estimator under adversarial measurements can be bounded by the
eigenvalues of the observability gramian, a control-theoretic object. An
interesting avenue of future work is to have an analytic characterization of
the solutions $A_{\lambda}$ along the Pareto boundary of the linear inverse
problem, such that we can not only bound the fragility of the nominal
solution, but also the conservatism of adversarially robust solutions. On the
control side, we pave the way for numerous avenues for future work including
the analysis of robustness-performance tradeoffs in LQR control. It would also
be interesting to study the tradeoffs arising in estimation from an infinite
horizon perspective.

## Acknowledgements

Bruce Lee is supported by the Department of Defense through the National
Defense Science & Engineering Graduate Fellowship Program. The research of
Hamed Hassani is supported by NSF Grants 1837253, 1943064, 1934876, AFOSR
Grant FA9550-20-1-0111, and DCIST-CRA. Nikolai Matni is funded by NSF awards
CPS-2038873, CAREER award ECCS-2045834, and a Google Research Scholar award.

## References

  * Al Makdah et al. (2020) A. A. Al Makdah, V. Katewa, and F. Pasqualetti.  Accuracy prevents robustness in perception-based control.  In _2020 American Control Conference (ACC)_ , pages 3940–3946. IEEE, 2020.
  * Bottou et al. (2018) L. Bottou, F. E. Curtis, and J. Nocedal.  Optimization methods for large-scale machine learning.  _SIAM Review_ , 60(2):223–311, 2018.  doi: 10.1137/16M1080173.  URL https://doi.org/10.1137/16M1080173.
  * Boyd and Vandenberghe (2004) S. P. Boyd and L. Vandenberghe.  _Convex optimization_.  Cambridge university press, 2004.
  * Candes and Tao (2005) E. J. Candes and T. Tao.  Decoding by linear programming.  _IEEE transactions on information theory_ , 51(12):4203–4215, 2005.
  * Carlini and Wagner (2016) N. Carlini and D. Wagner.  Defensive distillation is not robust to adversarial examples.  _arXiv preprint arXiv:1607.04311_ , 2016.
  * Carlini and Wagner (2017) N. Carlini and D. Wagner.  Towards evaluating the robustness of neural networks.  In _2017 IEEE symposium on security and privacy_ , pages 39–57. IEEE, 2017.
  * Carrasco et al. (2007) M. Carrasco, J.-P. Florens, and E. Renault.  Linear inverse problems in structural econometrics estimation based on spectral decomposition and regularization.  _Handbook of econometrics_ , 6:5633–5751, 2007.
  * Chen et al. (2020) L. Chen, Y. Min, M. Zhang, and A. Karbasi.  More data can expand the generalization gap between adversarially robust and standard models.  In _International Conference on Machine Learning_ , pages 1670–1680. PMLR, 2020.
  * Deka et al. (2020) S. A. Deka, D. M. Stipanović, and C. J. Tomlin.  Dynamically computing adversarial perturbations for recurrent neural networks.  _arXiv preprint arXiv:2009.02874_ , 2020.
  * Dobriban et al. (2020) E. Dobriban, H. Hassani, D. Hong, and A. Robey.  Provable tradeoffs in adversarially robust classification.  _arXiv preprint arXiv:2006.05161_ , 2020.
  * Doyle and Stein (1979) J. Doyle and G. Stein.  Robustness with observers.  _IEEE Transactions on Automatic Control_ , 24(4):607–611, 1979.  doi: 10.1109/TAC.1979.1102095.
  * Engl et al. (2009) H. W. Engl, C. Flamm, P. Kügler, J. Lu, S. Müller, and P. Schuster.  Inverse problems in systems biology.  _Inverse Problems_ , 25(12):123014, 2009.
  * Goodfellow et al. (2014) I. J. Goodfellow, J. Shlens, and C. Szegedy.  Explaining and harnessing adversarial examples.  _arXiv preprint arXiv:1412.6572_ , 2014.
  * Hassibi et al. (1999) B. Hassibi, T. Kailath, and A. H. Sayed.  _Indefinite-quadratic estimation and control: a unified approach to H $2$ and H$\infty$ theories_.  SIAM studies in applied and numerical mathematics, 1999.
  * Huang et al. (2017) S. Huang, N. Papernot, I. Goodfellow, Y. Duan, and P. Abbeel.  Adversarial attacks on neural network policies.  _arXiv preprint arXiv:1702.02284_ , 2017.
  * Javanmard et al. (2020) A. Javanmard, M. Soltanolkotabi, and H. Hassani.  Precise tradeoffs in adversarial training for linear regression.  In _Conference on Learning Theory_ , pages 2034–2078. PMLR, 2020\.
  * Khargonekar et al. (1996) P. P. Khargonekar, M. A. Rotea, and E. Baeyens.  Mixed H2/H$\infty$ filtering.  _International Journal of Robust and Nonlinear Control_ , 6(4):313–330, 1996.
  * Lutter et al. (2021) M. Lutter, S. Mannor, J. Peters, D. Fox, and A. Garg.  Robust value iteration for continuous control tasks.  _arXiv preprint arXiv:2105.12189_ , 2021.
  * Madry et al. (2017) A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_ , 2017.
  * Mandlekar et al. (2017) A. Mandlekar, Y. Zhu, A. Garg, L. Fei-Fei, and S. Savarese.  Adversarially robust policy learning: Active construction of physically-plausible perturbations.  In _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 3932–3939. IEEE, 2017.
  * Nakkiran (2019) P. Nakkiran.  Adversarial robustness may be at odds with simplicity.  _arXiv preprint arXiv:1901.00532_ , 2019.
  * Petersen et al. (2008) K. B. Petersen, M. S. Pedersen, et al.  The matrix cookbook.  _Technical University of Denmark_ , 7(15):510, 2008.
  * Pinto et al. (2017) L. Pinto, J. Davidson, R. Sukthankar, and A. Gupta.  Robust adversarial reinforcement learning.  In _International Conference on Machine Learning_ , pages 2817–2826. PMLR, 2017.
  * Raghunathan et al. (2019) A. Raghunathan, S. M. Xie, F. Yang, J. C. Duchi, and P. Liang.  Adversarial training can hurt generalization.  _arXiv preprint arXiv:1906.06032_ , 2019.
  * Recht et al. (2010) B. Recht, M. Fazel, and P. A. Parrilo.  Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization.  _SIAM review_ , 52(3):471–501, 2010.
  * Ribes and Schmitt (2008) A. Ribes and F. Schmitt.  Linear inverse problems in imaging.  _IEEE Signal Processing Magazine_ , 25(4):84–99, 2008.
  * Szegedy et al. (2013) C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus.  Intriguing properties of neural networks.  _arXiv preprint arXiv:1312.6199_ , 2013.
  * Tsipras et al. (2018) D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry.  Robustness may be at odds with accuracy.  _arXiv preprint arXiv:1805.12152_ , 2018.
  * Xie et al. (2020) C. Xie, M. Tan, B. Gong, A. Yuille, and Q. V. Le.  Smooth adversarial training.  _arXiv preprint arXiv:2006.14536_ , 2020.
  * Zhang et al. (2019) H. Zhang, Y. Yu, J. Jiao, E. P. Xing, L. E. Ghaoui, and M. I. Jordan.  Theoretically principled trade-off between robustness and accuracy.  _arXiv preprint arXiv:1901.08573_ , 2019.
  * Zhou and Doyle (1998) K. Zhou and J. C. Doyle.  _Essentials of Robust Control_.  Prentice-Hall, 1998.

##  Appendix A Proofs from Section 2

###  A.1 Proof of Correctness for Algorithm 1

Recalling the optimization problem

$\displaystyle\operatorname*{maximize}_{\delta\in\mathbb{R}^{n}}$
$\displaystyle\quad\delta^{\top}A^{\top}A\delta-2\delta^{\top}A^{\top}b$ (P)
$\displaystyle\operatorname{subject\ to}$
$\displaystyle\quad\delta^{\top}\delta\leq\varepsilon^{2},$

and the corresponding KKT conditions:

$\displaystyle 2(\lambda^{*}I-A^{\top}A)\delta^{*}+2A^{\top}b$
$\displaystyle=0$
$\displaystyle\lambda^{*}({\delta^{*}}^{\top}\delta^{*}-\varepsilon^{2})$
$\displaystyle=0$ $\displaystyle(\lambda^{*}I-A^{\top}A)$
$\displaystyle\succeq 0.$

The third condition implies that $\lambda^{*}\geq\sigma_{1}^{2}$. We assume
$\sigma_{1}>0$, otherwise the problem is trivial. Then using the SVD of $A$ to
re-arrange the first stationarity condition, we get

$\displaystyle(\lambda^{*}I-\Sigma^{\top}\Sigma)V^{\top}\delta^{*}$
$\displaystyle=\Sigma^{\top}U^{\top}b.$

Maximizing a convex function over a convex set achieves its maximum on the
boundary; it suffices to search over $\delta^{\top}\delta=\varepsilon^{2}$. We
now consider two cases: $\lambda^{*}>\sigma_{1}^{2}$ and
$\lambda^{*}=\sigma_{1}^{2}$. In the first case, we know
$\lambda^{*}I-\Sigma^{\top}\Sigma$ must be invertible, and thus

$\displaystyle\delta^{*}$
$\displaystyle=-V(\lambda^{*}I-\Sigma^{\top}\Sigma)^{-1}\Sigma^{\top}U^{\top}b$
$\displaystyle\varepsilon^{2}={\delta^{*}}^{\top}\delta^{*}$
$\displaystyle=b^{\top}U\Sigma(\lambda^{*}I-\Sigma^{\top}\Sigma)^{-2}\Sigma^{\top}U^{\top}b$
$\displaystyle=\sum_{i=1}^{\min\left\\{n,p\right\\}}\frac{(b^{\top}u_{i})^{2}\sigma_{i}^{2}}{(\lambda^{*}-\sigma_{i}^{2})^{2}},$

where $u_{i}$ are the columns of $U$. Observe that

$\displaystyle f(\lambda)$
$\displaystyle:=\sum_{i=1}^{\min\left\\{n,p\right\\}}\frac{(b^{\top}u_{i})^{2}\sigma_{i}^{2}}{(\lambda-\sigma_{i}^{2})^{2}},$

is a strictly monotonically decreasing function when $\lambda>\sigma_{1}^{2}$,
and converges to $0$ when $\lambda\to\infty$. This implies there is a unique
$\lambda^{*}$ such that $f(\lambda^{*})=\varepsilon^{2}$, which can be
numerically solved for in various ways, such as bisection.

Now we consider the case where $\lambda^{*}=\sigma_{1}^{2}$. In this case,
$\delta^{*}$ will no longer be unique, and will come in the form

$\displaystyle\delta^{*}$
$\displaystyle=-V(\sigma_{1}^{2}I-\Sigma^{\top}\Sigma)^{\dagger}\Sigma^{\top}U^{\top}b+cv,$

where † denotes the Moore-Penrose pseudoinverse, and $v$ is any unit vector
lying in the null-space of $\left(\sigma_{1}^{2}I-\Sigma^{2}\right)V^{\top}$,
which is precisely characterized in this case by

$\displaystyle\ker\left(\left(\sigma_{1}^{2}I-\Sigma^{2}\right)V^{\top}\right)$
$\displaystyle=\textbf{span}\left(\left\\{v_{i}:\sigma_{i}^{2}=\sigma_{1}^{2}\right\\}\right),$

with $v_{i}$ denoting the $i$th column of $V$. To find the appropriate scaling
$c$, we observe

$\displaystyle{\delta^{*}}^{\top}\delta^{*}$
$\displaystyle=b^{\top}U\Sigma\left((\sigma_{1}^{2}I-\Sigma^{\top}\Sigma)^{\dagger}\right)^{2}\Sigma^{\top}U^{\top}b+c^{2}$
$\displaystyle=\sum_{i:\sigma_{i}<\sigma_{1}}\frac{(b^{\top}u_{i})^{2}\sigma_{i}^{2}}{(\sigma_{1}^{2}-\sigma_{i}^{2})^{2}}=\varepsilon^{2}$
$\displaystyle c$
$\displaystyle=\sqrt{\varepsilon^{2}-\sum_{i:\sigma_{i}<\sigma_{1}}\frac{(b^{\top}u_{i})^{2}\sigma_{i}^{2}}{(\sigma_{1}^{2}-\sigma_{i}^{2})^{2}}}.$

Combining our precise characterization of
$\ker\left(\left(\sigma_{1}^{2}I-\Sigma^{\top}\Sigma\right)V^{\top}\right)$
using the columns of $V$, and the formula for $c$, we can extract an optimal
perturbation vector $\delta^{*}$. Therefore, we have demonstrated that (P), as
well as extracting its optimal solution, can be solved to arbitrary precision.

###  A.2 Proof of Theorem 2.1

First recall the definitions of SR and and AR:

$\displaystyle\operatorname{SR}(A)$
$\displaystyle=\mathbb{E}\left[\left\|y-Ax\right\|_{2}^{2}\right]$
$\displaystyle\operatorname{AR}(A)$
$\displaystyle=\mathbb{E}\left[\max_{\left\|\delta\right\|_{2}\leq\varepsilon}\left\|y-A(x+\delta)\right\|_{2}^{2}\right].$

Given fixed $y,x$, let us define the quantity $d(A):=y-Ax$. Writing out the
inner maximization of AR we have:

$\displaystyle\max_{\left\|\delta\right\|_{2}\leq\varepsilon}\left\|y-A(x+\delta)\right\|_{2}^{2}$
$\displaystyle=\max_{\left\|\delta\right\|_{2}\leq\varepsilon}\left\|d(A)-A\delta\right\|_{2}^{2}.$

Observe that this is equivalent to the problem

$\displaystyle\operatorname*{minimize}_{s}\quad$ $\displaystyle s$ (P1)
$\displaystyle\operatorname{subject\ to}\quad$ $\displaystyle
s-\left\|d(A)-A\delta\right\|_{2}^{2}\geq 0\text{ for all
}\delta^{\top}\delta\leq\varepsilon^{2}.$

We now recall the S-lemma for quadratic functions.

######  Lemma A.1 (S-lemma).

Given quadratic functions $p(x),q(x):\mathbb{R}^{n}\to\mathbb{R}$, suppose
there exists $x$ such that $p(x)>0$. Then,

$p(x)\geq 0\implies q(x)\geq 0\text{ for all }x$

if and only if

$\exists t\geq 0\text{ such that }q(x)\geq tp(x)\text{ for all }x.$

Using this lemma, we set $p(\delta)=\varepsilon^{2}-\delta^{\top}\delta$,
$q(\delta)=s-\left\|d(A)-A\delta\right\|_{2}^{2}\geq 0$. We observe that
trivially, there exists $\delta=0$ such that $p(\delta)>0$. Now given feasible
$s$ for (P1), we observe that by our constraints, any $\delta$ such that
$p(\delta)\geq 0$ immediately implies $q(\delta)\geq 0$. By the S-lemma, this
is equivalent to the existence of some $t\geq 0$ such that

$q(\delta)-tp(\delta)=s-\left\|d(A)-A\delta\right\|_{2}^{2}-t(\varepsilon^{2}-\delta^{\top}\delta)\geq
0$

for all $\delta$. Therefore, we can re-write the optimization problem (P1)
into

$\displaystyle\operatorname*{minimize}_{s}\quad$ $\displaystyle s$ (P2)
$\displaystyle\operatorname{subject\ to}\quad$ $\displaystyle\exists t\geq
0\text{ s.t.
}s-\left\|d(A)-A\delta\right\|_{2}^{2}-t(\varepsilon^{2}-\delta^{\top}\delta)\geq
0\text{ for all }\delta.$

Re-arranging the terms in the quadratic expression, we get:

$\displaystyle
s-\left\|d(A)-A\delta\right\|_{2}^{2}-t(\varepsilon^{2}-\delta^{\top}\delta)$
$\displaystyle=s-\left(\delta^{\top}A^{\top}A\delta-2d(A)^{\top}A\delta+\left\|d(A)\right\|_{2}^{2}\right)-t(\varepsilon^{2}-\delta^{\top}\delta)$
$\displaystyle=\delta^{\top}\left(tI-A^{\top}A\right)\delta+2d(A)^{\top}A\delta+\left(s-t\varepsilon^{2}-\left\|d(A)\right\|_{2}^{2}\right).$

Now we recall a property of Schur complements.

######  Lemma A.2 (Schur Complement).

Given $p(x)=x^{\top}Px+b^{\top}x+c$, we have

$\displaystyle p(x)\geq 0\;\forall\;x$ $\displaystyle\iff\begin{bmatrix}P&b\\\
b^{\top}&c\end{bmatrix}\succeq 0$ $\displaystyle\iff P\succeq
0,\;c-b^{\top}P^{\dagger}b\geq 0.$

Applying this to (P2), we see the constraints can be re-written

$\displaystyle\exists t\geq 0\text{ s.t.
}s-\left\|d(A)-A\delta\right\|_{2}^{2}-t(\varepsilon^{2}-\delta^{\top}\delta)\geq
0\text{ for all }\delta$ $\displaystyle\iff\quad$ $\displaystyle\exists t\geq
0,\;tI-A^{\top}A\succeq
0,\;s-t\varepsilon^{2}-\left\|d(A)\right\|_{2}^{2}-d(A)^{\top}A(tI-A^{\top}A)^{\dagger}A^{\top}d(A)\geq
0$ $\displaystyle\iff\quad$ $\displaystyle\exists
t\geq\lambda_{\max}(A^{\top}A),\;s-t\varepsilon^{2}-\left\|d(A)\right\|_{2}^{2}-d(A)^{\top}A(tI-A^{\top}A)^{\dagger}A^{\top}d(A)\geq
0.$

Therefore, we get the optimization problem

$\displaystyle\operatorname*{minimize}_{s,t}\quad$ $\displaystyle s$
$\displaystyle\operatorname{subject\ to}\quad$ $\displaystyle
t\geq\lambda_{\max}(A^{\top}A)$ $\displaystyle
s-t\varepsilon^{2}-\left\|d(A)\right\|_{2}^{2}-d(A)^{\top}A(tI-A^{\top}A)^{\dagger}A^{\top}d(A)\geq
0.$

However, this is clearly equivalent and has the same optimal value as the
following problem

$\displaystyle\operatorname*{minimize}_{t}\quad$ $\displaystyle
t\varepsilon^{2}+\left\|d(A)\right\|_{2}^{2}+d(A)^{\top}A(tI-A^{\top}A)^{\dagger}A^{\top}d(A)$
$\displaystyle\operatorname{subject\ to}\quad$ $\displaystyle
t\geq\lambda_{\max}(A^{\top}A).$

Notice that so far we are simply considering equivalent formulations to the
original optimization. The ensuing step is where the lower and upper bounds 6
and 7 arise. Recall the Neumann series, where since
$t\geq\lambda_{\max}(A^{\top}A)$, we have

$\displaystyle(tI-A^{\top}A)^{-1}$
$\displaystyle=\frac{1}{t}\left(I-\frac{1}{t}A^{\top}A\right)^{-1}$
$\displaystyle=\frac{1}{t}\left(I+\frac{1}{t}A^{\top}A+\frac{1}{t^{2}}\left(A^{\top}A\right)^{2}+\cdots\right).$

From the Neumann series, we see that we can upper and lower bound the inverse
using geometric series of the largest and smallest eigenvalues of $A^{\top}A$,
respectively,

$\displaystyle\frac{1}{t-\lambda_{\min}(A^{\top}A)}I\preceq(tI-A^{\top}A)^{-1}\preceq\frac{1}{t-\lambda_{\max}(A^{\top}A)}I$

From now on, we will deal with the inverse, since instead of the pseudo-
inverse we can take the infimum of the above problem, which is bounded from
below. Let us consider the lower bound first–the upper bound follows using the
exact same techniques. We have

$\displaystyle
t\varepsilon^{2}+\left\|d(A)\right\|_{2}^{2}+d(A)^{\top}A(tI-A^{\top}A)^{-1}A^{\top}d(A)$
$\displaystyle\geq
t\varepsilon^{2}+\left\|d(A)\right\|_{2}^{2}+d(A)^{\top}A\left(\frac{1}{t-\lambda_{\min}(A^{\top}A)}I\right)A^{\top}d(A)$
$\displaystyle=t\varepsilon^{2}+\left\|d(A)\right\|_{2}^{2}+\frac{1}{t-\lambda_{\min}(A^{\top}A)}\left\|A^{\top}d(A)\right\|_{2}^{2}.$

Therefore, we have

$\displaystyle\max_{\left\|\delta\right\|_{2}\leq\varepsilon}\left\|x_{k}-A(Y_{T}+\delta)\right\|_{2}^{2}$
$\displaystyle\geq\left\|d(A)\right\|_{2}^{2}+\min_{t>\lambda_{\max}(A^{\top}A)}t\varepsilon^{2}+\frac{1}{t-\lambda_{\min}(A^{\top}A)}\left\|A^{\top}d(A)\right\|_{2}^{2}.$

We now make a second relaxation:

$\displaystyle\left\|d(A)\right\|_{2}^{2}+\min_{t>\lambda_{\max}(A^{\top}A)}t\varepsilon^{2}+\frac{1}{t}\left\|A^{\top}d(A)\right\|_{2}^{2}$
$\displaystyle\geq\left\|d(A)\right\|_{2}^{2}+\min_{t\geq
0}t\varepsilon^{2}+\frac{1}{t-\lambda_{\min}(A^{\top}A)}\left\|A^{\top}d(A)\right\|_{2}^{2}$
$\displaystyle=\left\|d(A)\right\|_{2}^{2}+2\varepsilon\left\|A^{\top}d(A)\right\|_{2}+\varepsilon^{2}\lambda_{\min}(A^{\top}A),$

which we get by deriving the unconstrained minimizer
$t^{*}=\frac{\left\|A^{\top}d(A)\right\|_{2}}{\varepsilon}+\lambda_{\min}(A^{\top}A)$.
Now putting expectations on both sides of the inequality, we get

$\displaystyle\operatorname{AR}(A)$
$\displaystyle\geq\operatorname{SR}(A)+2\varepsilon\;\mathbb{E}\left[\left\|A^{\top}(x_{k}-AY_{T})\right\|_{2}\right]+\varepsilon^{2}\lambda_{\min}(A^{\top}A).$

$\blacksquare$

###  A.3 Proof of Corollary 2.2

We note that the upper and lower bounds boil down to upper and lower bounding
$\mathbb{E}\left[\left\|A_{\star}^{\top}(y-A_{\star}x)\right\|_{2}\right]$. We
first observe
$A_{\star}^{\top}(y-A_{\star}x)=A_{\star}^{\top}w\sim\mathcal{N}(0,\sigma_{w}^{2}A_{\star}^{\top}A_{\star})$.
The upper bound therefore comes from an application of Jensen’s inequality:

$\displaystyle\mathbb{E}\left[\left\|A_{\star}^{\top}w\right\|_{2}\right]$
$\displaystyle=\mathbb{E}\left[\sqrt{\left\|A_{\star}^{\top}w\right\|_{2}^{2}}\right]$
$\displaystyle\leq\sqrt{\mathbb{E}\left[\left\|A_{\star}^{\top}w\right\|^{2}_{2}\right]}$
$\displaystyle=\sqrt{\operatorname{\mathrm{tr}}\left(A_{\star}^{\top}A_{\star}\right)}.$

For the lower bound, we first consider the full SVD of $A_{\star}=U\Sigma
V^{\top}$, where $U,V$ are orthogonal matrices. Therefore, we have

$\displaystyle\left\|A^{\top}w\right\|_{2}^{2}$ $\displaystyle=\left\|\Sigma
U^{\top}w\right\|_{2}^{2}$
$\displaystyle=\sum_{i=1}^{p}\sigma_{i}^{2}w_{i}^{2}.$

Using the $\ell^{2}$-$\ell^{1}$ equivalence of norms, we have

$\displaystyle\sqrt{\sum_{i=1}\sigma_{i}^{2}w_{i}^{2}}\geq\frac{1}{\sqrt{p}}\sum_{i=1}^{p}\sigma_{i}{\left|w_{i}\right|}.$

Putting this together, we have

$\displaystyle\mathbb{E}\left[\left\|A_{\star}^{\top}w\right\|\right]$
$\displaystyle\geq\frac{1}{\sqrt{p}}\mathbb{E}\left[\sum_{i=1}^{p}\sigma_{i}{\left|w_{i}\right|}\right]=\frac{1}{\sqrt{p}}\mathbb{E}\left[{\left|w_{1}\right|}\right]\sum_{i=1}^{p}\sigma_{i},$

where $w_{1}\sim\mathcal{N}(0,1)$. The quantity
$\mathbb{E}\left[{\left|w_{1}\right|}\right]$ is the mean of a folded standard
normal, and we may express
$\sum_{i=1}^{p}\sigma_{i}=\operatorname{\mathrm{tr}}\left((A_{\star}^{\top}A_{\star})^{1/2}\right)$,
which yields us the desired lower bound. $\blacksquare$

##  Appendix B Kalman Filtering State Space Solution

Consider the setting defined in §3.1, i.e. we have a dynamical system which
progresses according to

$\displaystyle x_{t+1}$ $\displaystyle=Ax_{t}+w_{t}$ $\displaystyle y_{t}$
$\displaystyle=Cx_{t}+v_{t}$

with $x_{0}\sim{}\mathcal{N}(0,\Sigma_{0})$,
$w_{t}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,\Sigma_{w})$,
$v_{t}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,\Sigma_{v})$. Consider
estimating state $x_{k}$ given measurements $y_{0},\dots,y_{k}$. The minimum
mean square estimator is given by

$\hat{x}_{k}=\min_{z}\mathbb{E}\left[\left\|z-x_{k}\right\|_{2}^{2}|y_{0},\dots,y_{k}\right].$

This can be written as an integral

$\min_{z}\int_{\mathbb{R}^{n}}\left\|z-x_{k}\right\|_{2}^{2}f(x_{k}|y_{0},\dots,y_{k})dx_{k}$

where $f$ denotes the conditional density of $x_{k}$ given the measurements.
The objective is convex in $z$, and thus we can find the minimizer by setting
the gradient with respect to $z$ to zero. In particular, we have

$\displaystyle\frac{d}{dz}\int_{\mathbb{R}^{n}}\left\|z-x_{k}\right\|_{2}^{2}f(x_{k}|y_{0},\dots,y_{k})$
$\displaystyle=\int_{\mathbb{R}^{n}}\frac{d}{dz}\left\|z-x_{k}\right\|_{2}^{2}f(x_{k}|y_{0},\dots,y_{k})dx_{k}$
$\displaystyle=\int_{\mathbb{R}^{n}}2(z-x_{k})f(x_{k}|y_{0},\dots,y_{k})dx_{k}$
$\displaystyle=0$

where dominated convergence theorem permits the exchange of integration and
differentiation. Therefore, the state estimate may be expressed

$\hat{x}_{k}=\int_{\mathbb{R}^{n}}x_{k}f(x_{k}|y_{0},\dots,y_{k})dx_{k}=\mathbb{E}\left[x_{k}|y_{0},\dots
y_{k}\right].$

Thus we can determine the state estimates $\hat{x}_{k}$ as the mean of the
conditional distribution $f(x_{k}|y_{0},\dots y_{k})$. This may be computed
recursively. In particular, let $x_{k}|y_{0:k}$ be the random variable with
probability density function $f(x_{k}|y_{0},\dots y_{k})$. Then for all $k$,
we have that $x_{k}|y_{0:k}=\mathcal{N}(\hat{x}_{k}^{+},P_{k}^{+})$ where

$\displaystyle x_{0}^{-}$ $\displaystyle=0$ (13) $\displaystyle P_{0}^{-}$
$\displaystyle=\Sigma_{0}$ $\displaystyle\hat{x}_{k}^{+}$
$\displaystyle=x_{k}^{-}+P_{k}^{-}C^{\top}\left(CP_{k}^{-}C^{\top}+\Sigma_{v}\right)^{-1}\left(y_{k}-C\hat{x}_{k}^{-}\right)$
$\displaystyle P_{k}^{+}$
$\displaystyle=P_{k}^{-}-P_{k}^{-}C^{\top}\left(CP_{k}^{-}C^{\top}+\Sigma_{v}\right)CP_{k}^{-}$
$\displaystyle\hat{x}_{k+1}^{-}$ $\displaystyle=A\hat{x}_{k}^{+}$
$\displaystyle P_{k+1}^{-}$ $\displaystyle=A^{\top}P_{k}^{+}A+\Sigma_{w}$

To see that this is the case, recall that
$x_{0}\sim\mathcal{N}(0,\Sigma_{0})$, by assumption. Now suppose that
$x_{k}|y_{0:k-1}\sim\mathcal{N}(\hat{x}_{k}^{-},P_{k}^{-})$. Observe that

$\begin{bmatrix}x_{k}|y_{0:k-1}\\\
y_{k}\end{bmatrix}\sim\mathcal{N}\left(\begin{bmatrix}\hat{x}_{k}^{-}\\\
C\hat{x}_{k}^{-}\end{bmatrix},\begin{bmatrix}P_{k}^{-}&P_{k}^{-}C^{\top}\\\
CP_{k}^{-}&CP_{k}^{-}C^{\top}+\Sigma_{v}\end{bmatrix}\right)$

Thus

$\displaystyle x_{k}|y_{0:k}$
$\displaystyle\sim\mathcal{N}\left(x_{k}^{-}+P_{k}^{-}C^{\top}\left(CP_{k}^{-}C^{\top}+\Sigma_{v}\right)^{-1}\left(y_{k}-C\hat{x}_{k}^{-}\right),P_{k}^{-}-P_{k}^{-}C^{\top}\left(CP_{k}^{-}C^{\top}+\Sigma_{v}\right)CP_{k}^{-}\right)$
$\displaystyle=\mathcal{N}(x_{k}^{+},P_{k}^{+})$

Now, given $x_{k}|y_{0:k}\sim\mathcal{N}(x_{k}^{+},P_{k}^{+})$, observe that
$x_{k+1}|y_{0:k}=Ax_{k}|y_{0:k}+w_{k}\sim\mathcal{N}(A^{\top}x_{k}^{+},A^{\top}P_{k}^{+}A+\Sigma_{w})=\mathcal{N}(x_{k+1}^{-},P_{k}^{-})$.

Using the equations in (13), we can write the Kalman filter as a state space
system with inputs $y_{t}$. In particular, if $P_{k}^{-}$ and $P_{k}^{+}$ are
defined as in (13), we can let
$K_{k}=P_{k}^{-}C^{\top}\left(CP_{k}^{-}C^{\top}+\Sigma_{v}\right)^{-1}$. Then
we may express our state estimates using the following time varying system.

$\displaystyle\hat{x}_{k+1}$
$\displaystyle=(A-K_{k}CA)\hat{x}_{k}+K_{k}y_{k}.$

##  Appendix C General Statements and Proofs from Section 3

###  C.1 Lemma 3.3

Lemma 3.3: Suppose $k\leq N$. The finite horizon Kalman state estimator is the
solution to optimization problem (9), and is given by

$\displaystyle\hat{L}_{k}$
$\displaystyle=\left(A^{k}\Sigma_{0}\mathcal{O}_{N}\operatorname{{}^{\top}}+\Gamma_{k}\Sigma_{w}\tau_{N}\operatorname{{}^{\top}}\right)\left(\mathcal{O}_{N}\Sigma_{0}\mathcal{O}_{N}\operatorname{{}^{\top}}+\tau_{N}\left(I_{N}\otimes\Sigma_{w}\right)\tau_{N}\operatorname{{}^{\top}}+\left(I_{N+1}\otimes\Sigma_{v}\right)\right)^{-1}.$

Proof: We know $\operatorname{SR}(L)$ is convex in $L$, thus we may take the
derivative of $\operatorname{SR}(L)$ with respect to $L$ and set it to $0$ to
solve for $\hat{L}_{k}$. Matrix derivatives can be found in Petersen et al.
(2008).

###  C.2 Proof of Lemma 3.4

Proof: This follows simply by expanding the norm inside the expectation, and
noticing that since $x_{0}$, $W_{N}$, $V_{N}$ are defined to be zero-mean
Gaussian random vectors, their cross terms vanish. More precisely, we have

$\displaystyle\mathbb{E}\left[\left\|x_{k}-LY_{N}\right\|_{2}^{2}\right]$
$\displaystyle=\mathbb{E}\left[\operatorname{\mathrm{tr}}\left((x_{k}-LY_{N})(x_{k}-LY_{N})^{\top}\right)\right]$
$\displaystyle=\mathbb{E}\bigg{[}\operatorname{\mathrm{tr}}\bigg{(}\left(A^{k}-L\mathcal{O}_{N}\right)x_{0}x_{0}^{\top}\left(A^{k}-L\mathcal{O}_{N}\right)^{\top}+\left(\Gamma_{k}-L\tau_{N}\right)W_{N}W_{N}^{\top}(\Gamma_{k}-L\tau_{N})^{\top}$
$\displaystyle\quad+LV_{N}V_{N}^{\top}L^{\top}\bigg{)}\bigg{]}+0$
$\displaystyle=\left\|\left(A^{k}-L\mathcal{O}_{N}\right)\Sigma_{0}^{1/2}\right\|_{F}^{2}+\left\|\left(\Gamma_{k}-L\tau_{N}\right)\left(I_{N}\otimes\Sigma_{w}\right)^{1/2}\right\|_{F}^{2}+\left\|L\left(I_{N+1}\otimes\Sigma_{v}\right)^{1/2}\right\|_{F}^{2}.$

$\blacksquare$

###  C.3 Lemma 3.5

Lemma 3.5.  _For any $L\in\mathbb{R}^{n\times p(N+1)}$, the gap between
$\operatorname{AR}(L)$ and $\operatorname{SR}(L)$ admits the following lower
bound:_

$\displaystyle\operatorname{AR}(L)-\operatorname{SR}(L)$ $\displaystyle\geq
2\sqrt{\frac{2}{\pi}}\frac{\varepsilon}{\sqrt{n}}\operatorname{\mathrm{tr}}\bigg{(}\bigg{(}L^{\top}\Big{(}S\Sigma_{0}S^{\top}+T\left(I_{N}\otimes\Sigma_{w}\right)T^{\top}+L\left(I_{N+1}\otimes\Sigma_{v}\right)L^{\top}\Big{)}L\bigg{)}^{1/2}\bigg{)}$
$\displaystyle\geq
2\sqrt{\frac{2}{\pi}}\frac{\varepsilon}{\sqrt{n}}\sigma_{\min}(\Sigma_{v})^{1/2}\left\|L\right\|_{F}^{2}$
(14)

_where $S:=A^{k}-L\mathcal{O}_{N}$, $T:=\Gamma_{k}-L\tau_{N}$. _

Proof: Applying the lower bound (6), we have

$\displaystyle\operatorname{AR}(L)$
$\displaystyle\geq\operatorname{SR}(L)+2\varepsilon\;\mathbb{E}\left[\left\|L^{\top}(x_{k}-LY_{T})\right\|_{2}\right].$

Then to derive the lower bound (C.3), we observe that the random vector

$\displaystyle z$ $\displaystyle=L^{\top}(x_{k}-LY_{T})$
$\displaystyle=L^{\top}\left(Sx_{0}-TW_{T}+LV_{T})\right),$

is a zero-mean gaussian with covariance

$\displaystyle\Sigma$
$\displaystyle=L^{\top}\left(S\Sigma_{0}S^{\top}+T\Sigma_{w}T^{\top}+L\Sigma_{v}L^{\top}\right)L.$

We can also write $z=\Sigma^{1/2}w$ where $w\sim\mathcal{N}(0,I)$. Consider
the diagonalization of $\Sigma^{1/2}=VSV^{\top}$. Then

$\displaystyle\mathbb{E}\left[\left\|z\right\|_{2}\right]$
$\displaystyle=\mathbb{E}\left[\left\|VSV^{\top}w\right\|_{2}\right]$
$\displaystyle=\mathbb{E}\left[\left\|\sum_{i}s_{i}w_{i}v_{i}\right\|_{2}\right],$

where $v_{i}$ is the $i$th row of $V$ and $s_{i}$ is the $i$th singular value
of $\Sigma^{1/2}$. We have that

$\displaystyle\left\|\sum_{i}s_{i}w_{i}v_{i}\right\|_{2}^{2}=\sum_{i}s_{i}^{2}w_{i}^{2}v_{i}^{\top}v_{i}=\sum_{i}s_{i}^{2}w_{i}^{2}$

We have by equivalence of norms, $\sqrt{\sum_{i=1}^{n}x_{i}^{2}}\geq
n^{-1/2}\sum_{i=1}^{n}{\left|x_{i}\right|}$. Therefore,

$\displaystyle\sqrt{\sum_{i=1}^{n}s_{i}^{2}w_{i}^{2}}\geq\frac{1}{\sqrt{n}}\sum_{i=1}^{n}s_{i}{\left|w_{i}\right|},$

and thus

$\displaystyle\mathbb{E}\left[\left\|z\right\|_{2}\right]$
$\displaystyle\geq\frac{1}{\sqrt{n}}\mathbb{E}\left[\sum_{i=1}^{n}s_{i}|w|_{i}\right]=\frac{1}{\sqrt{n}}\mathbb{E}\left[{\left|w\right|}\right]\sum_{i=1}^{n}s_{i}$

where $w\sim\mathcal{N}(0,1)$. The quantity
$\mathbb{E}\left[{\left|w\right|}\right]$ is the expected value of a folded
standard normal, which is $\sqrt{\frac{2}{\pi}}$, while
$\sum_{i=1}^{n}s_{i}=\operatorname{\mathrm{tr}}\left(\Sigma^{1/2}\right)$.
Putting this together, we have that

$\displaystyle\operatorname{AR}(L)-\operatorname{SR}(L)$ $\displaystyle\geq
2\sqrt{\frac{2}{\pi}}\frac{\varepsilon}{\sqrt{n}}\operatorname{\mathrm{tr}}\bigg{(}\bigg{(}L^{\top}\Big{(}S\Sigma_{0}S^{\top}+T\left(I_{N}\otimes\Sigma_{w}\right)T^{\top}+L\left(I_{N+1}\otimes\Sigma_{v}\right)L^{\top}\Big{)}L\bigg{)}^{1/2}\bigg{)}.$

From the above bound, we may now derive a cruder lower bound from which we can
observe a dependence on the singular values of the observability grammian,
$W_{o}(N)$. In particular, begin with the expression above, and note that the
terms involving $\Sigma_{0}$ and $\Sigma_{w}$ are positive definite to achieve
a lower bound in terms of $L$:

$\displaystyle
2\sqrt{\frac{2}{\pi}}\frac{\varepsilon}{\sqrt{n}}\operatorname{\mathrm{tr}}\left(\left(L\operatorname{{}^{\top}}\left(S\Sigma_{0}S\operatorname{{}^{\top}}+T\left(I_{N}\otimes\Sigma_{w}\right)T\operatorname{{}^{\top}}+L\left(I_{N+1}\otimes\Sigma_{v}\right)L\operatorname{{}^{\top}}\right)L\right)^{1/2}\right)$
$\displaystyle\geq\;$ $\displaystyle
2\sqrt{\frac{2}{\pi}}\frac{\varepsilon}{\sqrt{n}}\sigma_{\min}\left(\Sigma_{v}\right)^{1/2}\operatorname{\mathrm{tr}}\left(\left(L\operatorname{{}^{\top}}LL\operatorname{{}^{\top}}L\right)^{1/2}\right)$
$\displaystyle=\;$ $\displaystyle
2\sqrt{\frac{2}{\pi}}\frac{\varepsilon}{\sqrt{n}}\sigma_{\min}\left(\Sigma_{v}\right)^{1/2}\left\|L\right\|_{F}^{2}.$

which completes the proof of inequality (C.3). $\blacksquare$

Introducing additional notation to express the Kalman estimator will be
helpful in subsequent sections. Let

$\displaystyle\bar{\Sigma}$ $\displaystyle:=\begin{bmatrix}\Sigma_{0}&\\\
&I_{N}\otimes\Sigma_{w}\end{bmatrix}$ (15) $\displaystyle H$
$\displaystyle:=\begin{bmatrix}I&&&&\\\ A&I&&&\\\ \vdots&&\ddots&&\\\
A^{N}&A^{N-1}&\ldots&I\end{bmatrix}\bar{\Sigma}^{1/2}$ $\displaystyle H_{k}$
$\displaystyle:=E_{k}^{\top}H=\begin{bmatrix}A^{k}&A^{k-1}&\dots&I&0&\dots&0\end{bmatrix}\bar{\Sigma}^{1/2}$
$\displaystyle M$ $\displaystyle:=H^{\top}\left(C^{\top}\otimes
I\right)=\bar{\Sigma}^{1/2}\begin{bmatrix}\mathcal{O}_{N}^{\top}\\\
\left(\mathcal{Z}\mathcal{O}_{N}\right)^{\top}\\\ \vdots\\\
\left(\mathcal{Z}^{N}\mathcal{O}_{N}\right)^{\top}\end{bmatrix},$

where $\mathcal{Z}\in\mathbb{R}^{p(N+1)\times p(N+1)}$ is a block downshift
operator, with blocks of size $m$. With this notation, the Kalman estimator
given in Lemma 3.3 may be rewritten more compactly as

$\hat{L}_{k}=H_{k}M\left(M^{\top}M+\Sigma_{v}\right)^{-1}.$

###  C.4 Theorem 3.1

Theorem 3.1.  _Suppose that $\hat{L}_{k}$ is the Kalman estimator from Lemma
3.3. Then we have the following bound on the gap between $\operatorname{AR}$
and $\operatorname{SR}$._

$\displaystyle\operatorname{AR}(\hat{L}_{k})-\operatorname{SR}(\hat{L}_{k})\geq
2\sqrt{\frac{2}{\pi}}\frac{\varepsilon}{\sqrt{n}}\sigma_{\min}\left(\Sigma_{v}\right)\left\|C\right\|_{F}^{2}\left(\frac{\sigma_{\min}\left(A^{k}\Sigma_{0}{A^{k}}^{\top}+\sum_{i=1}^{k}A^{k-i}\Sigma_{w}{A^{k-i}}^{\top}\right)}{(N+1)\left\|\bar{\Sigma}\right\|_{2}^{2}\left\|W_{o}(N)\right\|_{F}+\left\|\Sigma_{v}\right\|_{2}}\right)^{2}.$

_Proof:_ We begin by writing the Kalman estimator using the notation defined
in (15)

$L_{k}=H_{k}M\left(M^{\top}M+I_{N+1}\otimes\Sigma_{v}\right)^{-1}.$

Suppose the rank of $M$ is $m$. Then the singular value decomposition of $M$
can be taken to be

$U\begin{bmatrix}S&0\\\ 0&0\end{bmatrix}V^{\top}=M$

where $S=\operatorname{diag}\left(\begin{bmatrix}s_{1}&s_{2}&\dots
s_{m}\end{bmatrix}\right)$ with $s_{1}\geq s_{2}\geq\dots\geq s_{m}\geq 0$,
while $U\in\mathbb{R}^{n(N+1)\times n(N+1)}$ and $V\in\mathbb{R}^{p(N+1)\times
p(N+1)}$. We can now lower bound the Frobenius norm of $L_{k}$ as follows.

$\displaystyle\left\|L_{k}\right\|_{F}^{2}\geq\left\|H_{k}M\right\|_{F}^{2}\sigma_{\min}\left\\{\left(M^{\top}M+\Sigma_{v}I\right)^{-1}\right\\}^{2}.$

Note that
$\sigma_{\min}\left\\{\left(M^{\top}M+\Sigma_{v}I\right)^{-1}\right\\}\geq\sigma_{\min}\left\\{\left(M^{\top}M+\left\|\Sigma_{v}\right\|_{2}I\right)^{-1}\right\\}$.
Therefore

$\displaystyle\left\|L_{k}\right\|_{F}^{2}$
$\displaystyle\geq\sigma_{\min}\left\\{\left(\begin{bmatrix}S^{2}&\\\
&0\end{bmatrix}+\left\|\Sigma_{v}\right\|_{2}I\right)^{-2}\right\\}\left\|H_{k}M\right\|_{F}^{2}$
(16) $\displaystyle=\sigma_{\min}\left\\{\left(\begin{bmatrix}S^{2}&\\\
&0\end{bmatrix}+\left\|\Sigma_{v}\right\|I\right)^{-2}\right\\}\left\|H_{k}H^{\top}\left(C^{\top}\otimes
I\right)\right\|_{F}^{2}$
$\displaystyle=\sigma_{\min}\left\\{\left(\begin{bmatrix}S^{2}&\\\
&0\end{bmatrix}+\left\|\Sigma_{v}\right\|_{2}I\right)^{-2}\right\\}$
$\displaystyle\left\|\begin{bmatrix}A^{k}\Sigma_{0}C^{\top}&\ldots&A^{k}\Sigma_{0}\left(A^{N}\right)^{\top}C^{\top}+\sum_{i=1}^{k}A^{k-i}\Sigma_{w}\left(A^{N-i}\right)^{\top}C^{\top}\end{bmatrix}\right\|_{F}^{2}$

Now observe that

$\sigma_{\min}\left\\{\left(\begin{bmatrix}S^{2}&\\\
&0\end{bmatrix}+\left\|\Sigma_{v}\right\|I\right)^{-2}\right\\}=\frac{1}{\left(s_{1}^{2}+\left\|\Sigma_{v}\right\|_{2}\right)^{2}}$
(17)

Also note that
$s_{1}=\left\|M\right\|_{2}\leq\left\|\bar{\Sigma}^{1/2}\right\|_{2}\left\|\bar{\Sigma}^{-1/2}M\right\|_{F}$.
We have that

$\displaystyle\left\|\bar{\Sigma}^{-1/2}M\right\|_{F}^{2}=\left\|\begin{bmatrix}\mathcal{O}_{N}^{\top}\\\
\left(\mathcal{Z}\mathcal{O}_{N}\right)^{\top}\\\ \vdots\\\
\left(\mathcal{Z}^{N}\mathcal{O}_{N}\right)^{\top}\end{bmatrix}\right\|_{F}^{2}\leq\sum_{i=0}^{N}\left\|\mathcal{Z}^{i}\mathcal{O}_{N}\right\|_{F}^{2}\leq(N+1)\left\|\mathcal{O}_{N}\right\|_{F}^{2}.$

Then

$\displaystyle
s_{1}\leq\left\|\bar{\Sigma}^{1/2}\right\|_{2}\sqrt{N+1}\left\|\mathcal{O}_{N}\right\|_{F}$
(18)

When $k\geq 0$, we have

$\displaystyle\left\|\begin{bmatrix}A^{k}\Sigma_{0}C^{\top}&\ldots&A^{k}\Sigma_{0}\left(A^{N}\right)^{\top}C^{\top}+\sum_{i=1}^{k}A^{k-i}\Sigma_{w}\left(A^{T-i}\right)^{\top}C^{\top}\end{bmatrix}\right\|_{F}^{2}$
$\displaystyle\geq\left\|\left(A^{k}\Sigma_{0}\left(A^{k}\right)^{\top}+\sum_{i=1}^{k}A^{k-i}\Sigma_{w}\left(A^{k-i}\right)^{\top}\right)C^{\top}\right\|_{F}^{2}$
$\displaystyle\geq\sigma_{\min}\left(A^{k}\Sigma_{0}\left(A^{k}\right)^{\top}+\sum_{i=1}^{k}A^{k-i}\Sigma_{w}\left(A^{k-i}\right)^{\top}\right)^{2}\left\|C\right\|_{F}^{2}.$

In conjunction with (16), (17), and (18), this leads to (12). $\blacksquare$

###  C.5 Proof of Lemma 3.6

Lemma 3.6.  _For any $L\in\mathbb{R}^{n\times p(N+1)}$, the following bound
holds_

$\displaystyle\operatorname{AR}(L)-\operatorname{SR}(L)\leq
2\varepsilon\left\|L\right\|_{2}\left\|\Sigma^{1/2}\right\|_{F}+\varepsilon^{2}\left\|L\right\|_{2}^{2}$

_where $\Sigma^{1/2}$ is the symmetric square root of the covariance of
$x_{k}-LY_{N}$. _

Proof: By Theorem 2.1,

$\displaystyle\operatorname{AR}(L)-\operatorname{SR}(L)\leq
2\varepsilon\mathbb{E}\left[\left\|L(x_{t}-LY_{N})\right\|_{2}\right]+\varepsilon^{2}\lambda_{\max}\left(L^{\top}L\right)\leq
2\varepsilon\left\|L\right\|_{2}\mathbb{E}\left[\left\|x_{t}-LY_{N}\right\|_{2}\right]+\varepsilon^{2}\left\|L\right\|_{2}^{2}$

We can upper bound $\mathbb{E}\left[\left\|x_{t}-LY_{N}\right\|_{2}\right]$ by
bounding the expectation of the euclidean norm of a normal random variable. In
particular, let $w$ be a $n$ dimensional standard normal random variable, so
that
$\mathbb{E}\left[\left\|x_{t}-LY_{N}\right\|_{2}\right]=\mathbb{E}\left[\left\|\Sigma^{1/2}w\right\|_{2}\right]$,
where $\Sigma$ is defined as the covariance of $x_{k}-LY_{N}$, and
$\Sigma^{1/2}$ is its symmetric square root. Let
$US^{1/2}U\operatorname{{}^{\top}}:=\Sigma^{1/2}$ be the eigenvalue
decomposition of $\Sigma^{1/2}$ so that

$\displaystyle\left\|\Sigma^{1/2}z\right\|_{2}$
$\displaystyle=\left\|US^{1/2}U\operatorname{{}^{\top}}w\right\|_{2}$

Now define $z=U\operatorname{{}^{\top}}w$. We have that $z\sim N(0,I)$. Then
the above quantity equals $\sqrt{\left\|US^{1/2}w\right\|_{2}^{2}}$. Jensen’s
inequality tells us that

$\displaystyle\mathbb{E}\left[\sqrt{\left\|US^{1/2}w\right\|_{2}^{2}}\right]\leq\sqrt{\mathbb{E}\left[\left\|US^{1/2}w\right\|_{2}^{2}\right]}=\sqrt{\mathbb{E}\left[w\operatorname{{}^{\top}}S^{1/2}w\right]}=\left\|S^{1/2}\right\|_{F}=\left\|\Sigma^{1/2}\right\|_{F},$

from which the theorem follows. $\blacksquare$

###  C.6 Theorem 3.2

Theorem 3.2.  _Suppose that $\hat{L}_{k}$ is the Kalman state estimator given
by Lemma 3.3. Then the gap between $\operatorname{AR}(\hat{L}_{k})$ and
$\operatorname{SR}(\hat{L}_{k})$ is upper bounded by_

$\displaystyle\operatorname{AR}(\hat{L}_{k})-\operatorname{SR}(\hat{L}_{k})$
$\displaystyle\geq\epsilon\left(\frac{{\left\|A^{k}\Sigma_{0}\left(A^{k}\right)^{\top}+\sum_{i=1}^{k}A^{k-i}\Sigma_{w}\left(A^{k-i}\right)^{\top}_{2}\right\|_{2}}}{\sigma_{\min}(W_{o}(N))^{1/2}\sigma_{\min}\left(\bar{\Sigma}\right)}\right)$
$\displaystyle\quad\times\left(2\sqrt{n}\left(\left\|\bar{\Sigma}\right\|_{2}+\left(\frac{\sqrt{\left\|\Sigma_{v}\right\|_{2}}}{\sigma_{\min}(W_{o}(N))^{1/2}\sigma_{\min}\left(\bar{\Sigma}\right)}\right)^{2}\right)^{1/2}+\epsilon\left(\frac{1}{\sigma_{\min}(W_{o}(N))^{1/2}\sigma_{\min}\left(\bar{\Sigma}\right)}\right)\right).$

_Furthermore, if
$\lambda_{\min}(W_{o}(N))^{1/2}\geq\sigma_{v}/\sigma_{\min}\left(\bar{\Sigma}\right)$,
and defining
$\kappa=\frac{\lambda_{\min}(W_{o}(N))^{1/2}\sigma_{\min}\left(\bar{\Sigma}\right)}{\lambda_{\min}(W_{o}(N))\sigma_{\min}\left(\bar{\Sigma}\right)^{2}+\sigma_{v}}$,
we get the bound_

$\displaystyle\operatorname{AR}(\hat{L}_{k})-\operatorname{SR}(\hat{L}_{k})$
$\displaystyle\leq\varepsilon\left(\kappa\sqrt{\left\|A^{k}\Sigma_{0}\left(A^{k}\right)^{\top}+\sum_{i=1}^{k}A^{k-i}\Sigma_{w}\left(A^{k-i}\right)^{\top}_{2}\right\|_{2}}\right)$
$\displaystyle\quad\times\left(2\sqrt{n}\left(\sigma_{\max}(\bar{\Sigma})^{2}+\sigma_{\min}(\Sigma_{v})\kappa^{2}\right)^{1/2}+\varepsilon\kappa\right)$

Proof: By Lemma 3.6, upper bounding the gap between $\operatorname{AR}(L_{k})$
and $\operatorname{SR}(L_{k})$ reduces to upper bounding
$\left\|\Sigma^{1/2}\right\|_{F}$ and $\left\|L_{k}\right\|_{2}$. First
consider $\left\|\Sigma^{1/2}\right\|_{F}$. Equivalence of norms tells us that

$\displaystyle\left\|\Sigma^{1/2}\right\|_{F}\leq\sqrt{n}\left\|\Sigma^{1/2}\right\|_{2}=\sqrt{n}\left\|\Sigma\right\|_{2}^{1/2}.$
(19)

Recalling the notation defined in (15), the Kalman filter may be expressed as
$L_{k}=H_{k}M\left(M^{\top}M+\Sigma_{v}\right)^{-1}$. We may also express
$\Sigma$ in terms of this notation:
$\Sigma=\left(H_{k}-L_{k}M\right)\bar{\Sigma}\left(H_{k}-L_{k}M\right)^{\top}+L_{k}\left(I\otimes\Sigma_{v}\right)L_{k}\operatorname{{}^{\top}}$.
To upper bound the spectral radius of this, we can leverage triangle
inequality and submultiplicativity

$\displaystyle\left\|\Sigma\right\|_{2}$
$\displaystyle\leq\left\|\left(H_{k}-L_{k}M\right)\bar{\Sigma}\left(H_{k}-L_{k}M\right)^{\top}\right\|_{2}+\left\|L_{k}\left(I\otimes\Sigma_{v}\right)L_{k}\operatorname{{}^{\top}}\right\|_{2}$
$\displaystyle\leq\left\|\bar{\Sigma}\right\|_{2}\left\|H_{k}-L_{k}M\right\|_{2}^{2}+\left\|\Sigma_{v}\right\|_{2}\left\|L_{k}\right\|_{2}^{2}.$

Note that
$H_{k}-L_{k}M=H_{k}-H_{k}M\left(M^{\top}M+\Sigma_{v}\right)^{-1}M=H_{k}\left(I-M\left(M^{\top}M+\Sigma_{v}\right)^{-1}M^{\top}\right)$.
Then by submultiplicativity,

$\displaystyle\left\|H_{k}\left(I-M\left(M^{\top}M+\Sigma_{v}\right)^{-1}M^{\top}\right)\right\|_{2}\leq\left\|H_{k}\right\|_{2}\left\|I-M\left(M^{\top}M+\Sigma_{v}\right)^{-1}M^{\top}\right\|_{2}\leq\left\|H_{k}\right\|_{2}.$

We can further upper bound $\left\|H_{k}\right\|_{2}$ in terms of system
properties. In particular, we have

$\displaystyle\left\|H_{k}\right\|_{2}=\sqrt{\left\|H_{k}\right\|_{2}^{2}}=\sqrt{\left\|H_{k}H_{k}^{\top}\right\|_{2}}=\sqrt{\left\|A^{k}\Sigma_{0}\left(A^{k}\right)^{\top}+\sum_{i=1}^{k}A^{k-i}\Sigma_{w}\left(A^{k-i}\right)^{\top}_{2}\right\|_{2}}.$

Thus

$\displaystyle\left\|\Sigma\right\|_{2}\leq\left\|\bar{\Sigma}\right\|_{2}\left\|H_{k}\right\|_{2}^{2}+\left\|\Sigma_{v}\right\|_{2}\left\|L\right\|_{2}^{2}\leq\left\|\bar{\Sigma}\right\|_{2}\left\|A^{k}\Sigma_{0}\left(A^{k}\right)^{\top}+\sum_{i=1}^{k}A^{k-i}\Sigma_{w}\left(A^{k-i}\right)^{\top}_{2}\right\|_{2}+\left\|\Sigma_{v}\right\|_{2}\left\|L\right\|_{2}^{2}.$
(20)

Next we obtain a bound on $\left\|L_{k}\right\|_{2}$. As in the proof of
Theorem 3.1, we will assign $m:=\operatorname{rank}(M)$ and take the singular
value decomposition of $M$ to be $U\begin{bmatrix}S&0\\\
0&0\end{bmatrix}V^{\top}$ where
$S=\operatorname{diag}\left(\begin{bmatrix}s_{1}&\dots&s_{m}\end{bmatrix}\right)$
with $s_{1}\geq s_{2}\geq\dots\geq s_{m}\geq 0$, while
$U\in\mathbb{R}^{n(N+1)\times n(N+1)}$ and $V\in\mathbb{R}^{p(N+1)\times
p(N+1)}$.

$\displaystyle\left\|L_{k}\right\|_{2}$
$\displaystyle=\left\|H_{k}M\left(M^{\top}M+\Sigma_{v}\right)^{-1}\right\|_{2}\leq\left\|H_{k}\right\|_{2}\left\|M\left(M^{\top}M+\sigma_{\min}\left(\Sigma_{v}\right)\right)^{-1}\right\|_{2}$
$\displaystyle=\left\|H_{k}\right\|_{2}\left\|U\begin{bmatrix}S&\\\
&0\end{bmatrix}V^{\top}\left(V\left(\begin{bmatrix}S^{2}&\\\
&0\end{bmatrix}+\sigma_{\min}(\Sigma_{v})\right)V^{\top}\right)^{-1}\right\|$
$\displaystyle=\left\|H_{k}\right\|_{2}\left\|U\begin{bmatrix}S&\\\
&0\end{bmatrix}\left(\begin{bmatrix}S^{2}&\\\
&0\end{bmatrix}+\sigma_{\min}(\Sigma_{v})\right)^{-1}V^{\top}\right\|_{2}$
$\displaystyle=\left\|H_{k}\right\|_{2}\left\|S(S^{2}+\sigma_{\min}(\Sigma_{v}))^{-1}\right\|_{2}$
$\displaystyle\leq\left\|H_{k}\right\|_{2}\max_{1\leq k\leq
m}\frac{s_{k}}{s_{k}^{2}+\sigma_{\min}(\Sigma_{v})}.$

A simple bound on the last maximization would be

$\displaystyle\max_{1\leq k\leq
m}\frac{s_{k}}{s_{k}^{2}+\sigma_{\min}(\Sigma_{v})}$
$\displaystyle\leq\max_{1\leq k\leq
m}\frac{s_{k}}{s_{k}^{2}}\leq\frac{1}{s_{m}}$ (21)

Note that
$s_{m}\geq\lambda_{\min}(W_{o}(N))^{1/2}\sigma_{\min}\left(\bar{\Sigma}\right)$,
so
$\frac{1}{s_{m}}\leq\frac{1}{\lambda_{\min}(W_{o}(N))^{1/2}\sigma_{\min}\left(\bar{\Sigma}\right)}$.
Then

$\displaystyle\left\|L_{k}\right\|_{2}\leq\frac{\left\|H_{k}\right\|_{2}}{\lambda_{\min}(W_{o}(N))^{1/2}\sigma_{\min}\left(\bar{\Sigma}\right)}\leq\frac{\sqrt{\left\|A^{k}\Sigma_{0}\left(A^{k}\right)^{\top}+\sum_{i=1}^{k}A^{k-i}\Sigma_{w}\left(A^{k-i}\right)^{\top}_{2}\right\|_{2}}}{\lambda_{\min}(W_{o}(N))^{1/2}\sigma_{\min}\left(\bar{\Sigma}\right)}.$
(22)

Then the first half of the theorem follows by combining the result of Lemma
3.6 with (19), (20) and (22).

However, if
$\lambda_{\min}(W_{o}(N))^{1/2}\sigma_{\min}\left(\bar{\Sigma}\right)\geq\sigma_{v}$,
then the maximum (21) is attained at

$\displaystyle\max_{1\leq k\leq
m}\frac{s_{k}}{s_{k}^{2}+\sigma_{\min}(\Sigma_{v})}$
$\displaystyle=\frac{s_{m}}{s_{m}^{2}+\sigma_{v}}$
$\displaystyle\leq\frac{\lambda_{\min}(W_{o}(N))^{1/2}\sigma_{\min}\left(\bar{\Sigma}\right)}{\lambda_{\min}(W_{o}(N))\sigma_{\min}\left(\bar{\Sigma}\right)^{2}+\sigma_{v}}.$

Therefore, when
$\lambda_{\min}(W_{o}(N))^{1/2}\geq\sigma_{v}/\sigma_{\min}\left(\bar{\Sigma}\right)$,
we have the more precise bound

$\displaystyle\left\|L_{k}\right\|_{2}$
$\displaystyle\leq\left\|H_{k}\right\|_{2}\frac{\lambda_{\min}(W_{o}(N))^{1/2}\sigma_{\min}\left(\bar{\Sigma}\right)}{\lambda_{\min}(W_{o}(N))\sigma_{\min}\left(\bar{\Sigma}\right)^{2}+\sigma_{v}}$
$\displaystyle\leq\sqrt{\left\|A^{k}\Sigma_{0}\left(A^{k}\right)^{\top}+\sum_{i=1}^{k}A^{k-i}\Sigma_{w}\left(A^{k-i}\right)^{\top}_{2}\right\|_{2}}\frac{\lambda_{\min}(W_{o}(N))^{1/2}\sigma_{\min}\left(\bar{\Sigma}\right)}{\lambda_{\min}(W_{o}(N))\sigma_{\min}\left(\bar{\Sigma}\right)^{2}+\sigma_{v}},$

which leads to the second half of the theorem.

$\blacksquare$