Define the random variable \begin{align*} A=a_1^2\mathbf{a}\mathbf{a}^* \end{align*} where $\mathbf{a}\in\mathbb{c}^n$ is a random vector distributed as $\mathcal{N}(0,\mathbf{I}/2)+i\mathcal{N}(0,\mathbf{I}/2)$ and $a_1$ is the first entry of $\mathbf{a}$. Now let $\mathbf{A}_r$ for $r=1,2,\ldots,m$ be i.i.d. samples from $\mathbf{A}$. I'm interested in showing that \begin{align*} \\frac{1}{m}\sum_{r=1}^m\mathbf{A}_r\mathbb{E}[\mathbf{A}]\\le \delta \end{align*} with high probability for a small constant $\delta$ as long as $m\ge c(\delta)n$. Here, $\\cdot\$ denotes the spectral norm. Note that I am interested in establishing the result for $m\ge c(\delta)n$. I already know how to establish this result for $m\ge c(\delta)n(\log n)^3$ by using a truncation argument.
1 Answer
$\begingroup$
$\endgroup$
3
Your question looks very similar to Mark Rudelson's inequality. Rudelson's inequality bounds the deviation of rankone matrices/operators under the spectral norm.
For some nice applications of the inequality, see also Sampling from Matrices.
There is a rapidly growing line of research on the field, see Tropp's (beautiful) paper J. Tropp

$\begingroup$ Thanks, I am familiar with all of these references. In some sense all of them require that the matrices are bounded. Hence, one has to apply truncation first. This is where I loose the log factors. $\endgroup$– mohiMar 24, 2014 at 17:25

$\begingroup$ I see. Your bound O(n (log n)^3) is tight up to a (logn)^2 factor for general rankone samples. What are you shooting for? O(n) number of samples? $\endgroup$– zouziasMar 25, 2014 at 8:41

$\begingroup$ I can now actually do o(nlog^2 n) by truncation I think. I would like o(n) but I would actually be happy with an argument that gives o(nlog n) $\endgroup$– mohiMar 26, 2014 at 17:45