Bounding max eigenvalue / operator norm of difference of random matrix and its expectation

176 Views Asked by At

Suppose that I have a unit vector $v \in \mathbb{R}^d$. Let $B = \theta vv^T + I_{d \times d}$, where $I_{d \times d}$ is a identity matrix. Now let $X$ be a random vector so that $\mathbb{E}X = 0$, $\mathbb{E}\left[XX^T \right] = B$, and $\|X\|_2 \leq K \sqrt{E\left[ X \right]^2_2}$ almost surely. Then clearly $B$ has eigenvalues $1$ and $\theta + 1$, and:

$$ E\left[ X \right]^2_2 = \text{Tr}(B) = d + \theta $$

My central question is as follows: How can I show that the operator norm (that is, the largest eigenvalue by absolute value) of the quantity: $$XX^T - B$$ is $\leq c_1(1 + \theta)$, where $c_1 \in \mathbb{R}$ is some constant factor? Is this even true? (that is, how can I show that $\|XX^T -B\|_{op} \leq c_1 (1 + \theta)$?)

Originally I had the bound of the operator norm of $XX^T - B$ as $$\max(K^2E\left[ X \right]^2_2 - 1, 1 + \theta) = \max(K^2 \text{Tr}(B) - 1, 1 + \theta) = \max(K^2 (d + \theta) - 1, 1 + \theta)$$

But I am not sure that this is tight. I chose this originally because the two matrices in the difference are clearly PSD/symmetric, so the max eigenvalue is either at most $\|X\|_2^2$ (which is the max eigenvalue of $XX^T$) minus $1$ or $\theta + 1$ in the other case (such as if $\|X\|_2^2 \leq 1 + \theta$ for example).