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
-
$\begingroup$ I'm also interested in calculating the same quantity when $\mathbf{A}=a_1^2\mathbf{a}\mathbf{a}^*$ $\endgroup$– mohiCommented Mar 17, 2014 at 6:10
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Your question looks very similar to Mark Rudelson's inequality. Rudelson's inequality bounds the deviation of rank-one 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$– mohiCommented Mar 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 rank-one samples. What are you shooting for? O(n) number of samples? $\endgroup$– zouziasCommented Mar 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$– mohiCommented Mar 26, 2014 at 17:45