2
$\begingroup$

Given $y \sim N(0,\sigma^2 I)$, and $M$ that is a symmetric matrix (not necessarily idempotent)

  • what is the distribution of ${y^T M y}$?
  • is there a high probability bound on $|{y^T M y}|$?

Most bounds that I could find, such as in http://www2.econ.iastate.edu/classes/econ500/hallam/documents/QUAD_NORM.pdf hold only when $M$ is idempotent.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

By the spectral decomposition of $M$, the distribution of $y^T My$ is the same as that of $\sum_i\sigma^2\mu_i Z_i^2$, where the $\mu_i$'s are the eigenvalues of $M$ and the $Z_i$'s are iid standard normal random variables (r.v.'s). By rescaling, without loss of generality $\sigma=1$.

In the paper by Székely & Bakirov, exact lower and upper bounds on the cumulative distribution function of quadratic forms $Q:=y^T My$ are given. In particular, it is shown that $$\inf_{n\ge1,M\ge0,EQ=1}P(Q\le x)= \inf_{n\ge1}P(\chi^2_n/n\le x)=P(\chi^2_{n(x)}/n(x)\le x), $$ where $x>0$, $n(x)$ depends explicitly and only on $x$, and $\chi^2_n$ is a r.v. with the chi-squared distribution with $n$ degrees of freedom.

Among other results, it is also shown in that paper that $$\sup_{M\ge0,EQ=1}P(Q\le x)=P(\chi^2_n/n\le x)I\{x\ge y(n)\} +s(x)I\{1\le x<y(n)\}+P(\chi^2_1\le x)I\{x<1\}, $$ where $I$ is the indicator, $x>0$, $y(n)$ depends explicitly and only on $n$, and $$s(x):=\sup_{0\le\mu\le1/2}P(\mu Z_1^2+(1-\mu)Z_2^2\le x). $$

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you, that was very useful! Maybe I'm totally wrong but from my initial reading it seems like the paper you shared may not have a simple closed form expression for these tail bounds. Or is there one? I'm not looking for something very nuanced or tight. My own attempt at this based on your answer is to treat $\sum_i \mu_i Z_i^2$ as a sub-exponential distribution with parameters $\nu$ and $b$ that (roughly?) scale as $\sum \mu_i^2$ and $\max \mu_i^2$ and mean $\sum_i \mu_i$. Would anything go wrong with this technique? $\endgroup$
    – Enigman
    Mar 8, 2019 at 21:50
  • $\begingroup$ I am not sure if quite understand your comment. You might want to try to state it as a separate MO question. $\endgroup$
    – Iosif Pinelis
    Mar 10, 2019 at 0:21
  • $\begingroup$ I meant to ask if there would be anything wrong in applying a standard tail bound on sums of sub-exponential variables on $\sum_i \mu_i Z_i^2$ to get a simple closed form expression of the tail bound, since the paper you cited did not seem to have a simple closed form expression. But sure, I'll probably ask this as a separate question. $\endgroup$
    – Enigman
    Mar 10, 2019 at 8:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .