5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I'm also interested in calculating the same quantity when $\mathbf{A}=a_1^2\mathbf{a}\mathbf{a}^*$ $\endgroup$
    – mohi
    Mar 17, 2014 at 6:10

1 Answer 1

1
$\begingroup$

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.

See Rudelson inequality

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

$\endgroup$
3
  • $\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$
    – mohi
    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$
    – zouzias
    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$
    – mohi
    Mar 26, 2014 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.