R\upsilon&RVV^{T}R^{T}\cr\end{array}\right]\succeq
0,R\in\beth\end{array}\right\\}$

where $B_{s}={\overline{\zeta}}_{s}V_{s}$, $1\leq s\leq S$, and $\beth$ is the
set of all $n\times m$ matrices $R$ such that the matrix $RV$ is invertible.
For a feasible solution to this problem, it holds $\Upsilon[R]\leq\rho^{-1}$,
with inequality becoming equality when the complementary to $R$ variables of
the problem maximize the problem’s objective $R$ being fixed.

Problem ($S$) is nonconvex, and we intend to process it by successive convex
approximation to get a “presumably good” suboptimal solution. First, consider
the following reformulation of ($S$) (with $\varrho=\rho^{-2}$):

$None$
$\min\limits_{\varrho,R,\\{G_{{s}},H_{{s}}\\}}\left\\{\varrho:\begin{array}[]{l}\left[\begin{array}[]{c|c}G_{{s}}&RB_{{s}}\cr\hline\cr
B_{{s}}^{T}R^{T}&H_{{s}}\cr\end{array}\right]\succeq
0\,\forall{s},\;\left[\begin{array}[]{c|c}\varsigma^{2}&\upsilon^{T}R^{T}\cr\hline\cr
R\upsilon&RVV^{T}R^{T}\cr\end{array}\right]\succeq 0\\\
\sum_{{s}}G_{{s}}\preceq RVV^{T}R^{T},\sum_{{s}}H_{{s}}\preceq\varrho
I_{n},\,R\in{\beth}\end{array}\right\\}$

where $G_{{s}}=RVG_{{s}}^{\prime}V^{T}R^{T}$ and
$H_{{s}}=\rho^{-2}H_{{s}}^{\prime}$. Indeed, ($S$) is equivalent to (cf.
Remark 4.3)

$\max\limits_{\rho,R,\\{G_{{s}}^{\prime},H_{{s}}^{\prime}\\}}\left\\{\varrho:\begin{array}[]{l}\left[\begin{array}[]{c|c}[RV]G_{{s}}^{\prime}[RV]^{T}&\rho
RB_{{s}}\cr\hline\cr\rho
B_{{s}}^{T}R^{T}&H_{{s}}^{\prime}\cr\end{array}\right]\succeq
0\,\forall{s},\;\left[\begin{array}[]{c|c}\varsigma^{2}&\upsilon^{T}R^{T}\cr\hline\cr
R\upsilon&RVV^{T}R^{T}\cr\end{array}\right]\succeq 0\\\
\sum_{{s}}G_{{s}}^{\prime}\preceq I_{n},\sum_{{s}}H_{{s}}^{\prime}\preceq
I_{n},\,R\in{\beth}\end{array}\right\\},$

which is, after the change of variables, the same as

$\max\limits_{\rho,R,\\{G_{{s}},H_{{s}}\\}}\left\\{\rho:\begin{array}[]{l}\left[\begin{array}[]{c|c}G_{{s}}&RB_{{s}}\cr\hline\cr
B_{{s}}^{T}R^{T}&H_{{s}}\cr\end{array}\right]\succeq 0\,\forall
s,\;\left[\begin{array}[]{c|c}\varsigma^{2}&\upsilon^{T}R^{T}\cr\hline\cr
R\upsilon&RVV^{T}R^{T}\cr\end{array}\right]\succeq 0\\\
\sum_{{s}}G_{{s}}\preceq
RVV^{T}R^{T},\sum_{{s}}H_{{s}}\preceq\rho^{-2}I_{n},\,R\in{\beth}\end{array}\right\\}$

which is equivalent to ($S_{*}$). Taking into account that for $Q\succeq 0$ we
have

$PQP^{T}\succeq PQR^{T}+RQP^{T}-SQS^{T},$

we can, given $\underline{R}\in{\beth}$, safely approximate ($S_{*}$) by the
convex optimization problem

$None$
$\min\limits_{\varrho,R,\\{G_{{s}},H_{{s}}\\}}\left\\{\varrho:\begin{array}[]{l}\left[\begin{array}[]{c|c}G_{{s}}&RB_{{s}}\cr\hline\cr
B_{{s}}^{T}R^{T}&H_{{s}}\cr\end{array}\right]\succeq 0\,\forall s\\\
\sum_{{s}}G_{{s}}\preceq
R[VV^{T}]\underline{R}^{T}+\underline{R}[VV^{T}]R^{T}-\underline{R}[VV^{T}]\underline{R}^{T},\,\sum_{{s}}H_{{s}}\preceq\varrho
I_{n}\\\ \left[\begin{array}[]{c|c}\varsigma^{2}&\upsilon^{T}R^{T}\cr\hline\cr
R\upsilon&\underline{R}VV^{T}R^{T}+RVV^{T}\underline{R}^{T}-\underline{R}VV^{T}\underline{R}^{T}\cr\end{array}\right]\succeq
0,\,R\in{\beth}[\underline{R}]\end{array}\right\\}$

where for $R\in{\beth}$ the closed convex set ${\beth}[R]$ satisfies
$R\in{\beth}[R]\subset{\beth}$, e.g.,

${\beth}[R]=\\{R:|I_{n}-[RV]^{-1}[RV]|\leq\gamma\\},\;\gamma<1,$

where $|\cdot|$ is the spectral norm. When solving ($S_{*}$) (=($S$)) by
successive convex approximation, we iterate the following update

  1. 1)

given feasible solution
$\underline{\varrho},\underline{R},\underline{G}_{{s}},\underline{H}_{{s}}$ to
($S_{*}$), we fix $R=\underline{R}$ and solve ($S_{*}$) in the remaining
variables, thus arriving at a new feasible solution
$\overline{\varrho},\underline{R},\overline{G}_{{s}},\overline{H}_{{s}}$ to
($S_{*}$) with $\overline{\varrho}\leq\underline{\varrho}$;

  2. 2)

with $\underline{R}$ just defined, ($S_{+}$) is feasible, a feasible solution
being $\overline{\varrho},\underline{R},\overline{G}_{{s}},\overline{H}_{{s}}$
. We solve ($S_{+}$), thus arriving at a new feasible solution to ($S_{+}$)
and thus to ($S_{*}$), with the value of the objective
$\leq\overline{\varrho}$,

until the progress in the objective becomes small. We can initialize our
process by the aggregation matrix yielded by AM, and we can further benefit
from running this process several times from randomly selected starting
points.

##### Numerical illustration

In the experiments we report on below, given noisy observations of the states
and inputs we want to recover the matrix of the observed dynamical system. In
our simulations, the actual dynamics (state dimension $d=3$) is given by

$u_{t+1}=\left[\begin{array}[]{rrr}1.4455&0.5933&-0.4275\\\
-0.8535&-0.0912&0.7069\\\ -0.3244&-0.1548&0.4679\\\
\end{array}\right]u_{t}+r_{t}.$

We assume that states $u_{t}$ and right hand sides $r_{t}$ are observed on
time horizons $0\leq t\leq N=64$ ($u_{t}$’s) and $0\leq t<N$ ($r_{t}$’s),
resulting in $(m={193})\times(n=10)$ matrices $V$ and $V_{s}$, $1\leq s\leq
387$. We consider three experimental setups with bounds
${\overline{\zeta}}_{s}$ on the magnitude of the error in the $s$-th
observation set to 0.1 in the first, and to 0.01 in the second; in the third
simulation (“10% relative error”) the bounds were
${\overline{\zeta}}_{s}=0.1\max[a_{s},1]$ where $a_{s}$ is the magnitude of
the $s$-th observation. In all cases, in series A of experiments, simulated
observation errors were drawn at random from the uniform distributions on the
vertices of the resulting “observation box;” in series B of experiments, we
used dependent of each observation errors stemming for heuristics aimed to
make recovery difficult (we skip the details on this heuristics). The actual
trajectories of states and right hand sides underlying observations are shown
in Figure 3 and were the same in all experiments.

Figure 3:  “True” system ($d=3$) trajectories of the state (top plot) and
input (bottom plot) .

To save on experimentation time, when optimizing aggregation, we restricted
aggregation matrices to be of the form $R_{\hbox{\tiny\rm ini}}\hbox{\rm
Diag}\\{s\\}$ with positive $s\in{\mathbf{R}}^{m}$. It is immediately seen
that multiplying an aggregation matrix $R$ by positive constant has no effect
on $\Upsilon[R]$ and $y_{R}[\epsilon]$, which allows to model positivity of
$s$ by the constraint $s_{i}\geq 1$, $1\leq i\leq m$. The process of
successive convex approximation (SCA) always was started with the all-ones
vector $s$, so that the initial value of aggregation matrix in this process
was $R_{\hbox{\tiny\rm ini}}$, with several choices of $R_{\hbox{\tiny\rm
ini}}$ we are about to describe.

In every experiment, we build 9 recoveries as follows:

  1. 1)

recoveries $\widehat{x}_{\hbox{\tiny\rm ini}}$ and
$\widehat{x}_{\hbox{\tiny\rm fin}}$, computed without invoking Alternating
Minimization (AM). In the notation of this section,
$\widehat{x}_{\hbox{\tiny\rm ini}}=\widehat{x}_{V^{T}}[0]$ (that is, we use
the simplest aggregation matrix $V^{T}=\overline{R}[0]$, see (109)), and
$\widehat{x}_{\hbox{\tiny\rm fin}}=\widehat{x}_{{\overline{R}}}[0]$, where
${\overline{R}}=V^{T}\hbox{\rm Diag}\\{{\overline{s}}\\}$ is the outcome of
optimizing by SCA the aggregation over matrices of the form $V^{T}\hbox{\rm
Diag}\\{s\\}$.

  2. 2)

recoveries $\widehat{x}^{a}_{\hbox{\tiny\rm ini}}$ and
$\widehat{x}^{a}_{\hbox{\tiny\rm fin}}$ are obtained via AM initialized with
$y=y_{V^{T}}[0]$. Upon termination, the AM process provides us with the value
${\overline{\epsilon}}=\epsilon^{a}\in B_{\infty}$ of $\epsilon$, as well as
with aggregation matrix $R^{a}=\overline{R}[\epsilon^{a}]$. Recovery
$\widehat{x}^{a}_{\hbox{\tiny\rm ini}}$ is nothing but
$\widehat{x}_{R^{a}}[\epsilon^{a}]$, and $\widehat{x}^{a}_{\hbox{\tiny\rm
fin}}$ is $\widehat{x}_{R^{a}_{*}}[\epsilon^{a}]$, where $R^{a}_{*}$ is the
result of SCA as applied to optimizing aggregation over matrices
$R^{a}\hbox{\rm Diag}\\{s\\}$ with positive $s$.

  3. 3)

