5
$\begingroup$

Let $X_{ij}$ be independent (but not identically distributed) real-valued random variables for $1\leq i\leq j\leq n.$ Let $X$ be the symmetric matrix whose entries are given by $X_{ij}.$ Let \begin{eqnarray} A & = \big|\big|X\big|\big|~, \\ B & = \mathbb{E}\big|\big|X\big|\big|~, \\ C & = \big|\big|\mathbb{E}X\big|\big|~. \end{eqnarray}

Concentration of measure typically quantifies the deviation $|A-B|.$ I am interested in general results that quantify the deviation $|A-C|.$ Please make any assumptions you need. I am trying to understand the main techniques that help in this problem.

EDIT: Specifically, suppose that $X_{ij}$ are non-negative with means $0 < \mathbb{E}X_{ij}<1.$ What kinds of bounds on the tail distribution of these random variables can help prove a bound on the deviation $|A-C|.$ For instance, a bound on the variance of each $X_{ij}$ or a sub-Gaussian bound on the tail of $X_{ij}.$

$\endgroup$
5
  • $\begingroup$ Typically I thought these results prove: $E\|X-E[X]\| \le$ style results; see e.g., users.cms.caltech.edu/~jtropp/books/Tro15-Expected-Norm.pdf $\endgroup$
    – Suvrit
    Commented Aug 9, 2015 at 18:14
  • 1
    $\begingroup$ I'm not sure why you'd expect useful estimates. If the $X_{ij}$ have expectation 0 but variance 1, then $C=0$, whereas $A$ is of the order $n^{n/2}$. $\endgroup$ Commented Aug 9, 2015 at 18:21
  • $\begingroup$ Thanks Anthony. I edited the question to clarify what I meant. $\endgroup$
    – Hedonist
    Commented Aug 9, 2015 at 20:23
  • $\begingroup$ @Hedonist: Since you work with $|A-C|$, can't you use the triangle inequality to turn it into the form mentioned in my comment, and then use that literature of results? $\endgroup$
    – Suvrit
    Commented Aug 9, 2015 at 20:34
  • $\begingroup$ Thanks for your comments Suvrit. I can use Weyl's inequality to deduce that $||X-EX||\geq \big|||X||-E||X||\big|.$ However, I am looking for bounds on $P(||X||-E||X||\geq t),$ perhaps exponentially sharp. Using your suggested bound and Markov's inequality is not strong enough for my purposes. Can you point me to literature which provides exponential tail probabilities (making suitable assumptions on the tails of $X_{ij}$)? $\endgroup$
    – Hedonist
    Commented Aug 9, 2015 at 21:47

1 Answer 1

1
$\begingroup$

The following paper: "Concentration of norms and eigenvalues of matrices" by M. Meckes (who is active on MO) seems answer the question. In particular, theorem 1 of that paper proves an inequality of the type requested in the comments above (it proves something more general, but I have not checked if all the conditions in the OP hold).

$\endgroup$
3
  • $\begingroup$ Suvrit: It appears this paper too deals with the question of how concentrated $||X||$ is to its median. I am interested in showing it is close to $||\mathbb{E}X||.$ This will need some stringent constraint on the tails of the entries, and will not happen under such minimal assumptions as in the paper you provide. $\endgroup$
    – Hedonist
    Commented Aug 11, 2015 at 12:56
  • $\begingroup$ Ok, I just read the "where M is any median..." part in the paper, and thought it should be easy to extrapolate. But as you say, maybe not! Though is it $\|E X\|$ or $E \|X\|$, or both? $\endgroup$
    – Suvrit
    Commented Aug 11, 2015 at 13:48
  • $\begingroup$ On reading your question again, I see that you are indeed after $\|EX\|$... $\endgroup$
    – Suvrit
    Commented Aug 11, 2015 at 13:54

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.