Upper bound for conditional expectation of spectral norm

Question

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

Answer 1

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

Answer 2

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.