recoveries, $\widehat{x}^{b}_{\hbox{\tiny\rm ini}}$ and
$\widehat{x}^{b}_{\hbox{\tiny\rm fin}}$, obtained in the same fashion as in
2), but with AM initialized with $y_{{\overline{R}}}[0]$ rather than
$y_{V^{T}}[0]$, with ${\overline{R}}$ defined in 1).

  4. 4)

recovery $\widehat{x}_{\hbox{\rm\tiny 4.3.2}}$—the Euclidean projection of the
robust linear estimate described in Section 4.4.2 onto the plane of solutions
to (62).

  5. 5)

recovery $\widehat{x}_{\hbox{\tiny\rm 4.3.3.a}}$—estimate $\widehat{x}$ as
described in Section 4.4.3 with $\|\cdot\|_{\cal X}=\|\cdot\|_{2}$ and
$\|\cdot\|_{\cal B}=\|\cdot\|_{\infty}$, and single matrix
$E_{1}=\mathrm{Id}$, and recovery $\widehat{x}_{\hbox{\tiny\rm 4.3.3.b}}$ of
the same type with $m$ matrices $E_{\mu}$, $E_{\mu}z=z_{\mu}$, $1\leq\mu\leq
m$.

Note that recoveries 1) – 3) are of the form $\widehat{x}_{R}[\epsilon]$ with
aggregating matrix $R$ and $\epsilon\in B_{\infty}$ which depend on the
recovery in question. “With luck”—when $\Upsilon[R]<1$—we have at our disposal
an upper bound, stemming from (107), on the error of the corresponding
recovery. Similarly, with luck (see Sections 4.4.2 and 4.4.3), estimates
$\widehat{x}_{\hbox{\rm\tiny 4.3.2}}$ and $\widehat{x}_{{\hbox{\tiny\rm
4.3.3.b}}}$ also are equipped with upper bounds on the recovery errors.
Observe that if at least one of the recoveries admits such a bound, all
recoveries admit bounds: indeed, given a pair of recoveries
$\widehat{x}^{\prime}$, $\widehat{x}^{\prime\prime}$, when we know that
$\|\widehat{x}^{\prime}-x\|_{2}\leq\upsilon$, we know also that
$\|\widehat{x}^{\prime\prime}-x\|_{2}\leq\upsilon+\|\widehat{x}^{\prime}-\widehat{x}^{\prime\prime}\|_{2}$.

The results of the experiments are summarized in Table 1. In the table, column
”UpB” presents computed upper bounds on $\|\cdot\|_{2}$-recovery errors, and
”$\Upsilon$” for the recovery $\widehat{x}_{\hbox{\rm\tiny 4.3.2}}$ is
$\min_{E}\Upsilon[E]$, and for all recoveries utilizing aggregation is
$\Upsilon[R]$, where $R$ is the aggregation matrix underlying the recovery.

| 0.1 observation error bound, A
---|---
$\widehat{x}$ | $\|\widehat{x}-x\|_{2}$ | $\|\widehat{x}-x\|_{\infty}$ | UpB | $\Upsilon$
$\widehat{x}_{\hbox{\rm\tiny 4.3.2}}$ | 1.090 | 0.747 | 1.691 | 0.573
$\widehat{x}_{{\hbox{\tiny\rm 4.3.3.a}}}$ | 1.016 | 0.606 | 2.469 | N/A
$\widehat{x}_{{\hbox{\tiny\rm 4.3.3.b}}}$ | 0.517 | 0.316 | 2.455 | N/A
$\widehat{x}_{\hbox{\tiny\rm ini}}$ | 0.723 | 0.452 | 2.747 | 1.786
$\widehat{x}_{\hbox{\tiny\rm fin}}$ | 0.364 | 0.235 | 2.589 | 0.623
$\widehat{x}^{a}_{\hbox{\tiny\rm ini}}$ | 0.012 | 0.007 | 2.779 | 3.166
$\widehat{x}^{a}_{\hbox{\tiny\rm fin}}$ | 0.012 | 0.007 | 2.779 | 0.623
$\widehat{x}^{b}_{\hbox{\tiny\rm ini}}$ | 0.038 | 0.033 | 2.766 | 3.127
$\widehat{x}^{b}_{\hbox{\tiny\rm fin}}$ | 0.038 | 0.033 | 2.766 | 0.623

| 0.1 observation error bound, B
---|---
$\widehat{x}$ | $\|\widehat{x}-x\|_{2}$ | $\|\widehat{x}-x\|_{\infty}$ | UpB
$\widehat{x}_{\hbox{\rm\tiny 4.3.2}}$ | 0.996 | 0.727 | 1.697
$\widehat{x}_{{\hbox{\tiny\rm 4.3.3.a}}}$ | 0.948 | 0.631 | 2.349
$\widehat{x}_{{\hbox{\tiny\rm 4.3.3.b}}}$ | 0.760 | 0.402 | 2.106
$\widehat{x}_{\hbox{\tiny\rm ini}}$ | 0.430 | 0.287 | 2.467
$\widehat{x}_{\hbox{\tiny\rm fin}}$ | 0.332 | 0.237 | 2.438
$\widehat{x}^{a}_{\hbox{\tiny\rm ini}}$ | 0.213 | 0.143 | 2.541
$\widehat{x}^{a}_{\hbox{\tiny\rm fin}}$ | 0.213 | 0.143 | 2.541
$\widehat{x}^{b}_{\hbox{\tiny\rm ini}}$ | 0.201 | 0.138 | 2.734
$\widehat{x}^{b}_{\hbox{\tiny\rm fin}}$ | 0.201 | 0.138 | 2.734

| 0.01 observation error bound, A
---|---
$\widehat{x}$ | $\|\widehat{x}-x\|_{2}$ | $\|\widehat{x}-x\|_{\infty}$ | UpB | $\Upsilon$
$\widehat{x}_{\hbox{\rm\tiny 4.3.2}}$ | 0.034 | 0.022 | 0.156 | 0.062
$\widehat{x}_{{\hbox{\tiny\rm 4.3.3.a}}}$ | 0.153 | 0.113 | 0.302 | N/A
$\widehat{x}_{{\hbox{\tiny\rm 4.3.3.b}}}$ | 0.074 | 0.048 | 0.355 | N/A
$\widehat{x}_{\hbox{\tiny\rm ini}}$ | 0.018 | 0.013 | 0.187 | 1.201
$\widehat{x}_{\hbox{\tiny\rm fin}}$ | 0.049 | 0.039 | 0.167 | 0.694
$\widehat{x}^{a}_{\hbox{\tiny\rm ini}}$ | 0.002 | 0.001 | 0.170 | 1.167
$\widehat{x}^{a}_{\hbox{\tiny\rm fin}}$ | 0.002 | 0.001 | 0.170 | 0.699
$\widehat{x}^{b}_{\hbox{\tiny\rm ini}}$ | 0.002 | 0.002 | 0.170 | 1.165
$\widehat{x}^{b}_{\hbox{\tiny\rm fin}}$ | 0.002 | 0.002 | 0.170 | 0.699

| 0.01 observation error bound, B
---|---
$\widehat{x}$ | $\|\widehat{x}-x\|_{2}$ | $\|\widehat{x}-x\|_{\infty}$ | UpB
$\widehat{x}_{\hbox{\rm\tiny 4.3.2}}$ | 0.025 | 0.015 | 0.151
$\widehat{x}_{{\hbox{\tiny\rm 4.3.3.a}}}$ | 0.167 | 0.114 | 0.327
$\widehat{x}_{{\hbox{\tiny\rm 4.3.3.b}}}$ | 0.096 | 0.056 | 0.253
$\widehat{x}_{\hbox{\tiny\rm ini}}$ | 0.018 | 0.014 | 0.172
$\widehat{x}_{\hbox{\tiny\rm fin}}$ | 0.020 | 0.016 | 0.171
$\widehat{x}^{a}_{\hbox{\tiny\rm ini}}$ | 0.018 | 0.014 | 0.172
$\widehat{x}^{a}_{\hbox{\tiny\rm fin}}$ | 0.018 | 0.014 | 0.172
$\widehat{x}^{b}_{\hbox{\tiny\rm ini}}$ | 0.020 | 0.016 | 0.171
$\widehat{x}^{b}_{\hbox{\tiny\rm fin}}$ | 0.020 | 0.016 | 0.171

| 10% observation errors, A
---|---
$\widehat{x}$ | $\|\widehat{x}-x\|_{2}$ | $\|\widehat{x}-x\|_{\infty}$ | UpB | $\Upsilon$
$\widehat{x}_{\hbox{\rm\tiny 4.3.2}}$ | 1.170 | 0.820 | 1.617 | 0.580
$\widehat{x}_{{\hbox{\tiny\rm 4.3.3.a}}}$ | 1.098 | 0.788 | 2.751 | N/A
$\widehat{x}_{{\hbox{\tiny\rm 4.3.3.b}}}$ | 0.683 | 0.514 | 9.083 | N/A
$\widehat{x}_{\hbox{\tiny\rm ini}}$ | 0.762 | 0.471 | 2.689 | 1.786
$\widehat{x}_{\hbox{\tiny\rm fin}}$ | 0.485 | 0.321 | 2.410 | 0.635
$\widehat{x}^{a}_{\hbox{\tiny\rm ini}}$ | 0.014 | 0.011 | 2.797 | 3.483
$\widehat{x}^{a}_{\hbox{\tiny\rm fin}}$ | 0.014 | 0.011 | 2.797 | 0.644
$\widehat{x}^{b}_{\hbox{\tiny\rm ini}}$ | 0.014 | 0.011 | 2.797 | 3.480
$\widehat{x}^{b}_{\hbox{\tiny\rm fin}}$ | 0.014 | 0.011 | 2.797 | 0.540

