Upper bound for conditional expectation of spectral norm I am trying to understand an upper bound in the paper of Zhang et al.. This step is directly before equation (5.7) without any explanation. I even found the exact same step in two other papers without any explanation as well.
For a random matrix $C$ and a random vector $x$ the equation states
$$ \mathbb{E}[||(I-\mathbb{1}\mathbb{1}^T/N)C x||^2|\mathcal{F}] =
 \mathbb{E}[x^T \cdot(C^T(I-\mathbb{1}\mathbb{1}^T/N)C\cdot x |\mathcal{F}] $$
$$\leq ||\mathbb{E}[C^T(I-\mathbb{1}\mathbb{1}^T/N)C]|| \cdot \mathbb{E}[x^Tx|\mathcal{F}]$$
where $\mathbb{1}\in \mathbb{R}^N$ denotes the vector with every entry equal to 1, $I$ is the identity matrix, and $\mathcal{F}$ is a $\sigma$-algebra.
It holds:


*

*$C$ and $x$ are conditionally independent given $\mathcal{F}$

*$C$ is row stochastic

*$\mathbb{E}[C]$ is doubly stochastic
My approaches so far fail at two points. The first one is the conditional expectation, which I do not know how to get rid of in this step (the paper does not state that $C$ is independent of $\sigma(x, \mathcal{F})$). Even if this would hold, which leads to my second point, the norm is inside the expectation and taking it out would lead to a lower bound according to Jensen's inequality.
You can find the same step in the following papers:


*

*Suttle et al. on page 16

*Yan Zhang et al. on page 9 in Lemma IV.9
 A: This is what I got (ignore for now the conditional part of the expectations, and suppose $C,x$ are independent)
$$
\mathbb{E}[x^T \cdot C^T(I-\mathbb{1}\mathbb{1}^T/N)C\cdot x ] =
\mathbb{1}^T 
(\mathbb{E}[C^T(I-\mathbb{1}\mathbb{1}^T/N)C]\odot \mathbb{E}[xx^T ])
\mathbb{1}
$$
where $\odot$ is the Hadamard product.
$$
\mathbb{1}^T 
(\mathbb{E}[C^T(I-\mathbb{1}\mathbb{1}^T/N)C]\odot \mathbb{E}[xx^T ])
\mathbb{1}
\le n \|\mathbb{E}[C^T(I-\mathbb{1}\mathbb{1}^T/N)C] \|
\|\mathbb{E}[xx^T ] \|
$$
$$
\le n \|\mathbb{E}[C^T(I-\mathbb{1}\mathbb{1}^T/N)C] \|
\mathbb{E}[x^Tx ] 
$$
where $n$ is the size of the matrices, and in the last step we used Jensen
A: I found another hint to this equation in this paper in the proof including equation (18). The used statement is for any operator $\Psi$ which has an ONB of eigenvectors $\psi_n$ with corresponding eigenvalues $E_n$. Let the eigenvalues be ordered, i.e. $E_0 \leq E_1 \leq \cdots \leq E_N$. We can represent any vector $f$ in the Hilbert space by $f = \sum_n \langle \psi_n, f \rangle \psi_n$. From this we get
\begin{align*}
\langle f, \Psi f \rangle &= \sum_n \langle f, \Psi \psi_n \rangle \langle \psi_n, f \rangle = \sum_n E_n \langle f, \psi_n \rangle \langle \psi_n, f \rangle \\
& \leq E_N  \sum_n \langle f, \psi_n \rangle \langle \psi_n, f \rangle = E_N  \langle f,  f \rangle
\end{align*}
For my proof to work, I need to assume that $C$ is independent of $\sigma(x, \mathcal{F})$. This is still not optimal in my opinion. With this we get
\begin{align}
 \mathbb{E}[x^T \cdot (C^T(I- \mathbb{1}\mathbb{1}^T / N) C \cdot x | \mathcal{F}] &= \mathbb{E}[\mathbb{E}[x^T \cdot (C^T(I- \mathbb{1}\mathbb{1}^T / N) C) \cdot x | \sigma(x, \mathcal{F})] | \mathcal{F}] \\
&= \mathbb{E}[x^T \cdot \mathbb{E}[ (C^T(I- \mathbb{1}\mathbb{1}^T / N) C) | \sigma(x, \mathcal{F})]  \cdot x | \mathcal{F}] \\
&= \mathbb{E}[x^T \cdot \mathbb{E}[ (C^T(I- \mathbb{1}\mathbb{1}^T / N) C)]  \cdot x | \mathcal{F}] \\
& \leq ||\mathbb{E}[ (C^T(I- \mathbb{1}\mathbb{1}^T / N) C)] ||  \mathbb{E}[x^T  x | \mathcal{F}]. \\
\end{align}
Here I used the tower property of the conditional expectation for $\sigma(x, \mathcal{F}) \subset \mathcal{F}$. In the second step the $x$ could be taken out of the inner expectation, as it is $\sigma(x, \mathcal{F})$-measurable. The third step is possible due to the independence of $C$ to $\sigma(x, \mathcal{F})$. Finally, the result from above was used. Note that $\mathbb{E}[ (C^T(I- 11^T / N) C)]$ is a positive definite hermitian operator, therefore its largest eigenvalue is equal to the spectral norm.