|  10% observation errors, B
---|---
$\widehat{x}$ | $\|\widehat{x}-x\|_{2}$ | $\|\widehat{x}-x\|_{\infty}$ | UpB
$\widehat{x}_{\hbox{\rm\tiny 4.3.2}}$ | 1.136 | 0.790 | 1.815
$\widehat{x}_{{\hbox{\tiny\rm 4.3.3.a}}}$ | 2.051 | 1.445 | 2.733
$\widehat{x}_{{\hbox{\tiny\rm 4.3.3.b}}}$ | 0.712 | 0.432 | 2.416
$\widehat{x}_{\hbox{\tiny\rm ini}}$ | 0.341 | 0.229 | 2.812
$\widehat{x}_{\hbox{\tiny\rm fin}}$ | 0.269 | 0.189 | 2.740
$\widehat{x}^{a}_{\hbox{\tiny\rm ini}}$ | 0.230 | 0.135 | 3.110
$\widehat{x}^{a}_{\hbox{\tiny\rm fin}}$ | 0.230 | 0.135 | 3.110
$\widehat{x}^{b}_{\hbox{\tiny\rm ini}}$ | 0.247 | 0.136 | 3.049
$\widehat{x}^{b}_{\hbox{\tiny\rm fin}}$ | 0.305 | 0.136 | 3.049

Table 1:  Results of experiments.

Note that numerical lower bounds on the worst-case recovery error given the
actual trajectories of states and right hand sides and the magnitudes of
errors can be constructed; we discuss one construction of thus type at the end
of this section. In our experiments, these lower bounds were 0.241 (first and
third experiments in both series) and 0.024 (second experiments in both
series). We observe that the actual errors of recoveries utilizing Alternative
Minimization compare favorably to these lower bounds.999Of course, there is no
contradiction in actual errors being by factor 5-10 less than the worst-case
lower bounds

In our opinion, the reported results are rather encouraging. First, with not
too small observation errors (0.1 in the first, and 10% in the third
experiment), recovery errors, at least for the recoveries utilizing AM in
series A, are small. And this is so in spite of the “poor spectral content” of
the considered right hand sides which in our experiments were harmonic
oscillations with common to all entries in $r_{t}$’s randomly selected
frequency. On the negative side, upper bounds on recovery errors we end up
with are quite conservative, but this, to the best of our knowledge, is a
rather common situation. We believe that the very fact that we are able to
somehow upper-bound recovery errors is remarkable, and we stress that
optimizing aggregation (to the extent achievable with SCA) is instrumental
here: aside of robust linear estimate, in all reported experiments without
this optimization we have $\Upsilon>1$, that is, no upper bounds on the
recovery error at all.

##### Lower-bounding worst-case recovery errors

In our simulated experiments, we have at our disposal the “nominal” system
matrix $\overline{X}$, trajectories $\\{u_{t},1\leq t\leq N+1\\}$ of states
and trajectories $\\{\overline{r}_{t},1\leq t\leq N\\}$ of right hand sides
satisfying

$u_{t+1}=\overline{X}u_{t}+\overline{r}_{t},\;1\leq t\leq N.$

We are also given entrywise bounds $\bar{\zeta}_{ti}$ on the magnitudes of
errors in observations of right hand sides. This data allows to build a lower
bound on the worst-case recovery error, namely, as follows. Assume that our a
priori information on the system matrix $X$ to be identified is given by a
system of linear equations

$None$ ${{\mathop{\hbox{\rm Tr}}}(A_{j}X^{T})=b_{j}:={\mathop{\hbox{\rm
Tr}}}(A_{j}\overline{X}^{T}),\,j\leq J}$

(in the experiments described above $(*)$ is just empty). Let us subject the
nominal matrix $\overline{X}$ to perturbation $\Delta$ satisfying the
homogeneous version

${{\mathop{\hbox{\rm Tr}}}(A_{j}\Delta^{T})=0,\,j\leq J}$

of constraints $(*)$ and simultaneously pass from the nominal right hand sides
$\overline{r}_{t}$ to updated right hand sides $\overline{r}_{t}+\delta_{t}$
in such a way that the states $u_{t}$ remain unchanged, resulting in

$\delta_{t}=-\Delta u_{t},\,1\leq t\leq N.$

Imposing bounds $\bar{\zeta}_{ti}$ on the magnitudes of entries in
$\delta_{t}$, we end up with a system of linear constraints on $\Delta$, with
symmetric w.r.t. the origin solution set ${\cal D}$. When $\Delta\in{{\cal
D}}$, for $1\leq t\leq N$, we have

$\displaystyle u_{t+1}$ $\displaystyle=(\overline{X}+\Delta)u_{t}+r^{+}_{t},$
$\displaystyle(a)$ $\displaystyle u_{t+1}$
$\displaystyle=(\overline{X}-\Delta)u_{t}+r^{-}_{t}$ $\displaystyle(b)$

with $|[r^{\pm}_{t}]_{i}-[\overline{r}_{t}]_{i}|\leq\bar{\zeta}_{ti}$. Besides
this, both $\overline{X}+\Delta$ and $\overline{X}-\Delta$ satisfy $(*)$ and
thus conform with our a priori information about the matrix of the system.
Thus, treating $u_{t}$ as given to us observations of states, and
$\overline{r}_{t}$ as observations of right hand sides, these data fit, within
allowed observation errors, both dynamics $(a)$, $(b)$, and both of these
dynamics agree with available a priori information. As a result, for any norm
$\|\cdot\|$ on ${\mathbf{R}}^{d\times d}$ and any (deterministic) recovery,
the worst-case $\|\cdot\|$-norm of recovery error given the above observations
and the magnitudes of observation errors is at least $\|\Delta\|$. Thus, the
lower bound for the norm of the worst-case recovery error is at least

$\max_{\Delta}\\{\|\Delta\|:|[\Delta u_{t}]_{i}|\leq\bar{\zeta}_{ti},1\leq
t\leq N,1\leq i\leq d,{{\mathop{\hbox{\rm Tr}}}(A_{j}\Delta^{T})=0,\,j\leq
J}\\}.$

When $\|\Delta\|=\max_{i,j}|\Delta_{ij}|$, the latter problem reduces to
solving $d^{2}$ LP programs; when $\|\cdot\|=\|\cdot\|_{2}$, we can use
successive convex approximation (or semidefinite relaxation) to get a
suboptimal solution, and this is how the lower bounds we have mentioned were
built.

##  Appendix C Scaling

###  C.1 Motivation and goal

The problem we address in this section is as follows: we are given an
uncertain $n\times n$ matrix

${\cal A}=\left\\{{\sum}_{s=1}^{S}\epsilon_{s}A_{s}:\|\epsilon\|_{\infty}\leq
1\right\\}$

and a norm $\|\cdot\|_{\cal X}$ on ${\mathbf{R}}^{n}$ with unit ball ${\cal
X}$. We are allowed to subject instances of ${\cal A}$ to a common similarity
transformation $A\mapsto RAR^{-1}$, where $R$ is a nonsingular $n\times n$
matrix, we denote

$R{\cal
A}R^{-1}:=\left\\{{\sum}_{s=1}^{S}\epsilon_{s}RA_{s}R^{-1}:\|\epsilon\|_{\infty}\leq
1\right\\}.$

Our ideal goal would be to select nonsingular square $R$ which minimizes the
robust norm $\|R{\cal A}R^{-1}\|_{{\cal X},{\cal X}}$ of $R{\cal A}R^{-1}$. A
more realistic goal101010As we shall see, this “more realistic” goal still is
not attainable, but it is “less unattainable” than the ideal one. would be to
minimize over $R$ the upper bound, yielded by our machinery, on $\|R{\cal
A}R^{-1}\|_{{\cal X},{\cal X}}$. Our motivating example is as follows:

> Certifying robust stability of uncertain discrete time dynamical system.
> Consider uncertain discrete time system
>
> $x_{t}=A_{t}x_{t-1},t=0,1,...$
>
> where $n\times n$ matrix $A_{t}$ is, at every $t$, selected by nature from a
> given uncertainty set ${\cal U}\subset{\mathbf{R}}^{n\times n}$ with no
> further restrictions on the selection. Such a system is called stable, if
> every trajectory, for every selection $A_{t}$’s from ${\cal U}$, converges
> to 0 as $t\to\infty$.
>
> Now assume that we can point out a nonsingular $n\times n$ matrix $R$ and a
> norm $\|\cdot\|_{\cal X}$ on ${\mathbf{R}}^{n}$ such that
>
> $\|R{\cal U}R^{-1}\|_{{\cal X},{\cal X}}:=\sup\limits_{A\in{\cal
> U}}\|RAR^{-1}\|_{{\cal X},{\cal X}}<1.$
>
> Then we can be sure that the uncertain system is stable: system dynamics
> says that $z_{t+1}:=Rx_{t+1}\in[R{\cal U}R^{-1}]z_{t}$ and therefore
> $\|Rx_{t}\|_{\cal X}\leq\|Rx_{0}\|_{\cal X}\|R{\cal U}R^{-1}\|_{{\cal
> X},{\cal X}}^{t}$ for all $t$, implying stability.111111Sufficient stability
> condition of this type associated with $\|\cdot\|_{\cal X}=\|\cdot\|_{2}$ is
> called “existence of Lyapunov stability certificate” and is one of the
> standard tools in Control.
>
> Now, an uncertain $n\times n$ matrix ${\cal
> A}=\left\\{\sum_{s=1}^{S}\epsilon_{s}A_{s}:\|\epsilon\|_{\infty}\leq
> 1\right\\}$ can be enclosed, as ${\cal A}_{1}$, in the single-parametric
> family of uncertain matrices
>
> ${\cal A}_{\rho}=\rho{\cal
> A}=\left\\{{\sum}_{s}\epsilon_{s}A_{s}:\|\epsilon\|_{\infty}\leq\rho\right\\},\,\rho>0,$
>
> Whenever we have at our disposal $R$ and $\varsigma$ such that $\|R{\cal
> A}R^{-1}\|_{{\cal X},{\cal X}}\leq\varsigma$, we ensure that when
> uncertainty set ${\cal U}$ is contained in ${\cal A}_{\rho}$ with
> $\rho<1/\varsigma$, the uncertain system is stable. Given ${\cal A}$, the
> resulting sufficient stability condition is the stronger the smaller
> $\|R{\cal A}R^{-1}\|_{{\cal X},{\cal X}}$, and since we can select $R$ it
> would be nice to minimize the latter robust norm over $R$.

###  C.2 Simple case

In the example motivating our scaling problem, the matrix norm, by the essence
of the matter, should be $\|\cdot\|_{{\cal X},{\cal X}}$, implying that in
order for the approach developed in Section 4.2 to be applicable, the
corresponding norm $\|\cdot\|_{\cal X}$ on the image and original space should
be both ellitopic and co-ellitopic. This is why (cf. Remark 4.5) in the sequel
we focus on the simple case

(110) ${\cal X}=\hbox{\rm Conv}\Big{\\{}{\bigcup}_{k\leq K}P_{k}{\cal
B}_{n}\Big{\\}},$

where ${\cal B}_{n}$ is the unit $\|\cdot\|_{2}$-ball in ${\mathbf{R}}^{n}$,
and $P_{k}\in{\mathbf{R}}^{n\times n}$ are nonsingular matrices.121212The
reasons for sticking to ${\cal X}$ of the form (110) have been partially
explained, cf. Remark 4.5. What remains to be explained is why we assume the
matrices $P_{k}$ to be square and nonsingular. This assumption simplifies
significantly the derivations to follow and is basically “for free”—a convex
compact set ${\cal X}\subset{\mathbf{R}}^{n}$ with nonempty interior given by
(69) can be easily approximated to whatever high accuracy by similar set with
square nonsingular $P_{k}$. Indeed, the conjugate norm
$\max\limits_{k}\|P_{k}^{T}x\|_{2}$ remains intact when restricting $P_{k}$’s
to orthogonal complements of their kernels; thus, we lose nothing by assuming
that $P_{k}$ is $n\times m_{k}$ with $m_{k}\leq n$. Augmenting $P_{k}$ with
$n-m_{k}$ small columns and slightly perturbing the existing entries in
$P_{k}$, we arrive at nonsingular square matrices $\overline{P}_{k}$; given
tolerance $\delta>0$, we can select the perturbations and the magnitudes of
added columns so small that
$(1-\delta)\max\limits_{k}\|P_{k}^{T}x\|_{2}\leq\max\limits_{k}\|\overline{P}_{k}^{T}x\|_{2}\leq(1+\delta)\max\limits_{k}\|P_{k}^{T}x\|_{2}.$
As we know, in this case

$\begin{array}[]{c}\|x\|_{\cal X}=\min\limits_{x_{k}\in{\mathbf{R}}^{n},k\leq
K}\left\\{\sum_{k}\|x_{k}\|_{2}:\sum_{k}{P}_{k}x_{k}=x\right\\},\\\
\|x\|_{{\cal X}_{*}}=\max\limits_{k\leq K}\|P_{k}^{T}x\|_{2},\|A\|_{{\cal
X},{\cal X}}=\max_{k\leq K}\|AP_{k}\|_{{\cal X},{\cal B}_{n}}.\end{array}$

####  C.2.1 Processing the problem

Taking into account that ${\cal X}_{*}$ is the ellitope
$\\{x:\|P_{k}^{T}x\|_{2}\leq 1,k\leq K\\}$, and utilizing Proposition 4.1 we
can efficiently bound the value $\|R{\cal A}R^{-1}\|_{{\cal X},{\cal X}}$
within the factor $\vartheta(2\max_{s}{\mathop{\hbox{\rm Rank}}}A_{s})$ with
the quantity

$\hbox{\rm Opt}(R)=\max\limits_{k}\hbox{\rm Opt}_{k}(R)$

where

$\hbox{\rm
Opt}_{k}(R)=\min\limits_{\lambda,\mu,\\{g_{s},h_{s}\\}}\left\\{{\sum}_{k}\lambda_{k}+\mu:\begin{array}[]{l}\left[\begin{array}[]{c|c}g_{s}&{1\over
2}RA_{s}R^{-1}P_{k}\cr\hline\cr{1\over
2}P_{k}^{T}R^{-T}A_{s}^{T}R^{T}&h_{s}\cr\end{array}\right]\succeq 0,\,s\leq
S\\\ \lambda\geq
0,\,\sum_{s}g_{s}\preceq\sum_{k=1}^{K}\lambda_{k}{P_{k}P_{k}^{T}},\,\sum_{s}h_{s}\preceq\mu
I_{n}\end{array}\right\\}.$

When denoting ${G}_{s}=R^{-1}g_{s}R^{-T}$ and
${H}_{s}=R^{T}P_{k}^{-T}h_{s}P_{k}^{-1}R$, the latter problems can be
rewritten as

(118) $\displaystyle\hbox{\rm
Opt}_{k}^{-1}(R)=\max\limits_{\\{{G}_{s},{H}_{s}\\},\lambda,E,\rho}\left\\{\rho:\begin{array}[]{l}\left[\begin{array}[]{c|c}{G}_{s}&\rho
A_{s}\cr\hline\cr\rho A_{s}^{T}&{H}_{s}\cr\end{array}\right]\succeq 0,\,s\leq
S\\\
\left[\begin{array}[]{c|c}\sum_{k}\lambda_{k}{P_{k}P_{k}^{T}}&R\cr\hline\cr
R^{T}&{E}\cr\end{array}\right]\succeq 0,\,\lambda\geq
0,\,\sum_{k}\lambda_{k}=1,\\\ \sum_{s}{G}_{s}\preceq
E^{-1},\,\sum_{s}{H}_{s}\preceq
R^{T}[P_{k}^{-T}P_{k}^{-1}]R\end{array}\right\\}$

Indeed, by Remark 4.3,

$\displaystyle\hbox{\rm Opt}^{-1}_{k}(R)$ $\displaystyle=$
$\displaystyle\max\limits_{\\{g_{s},h_{s}\\},\\{\lambda_{s}\\},\rho}\left\\{\rho:\begin{array}[]{l}\left[\begin{array}[]{c|c}g_{s}&\rho
RA_{s}R^{-1}P_{k}\cr\hline\cr\rho
P_{k}^{T}R^{-T}A_{s}^{T}{R^{T}}&h_{s}\cr\end{array}\right]\succeq 0,\,s\leq
S\\\ \lambda\geq 0\,,\sum_{s}\lambda_{s}\leq
1,\,\sum_{s}g_{s}\preceq\sum_{s}\lambda_{s}{P_{s}P_{s}^{T}},\,\sum_{s}h_{s}\preceq
I_{n}\end{array}\right\\}$ $\displaystyle=$
$\displaystyle\max\limits_{\\{{g}_{s},{h}_{s}\\},\lambda,\rho}\left\\{\rho:\begin{array}[]{l}\left[\begin{array}[]{c|c}R^{-1}g_{s}R^{-T}&\rho
A_{s}\cr\hline\cr\rho
A_{s}^{T}&R^{T}P_{k}^{-T}h_{s}P_{k}^{-1}R\cr\end{array}\right]\succeq
0,\,s\leq S\\\ \lambda\geq 0,\,\sum_{k}\lambda_{k}\leq
1,\,\sum_{s}g_{s}\preceq\sum_{k}\lambda_{k}{P_{k}P_{k}^{T}},\,\sum_{s}h_{s}\preceq
I_{n}\end{array}\right\\}$ $\displaystyle=$
$\displaystyle\max\limits_{\\{G_{s},H_{s}\\},\lambda,\rho}\left\\{\rho:\begin{array}[]{l}\left[\begin{array}[]{c|c}G_{s}&\rho
A_{s}\cr\hline\cr\rho A_{s}^{T}&H_{s}\cr\end{array}\right]\succeq 0,\,s\leq
S,\,\lambda\geq 0,\,\sum_{k}\lambda_{k}=1\\\ \sum_{s}G_{s}\preceq
R^{-1}\left[\sum_{k}\lambda_{k}{P_{k}P_{k}^{T}}\right]R^{-T},\,\sum_{s}H_{s}\preceq
R^{T}P_{k}^{-T}P_{k}^{-1}R\end{array}\right\\}$

which is equivalent to (118). We conclude that the problem of minimizing over
$R$ of the actual robust norm of $R{\cal A}R^{-1}$ induced by the norm
$\|\cdot\|_{\cal X}$ on ${\mathbf{R}}^{n}$ can be safely approximated by the
problem

(125)
$\max\limits_{\rho,R,\\{\lambda^{k}\\},\atop\\{{G}^{k}_{s},{H}^{k}_{s},{E}_{k}\\}}\left\\{\rho:\begin{array}[]{lrlr}\\\
{R\in\beth}&(a)&\;\;\left[\begin{array}[]{c|c}\sum_{j}\lambda^{k}_{j}{P_{j}P_{j}^{T}}&R\cr\hline\cr
R^{T}&{E}_{k}\cr\end{array}\right]\succeq 0&(d)\\\
\sum_{s}{G}^{k}_{s}\preceq{E}_{k}^{-1}&(b)&\;\;\left[\begin{array}[]{c|c}{G}^{k}_{s}&\rho
A_{s}\cr\hline\cr\rho A_{s}^{T}&{H}^{k}_{s}\cr\end{array}\right]\succeq
0&(e)\\\ \sum_{s}{H}^{k}_{s}\preceq
R^{T}[P_{k}P_{k}^{T}]^{-1}R&(c)&\;\;\lambda^{k}\geq
0,\sum_{j}\lambda^{k}_{j}=1&(f)\\\ \end{array}\right\\}.$

where $\beth$ is the set of nonsingular $n\times n$ matrices.

##### Applying SCA

The resulting problem is heavily nonconvex; we intend to process it by a
reasonable heuristics of the successive convex approximation type similarly to
what was done in Section B. Specifically, assume that at the beginning of an
iteration we have at our disposal a feasible iterate
$\\{\underline{\rho},\underline{R},\underline{G}^{k}_{s},\underline{H}^{k}_{s},\underline{E}_{k},\underline{\lambda}^{k}:1\leq
k\leq K,1\leq s\leq S\\}$. Let us act as follows:

  * •

(I): We set the value of variable $R$ to $\underline{R}$ and consider the
optimization problem in remaining variables
$\rho,\,{G}^{k}_{s},\,{H}^{k}_{s},\,{E}_{k},\,1\leq k\leq K,\,1\leq s\leq S,$
obtained from (125). After eliminating $E_{k}$-variables (given by
$E_{k}=\underline{R}^{T}\left[\sum_{j}\lambda^{k}_{j}{P_{j}P_{j}^{T}}\right]^{-1}\underline{R}$),
this problem becomes convex problem

$\max\limits_{\rho,\lambda^{k},{G}^{k}_{s},{H}^{k}_{s}}\left\\{\rho:\begin{array}[]{l}\sum_{s}{G}^{k}_{s}\preceq\underline{R}^{-1}\left[\sum_{s}\lambda^{k}_{s}{P_{s}P_{s}^{T}}\right]\underline{R}^{-T},\,\sum_{s}{H}^{k}_{s}\preceq\underline{R}^{T}[P_{k}P_{k}^{T}]^{-1}\underline{R}\\\
\left[\begin{array}[]{c|c}{G}^{k}_{s}&\rho A_{s}\cr\hline\cr\rho
A_{s}^{T}&{H}^{k}_{s}\cr\end{array}\right]\succeq 0,\,\lambda^{k}\geq
0,\sum_{s}\lambda^{k}_{s}=1,\,1\leq k\leq K,1\leq s\leq S\\\
\end{array}\right\\}$

The latter problem clearly is feasible, a feasible solution being
$\\{\underline{\rho},\underline{G}^{k}_{s},\underline{H}^{k}_{s},\underline{\lambda}^{k}:1\leq
k\leq K,1\leq s\leq S\\}.$ Given feasibility, the problem clearly is solvable.
We find its optimal solution

$\\{\overline{\rho},\overline{G}^{k}_{s},\overline{H}^{k}_{s},\overline{\lambda}^{k}:1\leq
k\leq K,1\leq s\leq S\\}$

(note that $\overline{\rho}\geq\underline{\rho}$) and set
$\overline{E}_{k}=\underline{R}^{T}\left[\sum_{j}\overline{\lambda}^{k}_{j}{P_{j}P_{j}^{T}}\right]^{-1}\underline{R}$,
thus arriving at the feasible solution

(126)
$\\{\overline{\rho},\underline{R},\overline{G}^{k}_{s},\overline{H}^{k}_{s},\overline{E}_{k},\overline{\lambda}^{k}:1\leq
k\leq K,1\leq s\leq S\\}$

to (125).

  * •

We select somehow a convex compact set ${\beth[\underline{R}]}\subset{\beth}$
such that $\underline{R}\in{\beth[\underline{R}]}$, e.g.,
${\beth[\underline{R}]}=\\{R:\,|I_{n}-\underline{R}^{-1}R|\leq\gamma\\}$,
where $|\cdot|$ is the spectral norm, and $\gamma<1$ is a control parameter.

  * •

(II): We strengthen the “troublemaking constraints” $(a)$, $(b)$, and $(c)$ in
(125) to the convex constraints, namely,

$\begin{array}[]{cr}R\in{\beth[\underline{R}]}&(a^{\prime})\\\
\sum_{s}{G}^{k}_{s}\preceq\overline{E}_{k}^{-1}-\overline{E}_{k}^{-1}[E_{k}-\overline{E}_{k}]\overline{E}_{k}^{-1}&(b^{\prime})\\\
\sum_{s}{H}^{k}_{s}\preceq\underline{R}^{T}[P_{k}P_{k}^{T}]^{-1}\underline{R}+[R-\underline{R}]^{T}[P_{k}P_{k}^{T}]^{-1}\underline{R}+\underline{R}^{T}[P_{k}P_{k}^{T}]^{-1}[R-\underline{R}]&(c^{\prime})\end{array}$

Taking these constraints together with $(d)$, $(e)$, and $(f)$, we get a
system of convex constraints on the optimization variables of (125); for this
system, let it be called ${\cal S}[\underline{R}]$, (126) is a feasible
solution. Maximizing $\rho$ under the feasible system of convex constraints
${\cal S}[\underline{R}]$, we get a new feasible solution to (125), with the
value of the objective $\geq\underline{\rho}$. We now can iterate this process
and terminate it when the progress in the objective becomes small. We can also
benefit from running iterations from several selected at random starting
points.

####  C.2.2 Back to certifying robust stability

As applied to certifying robust stability, the construction we have just
presented deals with the case when the uncertainty set ${\cal U}$ is just an
uncertain matrix ${\cal A}$ with box uncertainty. Typically, the situation is
different – ${\cal U}$ is a shift of uncertain matrix by a given nominal
matrix $A_{\mathrm{nom}}$ which is stable — with spectral radius $<1$. Assume
we can certify the stability of $A_{\mathrm{nom}}$ by our machinery, that is,
can point out $R_{\mathrm{nom}}\in\beth$ and $\gamma<1$ such that with
$R=R_{\mathrm{nom}}$, every one of the $K$ the systems of constraints (cf.
(118))

$None$
$\begin{array}[]{l}\left[\begin{array}[]{c|c}G&\gamma^{-1}A_{\mathrm{nom}}\cr\hline\cr\gamma^{-1}A_{\mathrm{nom}}^{T}&{H}\cr\end{array}\right]\succeq
0,\left[\begin{array}[]{c|c}\sum_{j}\lambda_{j}{P_{j}P_{j}^{T}}&R\cr\hline\cr
R^{T}&{E}\cr\end{array}\right]\succeq 0,\\\ \lambda\geq
0,\,\sum_{j}\lambda_{j}=1,G\preceq E^{-1},\,H\preceq
R^{T}[P_{k}^{-T}P_{k}^{-1}]R,\end{array}$

in variables $G,H,\lambda,E$ is feasible.131313Indeed, when deriving (118), we
have seen that if $R$ is nonsingular then feasibility of each system
$(S_{k}[R])$, $k\leq K$, certifies the upper bound $\gamma$ on the robust norm
of the uncertain matrix $\\{\epsilon RA_{\mathrm{nom}}R^{-1}:|\epsilon|\leq
1\\}$, i.e., certifies that $\|RA_{\mathrm{nom}}R^{-1}\|_{{\cal X},{\cal
X}}\leq\gamma$. We can now try to minimize the (given by our machinery upper
bound on) the robust radius of the uncertain matrix $R{\cal A}R^{-1}$ over $R$
by successive convex approximation, starting with $R=R_{\mathrm{nom}}$ and
maintaining feasibility of all $K$ systems $(S_{k}[\cdot])$ along the
generated sequence of $R$’s. With this approach, after a number of steps of
SCA we get at our disposal a nonsingular matrix $R$ and an upper bound
$1/\rho$ on $\|R{\cal A}R^{-1}\|_{{\cal X},{\cal X}}$ such that we can certify
the relation $\|RA_{\mathrm{nom}}R^{-1}\|_{{\cal X},{\cal X}}\leq\gamma$. As a
result, we will know that for every $\varsigma\geq 0$ the quantity
$\max_{A}\left\\{\|RAR^{-1}\|_{{\cal X},{\cal
X}}:A=A_{\mathrm{nom}}+\sum_{s}\epsilon_{s}A_{s},\|\epsilon\|_{\infty}\leq\varsigma\right\\}$
is at most $\gamma+\varsigma/\rho$ and thus will be able to evaluate the
“uncertainty level” $\varsigma$ ensuring robust stability of the uncertain
dynamical system. Note that as SCA goes on, the quantity $1/\rho$ does not
increase, so that the conclusions on “admissible uncertainty level” can only
improve with time.

It remains to explain how we update the SCA procedure described above to make
it “proper”—to maintain feasibility of the systems $(S_{k}[R])$ along the
resulting trajectory of $R$’s. To this end note that if $\overline{R}\in\beth$
is such that the system $(S_{k}[\overline{R}])$ is feasible and $\overline{E}$
is $E$-component of a feasible solution to this system, then the system

$None$
$\begin{array}[]{l}R\in\beth[\overline{R}],\,\left[\begin{array}[]{c|c}G&\gamma^{-1}A_{\mathrm{nom}}\cr\hline\cr\gamma^{-1}A_{\mathrm{nom}}^{T}&{H}\cr\end{array}\right]\succeq
0,\,\left[\begin{array}[]{c|c}\sum_{j}\lambda_{j}{P_{j}P_{j}^{T}}&R\cr\hline\cr
R^{T}&{E}\cr\end{array}\right]\succeq 0,\lambda\geq
0,\,\sum_{j}\lambda_{j}=1,\\\ G\preceq
2\overline{E}^{-1}-\overline{E}^{-1}E\overline{E}^{-1},\,H\preceq\overline{R}^{T}[P_{k}^{-T}P_{k}^{-1}]R+R^{T}[P_{k}^{-T}P_{k}^{-1}]\overline{R}-\overline{R}^{T}[P_{k}^{-T}P_{k}^{-1}]\overline{R}\\\
\end{array}$

in variables $G,H,\lambda,E,R$ is feasible, and the $R$-component, $R$, of a
feasible solution to the system results in feasible system $(S_{k}[R])$. With
this in mind, to enforce properness of SCA, it suffices to act as follows:

  * •

start the entire SCA process with feasible solution to (125) (see (I)) where
$R=R_{\mathrm{nom}}$;

  * •

prior to executing rule (II), we find $E$-components $\widehat{E}_{k}$ of
feasible solutions to all $K$ systems $(S_{k}[\underline{R}])$, and augment
the design variables of ${\cal S}[\underline{R}]$ with design variables of all
$K$ systems of constraints $(T_{k}[\underline{R},\overline{E}_{k}])$, thus
arriving at the system ${\cal S}^{+}[\underline{R}]$ of constraints on the
extended family of variables. We replace in (II) maximizing $\rho$ under
constraints ${\cal S}[\underline{R}]$ with maximizing the same objective under
the constraints ${\cal S}^{+}[\underline{R}]$, and take the relevant
components of the optimal solution as new feasible solution to (125).

As it is immediately seen, these modifications indeed make SCA proper.

##  Appendix D Spectratopic case

###  D.1 Spectratopes

A basic spectratope is a bounded set ${\cal W}$ represented as

(127) ${\cal W}=\\{w\in{\mathbf{R}}^{p}:\exists t\in{\cal
T}:T_{k}^{2}[w]\preceq t_{k}I_{d_{k}},1\leq k\leq K\\}$

where

$T_{k}[w]=\sum_{i=1}^{p}w_{i}T_{ki}$

is a linear mapping from ${\mathbf{R}}^{p}$ to ${\mathbf{S}}^{d_{k}}$ (so that
$T_{ki}$ are symmetric $d_{k}\times d_{k}$ matrices), and ${\cal T}$ is as in
the definition of a basic ellitope.

A spectratope is a set ${\cal X}$ represented as the linear image of a basic
spectratope ${\cal W}$:

$\begin{array}[]{c}{\cal X}=P{\cal W}=\\{x\in{\mathbf{R}}^{n}:\exists
w\in{\cal W}:x=Pw\\},\\\ {\cal W}=\Big{\\{}w\in{\mathbf{R}}^{p}:\exists
t\in{\cal T}:\Big{[}{\sum}_{i}w_{i}T_{ki}\Big{]}^{2}\preceq
t_{k}I_{d_{k}},k\leq K\Big{\\}}\end{array}$

We refer to $D=\sum_{k=1}^{K}d_{k}$ as spectratopic dimension of ${\cal W}$.

Same as ellitopes, spectratopes are convex compact sets symmetric w.r.t. the
origin; a basic spectratope, in addition, has a nonempty interior.

##### Examples

First of all, every ellitope is a spectratope. Indeed, it suffices to consider
the case when the ellitope ${\cal W}$ in question is the basic ellitope (2).
In this case, passing to eigenvalue decompositions of matrices $T_{k}$, we
have

$T_{k}=\sum_{i=1}^{\nu_{k}}e_{ki}e_{ki}^{T},\;\nu_{i}={\mathop{\hbox{\rm
Rank}}}(T_{k}),$

whence

$\begin{array}[]{rcl}{\cal W}&=&\\{w:\exists t\in{\cal T}:w^{T}T_{k}w\leq
t_{k},k\leq K\\}\\\ &=&\\{w:\exists\bar{t}=\\{t_{ki},i\leq\nu_{k},k\leq
K\\}\in\overline{{\cal T}}:[e_{ki}^{T}w]^{2}\preceq t_{ki}I_{1},\,1\leq
i\leq\nu_{k},k\leq K\\},\\\ \overline{{\cal T}}&:=&\Big{\\{}t_{ki}\geq
0:\,\Big{[}\sum_{i}t_{1i};...;\sum_{i}t_{Ki}\Big{]}\in{\cal
T}\Big{\\}}.\end{array}$

An example of a “genuine” basic spectratope is the unit $\|\cdot\|$-ball,
$\|\cdot\|$ being the spectral norm on ${\mathbf{R}}^{p\times q}$:

$\\{w\in{\mathbf{R}}^{p\times q}:\|w\|\leq 1\\}=\bigg{\\{}w:\exists t\in{\cal
T}[0,1]:T^{2}[w]:=\left[\begin{array}[]{c|c}&w\cr\hline\cr
w^{T}&\cr\end{array}\right]^{2}\preceq tI_{p+q}\bigg{\\}},$

Same as ellitopes, spectratopes admit fully algorithmic ”calculus,” and their
family is closed with respect to basic operations preserving convexity and
symmetry w.r.t. the origin, such as taking finite intersections, linear
images, inverse images under linear embedding, direct products, arithmetic
summation ( see [18, Section 4.6] for details); what is missing, is taking
convex hulls of finite unions.

####  D.1.1 Bounding maximum of quadratic form over a spectratope

Given a linear mapping

$R[w]={\sum}_{i=1}^{\nu}w_{i}R_{i}:{\mathbf{R}}^{\nu}\to{\mathbf{S}}^{d}$

so that $R_{i}\in{\mathbf{S}}^{d}$, we associate with it linear mappings

$\begin{array}[]{rclrcl}R^{+}[W]&=&\sum_{i,j=1}^{\nu}W_{ij}R_{i}R_{j}:\;{\mathbf{S}}^{\nu}\to{\mathbf{S}}^{d},&R^{+,*}[\Lambda]&=&\left[{\mathop{\hbox{\rm
Tr}}}(\Lambda
R_{i}R_{j})\right]_{i,j\leq\nu}:\;{\mathbf{S}}^{d}\to{\mathbf{S}}^{\nu}.\end{array}$

Note that

(128) $\displaystyle R^{+}[ww^{T}]$ $\displaystyle=$ $\displaystyle R^{2}[w]$

and

(129) $\displaystyle{\mathop{\hbox{\rm Tr}}}(R^{+}[W]\Lambda)$
$\displaystyle=$ $\displaystyle{\mathop{\hbox{\rm
Tr}}}(WR^{+,*}[\Lambda))\,\,\forall(W\in{\mathbf{S}}^{\nu},\Lambda\in{\mathbf{S}}^{d}).$

Given a collection $\Lambda=\\{\Lambda_{k}:,k\leq K\\}$ of symmetric matrices
(of, perhaps, different sizes), we set

$\lambda[\Lambda]=[{\mathop{\hbox{\rm
Tr}}}(\Lambda_{1});...;{\mathop{\hbox{\rm Tr}}}(\Lambda_{K})].$

Finally, same as above, for a convex compact set ${\cal T}$,

$\phi_{\cal T}(\lambda)=\max_{t\in{\cal T}}\lambda^{T}t$

is the support function of ${\cal T}$.

Given a spectratope

${\cal X}=P{\cal W},\,{\cal W}=\Big{\\{}w\in{\mathbf{R}}^{q}:\exists t\in{\cal
T}:T_{k}^{2}[w]:=\left[{\sum}_{i}w_{i}T_{ki}\right]^{2}\preceq
t_{k}I_{d_{k}},k\leq K\Big{\\}},$

an efficiently computable upper bound $\hbox{\rm Opt}(C)$ on the quantity

$\hbox{\rm Opt}_{*}(C)=\max_{x\in{\cal X}}x^{T}Cx$

can be built as follows. Assume that $\Lambda=\\{\Lambda_{k}\in{\cal
S}^{d_{k}}_{+},k\leq K\\}$ is such that

(130) $\displaystyle P^{T}CP\preceq\sum_{k}{T}_{k}^{+,*}[\Lambda_{k}].$

When $x\in{\cal X}$, there exists $w\in{\mathbf{R}}^{q}$ and $t\in{\cal T}$
such that (see (128))

$x=Pw\ \&\ T^{+}_{k}[ww^{T}]=T_{k}^{2}[w]\preceq t_{k}I_{d_{k}},\,k\leq K,$

whence

(131) $\displaystyle\sum_{k}{\mathop{\hbox{\rm
Tr}}}(T^{+}_{k}[ww^{T}]\Lambda_{k})\leq\sum_{k}t_{k}{\mathop{\hbox{\rm
Tr}}}(\Lambda_{k})\leq\phi_{{\cal T}}(\lambda[\Lambda]).$

On the other hand, by (129) we have

(132) $\displaystyle{\mathop{\hbox{\rm
Tr}}}(T_{k}^{+}[ww^{T}]\Lambda_{k})={\mathop{\hbox{\rm
Tr}}}(T_{k}^{+,*}[\Lambda_{k}][ww^{T}])=w^{T}T_{k}^{+,*}[\Lambda_{k}]w,$

so that

$x^{T}Cx=w^{T}[P^{T}CP]w\underbrace{\leq}_{\hbox{[by
~{}(\ref{(a)})}]}w^{T}\left[{\sum}_{k}T_{k}^{+,*}[\Lambda_{k}]\right]w\leq\phi_{{\cal
T}}(\lambda[\Lambda])$

due to (132) and (131). As a result, the efficiently computable convex
function

$\hbox{\rm Opt}(C)=\min\limits_{\Lambda}\left\\{\phi_{{\cal
T}}(\lambda[\Lambda]):\Lambda=\\{\Lambda_{k}\in{\mathbf{S}}^{d_{k}}_{+},k\leq
K\\},P^{T}CP\preceq{\sum}_{k}T_{k}^{+,*}[\Lambda_{k}]\right\\}$

is an upper bound on $\hbox{\rm Opt}(C)$. It is known ([18, Proposition 4.8])
that this bound is reasonably tight:

$\hbox{\rm Opt}_{*}(C)\leq\hbox{\rm Opt}(C)\leq 2\ln(2D)\hbox{\rm
Opt}_{*}(C),\;\;D={\sum}_{k}d_{k}.$

###  D.2 Bounding operator norms, spectratopic case

Similarly to the ellitopic case, our problem of interest is tight
computationally efficient upper-bounding of the norm

$\|A\|_{{\cal B},{\cal X}}=\max_{x\in{\cal X}}\|Ax\|_{{\cal
B}}=\max\limits_{[y;x]\in{\cal B}_{*}\times{\cal
X}}[y;x]^{T}\left[\begin{array}[]{c|c}&{1\over 2}A\cr\hline\cr{1\over
2}A^{T}&\cr\end{array}\right][y;x]$

in the case when ${\cal X}$ and ${\cal B}_{*}$ are spectratopes:

(133) $\begin{array}[]{rcl}{\cal X}&=&P{\cal
W}=\\{x\in{\mathbf{R}}^{n}:\exists w\in{\cal W}:x=Pw\\},\,{\cal
W}=\\{w\in{\mathbf{R}}^{p}:\exists t\in{\cal T}:T_{k}^{2}[w]\preceq
t_{k}I_{d_{k}},k\leq K\\}\\\ {\cal B}&=&\\{v\in{\mathbf{R}}^{m}:v^{T}y\leq
1\,\forall y\in{\cal B}_{*}\\}\end{array}$

where

(134) $\begin{array}[]{rcl}{\cal B}_{*}&=&\\{y\in{\mathbf{R}}^{m}:y^{T}v\leq
1\,\forall v\in{\cal B}\\}=Q{\cal Z}=\\{y\in{\mathbf{R}}^{m}:\exists z\in{\cal
Z}:y=Qz\\},\\\ {\cal Z}&=&\\{z\in{\mathbf{R}}^{q}:\exists s\in{\cal
S}:S_{\ell}^{2}[z]\preceq s_{\ell}I_{g_{\ell}},\ell\leq L\\}.\end{array}$

In this case the efficiently computable upper bound on $\|a\|_{{\cal B},{\cal
X}}$ and its tightness are given by the following result (which is an
improvement of the just cited result from [18]):

######  Theorem D.1.

In the case of  (133),  (134), the efficiently computable convex function of
$A$ given by

(135) $\hbox{\rm Opt}(A)=\min\limits_{\Lambda,\Upsilon}\left\\{\phi_{{\cal
T}}(\lambda[\Lambda])+\phi_{{{\cal
S}}}(\lambda[\Upsilon]):\begin{array}[]{l}\Lambda=\\{\Lambda_{k}\in{\mathbf{S}}^{d_{k}}_{+},k\leq
K\\},\Upsilon=\\{\Upsilon_{\ell}\in{\mathbf{S}}^{g_{\ell}}_{+},\ell\leq
L\\}\\\
\left[\begin{array}[]{c|c}\sum_{\ell}S_{\ell}^{+,*}[\Upsilon_{\ell}]&{1\over
2}Q^{T}AP\cr\hline\cr{1\over
2}P^{T}A^{T}Q&\sum_{k}T_{k}^{+,*}[\Lambda_{k}]\cr\end{array}\right]\succeq
0\\\ \end{array}\right\\}$

is a reasonably tight upper bound on $\|A\|_{{\cal B},{\cal X}}$:

(136) $\|A\|_{{\cal B},{\cal X}}\leq\hbox{\rm Opt}(A)\leq
2\sqrt{\ln(5G)\ln(5D)}\|A\|_{{\cal B},{\cal
X}},\;\;G=\sum_{\ell}g_{\ell},\;D=\sum_{k}d_{k}.$

Proof. The left inequality in (136) is evident. Let us prove the right
inequality. Let $q$, $p$ be the dimensions of the embedding spaces of ${\cal
Z}$ and ${\cal W}$, and assume that $q\leq p$, which is w.l.o.g. for the same
reasons as in the ellitopic case. Same as in the latter case, (135) is nothing
but the conic problem

$\hbox{\rm
Opt}(A)=\min\limits_{\Lambda,\Upsilon,\tau,\rho}\left\\{\tau+\rho:\begin{array}[]{l}\Lambda=\\{\Lambda_{k}\in{\mathbf{S}}^{d_{k}}_{+},k\leq
K\\},{[-\lambda[\Lambda];\tau]}\in{\mathfrak{T}}_{*}\\\
\Upsilon=\\{\Upsilon_{\ell}\in{\mathbf{S}}^{g_{\ell}}_{+},\ell\leq
L\\},[-\lambda[\Upsilon];\rho]\in{\mathfrak{{S}}}_{*}\\\
\left[\begin{array}[]{c|c}\sum_{\ell}S_{\ell}^{+,*}[\Upsilon_{\ell}]&{1\over
2}Q^{T}AP\cr\hline\cr{1\over
2}P^{T}A^{T}Q&\sum_{k}T_{k}^{+,*}[\Lambda_{k}]\cr\end{array}\right]\succeq
0\\\ \end{array}\right\\}$

with the same cones $\mathfrak{T}$, $\mathfrak{{S}}$ and their duals
${\mathfrak{T}}_{*}$, ${\mathfrak{{S}}}_{*}$ as in the ellitopic case. Same as
in that case, the latter problem is strictly feasible and bounded, and by
Conic Duality one has

$\begin{array}[]{rcl}&&\hbox{\rm Opt}(A)\\\
&=&\max\limits_{r,t,U,V,W}\left\\{{\mathop{\hbox{\rm
Tr}}}(W^{T}Q^{T}AP):\begin{array}[]{l}{S}^{+}_{\ell}[U]\leq
s_{\ell}I_{g_{\ell}}\,\forall\ell,{T}^{+}_{k}[V]\leq t_{k}I_{d_{k}}\,\forall
k\\\ t\in{\cal T},s\in{\cal S},\,\left[\begin{array}[]{c|c}U&W\cr\hline\cr
W^{T}&V\cr\end{array}\right]\succeq 0\\\ \end{array}\right\\}\\\
&=&\max\limits_{r,t,U,V,Y}\left\\{{\mathop{\hbox{\rm
Tr}}}([U^{1/2}YV^{1/2}]^{T}Q^{T}AP):\begin{array}[]{l}s\in{\cal S},t\in{\cal
T},U\succeq 0,V\succeq 0,Y^{T}Y\preceq I\cr{S}^{+}_{\ell}[U]\leq
s_{\ell}I_{g_{\ell}}\,\forall\ell,\;aic{S}{T}^{+}_{k}[V]\leq
t_{k}I_{d_{k}}\,\forall k\\\ \end{array}\right\\}\\\
&=&\max\limits_{r,t,U,V}\left\\{\sum_{i=1}^{q}\sigma_{i}(U^{1/2}Q^{T}APV^{1/2}):\begin{array}[]{l}{S}^{+}_{\ell}[U]\leq
s_{\ell}I_{g_{\ell}}\,\forall\ell,\;{T}^{+}[V]\leq t_{k}I_{d_{k}}\forall k\\\
U\succeq 0,\,V\succeq 0,\,s\in{\cal S},\,t\in{\cal T}\end{array}\right\\}\\\
\end{array}$

(cf. item 1o in the “ellitopic proof”).

##### 2o

The concluding optimization problem in the above chain clearly is solvable;
let $U,V,r,t$ be the optimal solution, and
$\sum_{\iota=1}^{q}\sigma_{\iota}e_{\iota}f_{\iota}^{T}$ be the singular value
decomposition of $U^{1/2}Q^{T}APV^{1/2}$, so that

(137) $\begin{array}[]{rcl}\hbox{\rm
Opt}(A)&=&\sum_{\iota=1}^{q}\sigma_{\iota}\\\
U^{1/2}Q^{T}APV^{1/2}&=&\sum_{\iota=1}^{q}\sigma_{\iota}e_{\iota}f_{\iota}^{T}\\\
e_{i}^{T}e_{j}&=&\left\\{\begin{array}[]{ll}1,&i=j\\\ 0,&i\neq
j\cr\end{array}\right.,i,j\leq q\ \&\
f_{i}^{T}f_{j}=\left\\{\begin{array}[]{ll}1,&i=j\\\ 0,&i\neq
j\cr\end{array}\right.,i,j\leq p.\end{array}$

Let $\epsilon_{1},...,\epsilon_{p}$ be independent random variables taking
values $\pm 1$ with probabilities 1/2, and let

$\xi={\sum}_{i=1}^{q}\epsilon_{i}e_{i},\;\;\;\eta={\sum}_{j=1}^{p}\epsilon_{j}f_{j}.$

Then, in view of (137) it holds, identically in $\epsilon_{i}=\pm 1$, $1\leq
i\leq p$:

(138) $\xi^{T}U^{1/2}Q^{T}APV^{1/2}\eta={\sum}_{i,\iota\leq q,j\leq
p}[\epsilon_{i}\epsilon_{j}\sigma_{\iota}e_{i}^{T}e_{\iota}f_{\iota}^{T}f_{j}]={\sum}_{\iota=1}^{q}\sigma_{\iota}=\hbox{\rm
Opt}(A).$

On the other hand, setting $E=[e_{1},...,e_{q}]$, we get an orthonormal
$q\times q$ matrix such that $\xi=E\underline{\epsilon}$, where
$\underline{\epsilon}=[\epsilon_{1};...;\epsilon_{q}]$ is a Rademacher vector.
Now let $\widehat{\xi}=U^{1/2}\xi=U^{1/2}E\underline{\epsilon}$. Observe that
for every $\ell\leq L$ and for properly selected matrices $\overline{S}_{\ell
i}\in{\mathbf{S}}^{g_{\ell}}$ we have

$S_{\ell}[U^{1/2}Ey]={\sum}_{i=1}^{q}\overline{S}_{\ell i}y_{i},\,\forall
y\in{\mathbf{R}}^{q}.$

We have

${\mathbf{E}}\\{\widehat{\xi}\widehat{\xi}^{T}\\}={\mathbf{E}}\\{U^{1/2}E\underline{\epsilon}\underline{\epsilon}^{T}E^{T}U^{1/2}\\}=U^{1/2}E{\mathbf{E}}\\{\underline{\epsilon}\underline{\epsilon}^{T}\\}E^{T}U^{1/2}=U^{1/2}EE^{T}U^{1/2}=U,$

whence

${\mathbf{E}}\left\\{S_{\ell}^{2}[\widehat{\xi}]\right\\}=S^{+}_{\ell}[{\mathbf{E}}\\{\widehat{\xi}\widehat{\xi}^{T}\\}]=S^{+}_{\ell}[U]\preceq
s_{\ell}I_{g_{\ell}}\;\forall\ell\leq L$

(we have used (128)). On the other hand,

$S_{\ell}[\widehat{\xi}]=S_{\ell}[U^{1/2}E\underline{\epsilon}]={\sum}_{i=1}^{q}\overline{S}_{\ell
i}\epsilon_{i},$

so $\sum_{i=1}^{q}\overline{S}_{\ell
i}^{2}={\mathbf{E}}\left\\{S_{\ell}^{2}[\widehat{\xi}]\right\\}$, and we end
up with

${\sum}_{i=1}^{q}\overline{S}_{\ell i}^{2}\preceq s_{\ell}I_{g_{\ell}}.$

Applying the noncommutative Khintchine inequality141414Noncommutative
Khintchine Inequality due to Lust-Piquard, Pisier, and Buchholz, see [39,
Theorem 4.6.1], states that if $Q_{i}\in{\mathbf{S}}^{n}$, $1\leq i\leq I$,
and $\xi_{i}$, $i=1,...,I$, are independent Rademacher or ${\cal N}(0,1)$
random variables, then for all $t\geq 0$ one has  $\hbox{\rm
Prob}\left\\{\left|{\sum}_{i=1}^{I}\xi_{i}Q_{i}\right|\geq t\right\\}\leq
2n\exp\left\\{-{t^{2}\over 2\left|{\sum}_{i=1}^{I}Q_{i}^{2}\right|}\right\\}$
where $|\cdot|$ is the spectral norm. we conclude that

$\forall\theta>0:\hbox{\rm
Prob}\\{S_{\ell}^{2}[\widehat{\xi}]\preceq\theta^{2}s_{\ell}I_{g_{\ell}}\\}=1-\hbox{\rm
Prob}\Big{\\{}\Big{|}{\sum}_{i}\overline{S}_{\ell
i}\epsilon_{i}\Big{|}>\theta\sqrt{s_{\ell}}\Big{\\}}\geq
1-2d_{\ell}\exp\big{\\{}-\mbox{\small$\frac{1}{2}$}\theta^{2}\big{\\}}.$

As a result, when setting $\theta=\sqrt{2\ln(5G)}$ we get

$\hbox{\rm Prob}\\{S_{\ell}^{2}[\widehat{\xi}]\preceq
2\ln(5G)s_{\ell}I_{d_{\ell}},\ell\leq L\\}>1/2,$

and

$\hbox{\rm Prob}\big{\\{}\|QU^{1/2}\xi\|_{{\cal
B}_{*}}\leq\sqrt{2\ln(5G)}\big{\\}}\geq\hbox{\rm
Prob}\\{S_{\ell}^{2}[\widehat{\xi}]\preceq
2\ln(5G)s_{\ell}I_{d_{\ell}},\ell\leq L\\}>1/2.$

By similar reasoning,

$\hbox{\rm Prob}\\{\|PV^{1/2}\eta\|_{\cal X}\leq\sqrt{2\ln(5D)}\\}>1/2.$

As a result, there exists realization $(\bar{\xi},\bar{\eta})$ of $(\xi,\eta)$
such that

$\|QU^{1/2}\bar{\xi}\|_{{\cal
B}_{*}}\leq\sqrt{2\ln(5G)}\;\&\;\|PV^{1/2}\bar{\eta}\|_{{\cal
X}}\leq\sqrt{2\ln(5D)}.$

On the other hand, invoking (138),

$\hbox{\rm
Opt}(A)=\bar{\xi}^{T}U^{1/2}Q^{T}APV^{1/2}\bar{\eta}\leq\|QU^{1/2}\bar{\xi}\|_{{\cal
B}*}\|PV^{1/2}\bar{\eta}\|_{\cal X}\|A\|_{{\cal B},{\cal X}}.$

Combining our observations, we conclude that

$\square$ $\hbox{\rm Opt}(A)\leq 2\sqrt{\ln(5G)\ln(5D)}\|A\|_{{\cal B},{\cal
X}}.$

###  D.3 Bounding robust norms of uncertain matrices, spectratopic case

Let spectratopes ${\cal X}\subset{\mathbf{R}}^{n}$, ${\cal
B}_{*}\subset{\mathbf{R}}^{m}$ with nonempty interiors and the polar ${\cal
B}$ of ${\cal B}_{*}$ be given by (133). Our goal is to conceive a
computationally efficient upper-bounding of the robust norm

$\|{\cal A}\|_{{\cal B},{\cal X}}=\max\limits_{A\in{\cal A}}\|A\|_{{\cal
B},{\cal X}}$

of uncertain matrix

${\cal A}=\Big{\\{}{\sum}_{s}\epsilon_{s}A_{s}:\|\epsilon\|_{\infty}\leq
1\Big{\\}}\subset{\mathbf{R}}^{m\times n}.$

##### Processing the problem

Acting exactly as in the ellitopic case, with the results of Section D.1.1 in
the role of their “ellitopic counterparts” from Section 2.2, we conclude that
the efficiently computable quantity

(139) $\hbox{\rm
Opt}:=\min\limits_{\Lambda,\Upsilon,\atop\\{G_{s},H_{s}\\}}\left\\{\phi_{{\cal
S}}(\lambda[\Lambda])+\phi_{{\cal
T}}(\lambda[\Upsilon]):\begin{array}[]{l}\left[\begin{array}[]{c|c}G_{s}&{1\over
2}Q^{T}A_{s}P\cr\hline\cr{1\over
2}P^{T}A_{s}^{T}Q&H_{s}\cr\end{array}\right]\succeq 0,i\leq N\\\
\Lambda=\\{\Lambda_{\ell}\in{\mathbf{S}}^{g_{\ell}}_{+},\ell\leq
L\\},\,\sum_{s}G_{s}\preceq\sum_{\ell}{\cal S}_{\ell}^{*}[\Lambda_{\ell}]\\\
\Upsilon=\\{\Upsilon_{k}\in{\mathbf{S}}^{d_{k}}_{+},k\leq
K\\},\,\sum_{s}H_{s}\preceq\sum_{k}{\cal
T}_{k}^{*}[\Upsilon_{k}]\end{array}\right\\}$

—the “spectratopic analog” of (103)—is an upper bound on $\|{\cal A}\|_{{\cal
B},{\cal X}}$ such that for properly selected matrices
$X\in{\mathbf{S}}^{p}_{+}$, $Y\in{\mathbf{S}}^{q}_{+}$ and $s\in{\cal S}$,
$t\in{\cal T}$ one has

${\cal S}_{\ell}[Y]\preceq s_{\ell}I_{g_{\ell}},\,\ell\leq L,\ \&{\cal
T}_{k}[X]\preceq t_{k}I_{d_{k}},\,k\leq K,$

and for the norms $\pi(\cdot)$ and $\rho(\cdot)$ with unit balls ${\cal W}$
and ${\cal Z}$, respectively, and $[\eta;\xi]\sim{\cal
N}(0,\mathrm{Diag}\\{Y,X\\})$,

(140) $\hbox{\rm Opt}\leq\vartheta(2\kappa)\|{\cal A}\|_{{\cal B},{\cal
X}}{\mathbf{E}}\\{\rho(\eta)\pi(\xi)\\}=\vartheta(2\kappa)\|{\cal A}\|_{{\cal
B},{\cal
X}}{\mathbf{E}}\left\\{\pi(\xi)\right\\}{\mathbf{E}}\left\\{\rho(\eta)\right\\}$

where $\kappa$ is the maximum of ranks of $A_{s}$ and $\vartheta(\cdot)$ is
given by (29) (cf.(104)).

We have the following spectratopic analog of Lemma A.2.

######  Lemma D.2.

Let

${\cal V}=\\{v\in{\mathbf{R}}^{d}:\exists r\in{\cal R}:R_{j}^{2}[v]\preceq
r_{j}I_{\nu_{j}},1\leq j\leq J\\}\subset{\mathbf{R}}^{d}$

be a basic spectratope, $W\succeq 0$ be symmetric $d\times d$ matrix such that

$\exists r\in{\cal R}:{\cal R}_{j}[W]\preceq r_{j}I_{\nu_{j}},j\leq J,$

and $\omega\sim{\cal N}(0,W)$. Denoting by $\rho(\cdot)$ the norm on
${\mathbf{R}}^{d}$ with the unit ball ${\cal V}$, we have

(141)
${\mathbf{E}}\\{\rho(\omega)\\}\leq\varkappa\left({\sum}_{j}\nu_{j}\right),\;\varkappa(F)=2\sqrt{2\ln(2F)}.\\\
$

Proof. Let $\zeta\sim{\cal N}(0,I_{d})$. When setting

$None$
$\overline{R}_{j}[z]=R_{j}[W^{1/2}z]={\sum}_{i=1}^{d}\overline{R}_{ji}z_{j},$

we have

${\sum}_{i}\overline{R}_{ji}^{2}={\mathbf{E}}\\{\overline{R}_{j}^{2}[\zeta]\\}={\mathbf{E}}\\{R_{j}^{2}[W^{1/2}\zeta]\\}={\mathbf{E}}\\{{\cal
R}_{j}[W^{1/2}\zeta\zeta^{T}W^{1/2}]\\}={\cal R}_{j}[W]\preceq
r_{j}I_{\nu_{j}}.$

Hence for every $\gamma>0$

$\begin{array}[]{rcl}\hbox{\rm
Prob}\left\\{R_{j}^{2}[\omega]\preceq\gamma^{2}r_{j}I_{\nu_{j}}\right\\}&=&\hbox{\rm
Prob}\left\\{\overline{R}_{j}^{2}[\zeta]\preceq\gamma^{2}r_{j}I_{\nu_{j}}\right\\}=1-\hbox{\rm
Prob}\left\\{\big{|}\sum_{i}\zeta_{i}\overline{R}_{ji}\big{|}>\gamma\sqrt{r_{j}}\right\\}\\\
&\geq&1-2\nu_{j}\exp\\{-\gamma^{2}/2\\},\\\ \end{array}$

with the concluding $\geq$ given by $\sum_{i}\overline{R}_{ji}^{2}\preceq
r_{j}I_{\nu_{j}}$ combined with the noncommutative Khintchine inequality. As a
result,

$\hbox{\rm Prob}\\{\rho(\omega)>\gamma\\}\leq 1-\hbox{\rm Prob}\left\\{\exists
j:R_{j}^{2}[\omega]\preceq\gamma^{2}r_{j}I_{\nu_{j}}\right\\}\leq\Big{[}{\sum}_{j}2\nu_{j}\Big{]}\exp\\{-\gamma^{2}/2\\}.$

Therefore, when setting $F=\sum_{j}\nu_{j}$ we obtain

$\square$
${\mathbf{E}}\\{\rho(\omega)\\}\leq\int_{0}^{\infty}\min\left[1,2F\exp\\{-\gamma^{2}/2\\}\right]d\gamma\leq
2\sqrt{2\ln(2F)}.$

Applying the lemma to ${\cal V}={\cal W}$, $W=X$, and to ${\cal V}={\cal Z}$,
$W=Y$, we get from (140) the following analog of Proposition 4.1:

######  Proposition D.3.

In the situation described in the beginning of this section, assuming that
ranks of all $A_{s}$ are $\leq\kappa$, the efficiently computable quantity Opt
as given by (139) is a reasonably tight upper bound on the robust norm
$\|{\cal A}\|_{{\cal B},{\cal X}}$ of uncertain matrix ${\cal A}$,
specifically,

(142) $\|A\|_{{\cal B},{\cal X}}\leq\hbox{\rm
Opt}\leq\varkappa({\sum}_{k}d_{k})\varkappa({\sum}_{\ell}g_{\ell})\vartheta(2\kappa)\|A\|_{{\cal
B},{\cal X}}$

where $\varkappa(\cdot)$ is given by (141) and $\vartheta(\cdot)$, given by
(29), satisfies

$\vartheta(1)=1,\,\vartheta(2)={\pi\over
2},\,\vartheta(4)=2,\,\vartheta(k)\leq\pi\sqrt{k}/2.$