Eigenvalues of sums of random matrices
Say I have a sum of random Hermitian matrices 
. I’d like to know what the 
-th eigenvalue of 
tends to look like. In the case that the 
are positive-semidefinite, the upper and lower Chernoff tail bounds in User Friendly Tail Bounds bound the relative deviation of 
from 
and 
from 
respectively, so you might expect that 
tends to look like 
. However, it’s easy to see that this isn’t the case, even for 
and 
: assume 
has all eigenvalues equal to 
. Then it seems that an instance of is likely to have 
and 
. More formally, we expect the same results from Jensen's inequality.
To illustrate my point graphically, I took 
to be the first 
rows of an 
Fourier matrix; let 
refer to the 
-th column of , and take 
where 
are i.i.d Bernoulli(
) random variables. Then the eigenvalues of are the squares of the singular values of a matrix you get by tossing out each of the columns of independently with probability 
. On average, the singular values of this column subsampled version of are all 
, but you can see that empirically the extreme singular values do not cluster around (indicated by the red lines).
empirical singular value distribution of a column subsampled matrix with 30 orthogonal rows
It seems that whatever 
clusters around is comparable to from the bounds in User Friendly, but it’s not clear that one can’t do much better.
Possibly relevant posts:
- Full rankedness of random submatrices of orthogonal matrices (5/26/2010)
- The gist of the Laplace transform method for bounding eigenvalues of random matrices (8/27/2010)
- One direction in Khintchine’s inequality for Rademacher sums (9/26/2008)
be conformal matrices, then it’s clear that the matrix ![\displaystyle
[\text{Tr}(A_i^\star A_j)]_{i,j=1,\ldots,m}](/cz/latexrender/pictures/447ebb0cede930ab36d18ae80d5b5bbd.png "\displaystyle
[\text{Tr}(A_i^\star A_j)]_{i,j=1,\ldots,m}")
![\displaystyle
[\text{Tr}((A_i^\star A_j)^k)]_{i,j=1,\ldots,m}](/cz/latexrender/pictures/6bd9d8bdf32578d68ee0e08337a773d8.png "\displaystyle
[\text{Tr}((A_i^\star A_j)^k)]_{i,j=1,\ldots,m}")
![\displaystyle
\begin{gathered}
\sum\nolimits_{k=0}^\infty [ \text{Tr}((A_i^\star A_j)^k)]_{i,j=1,\ldots,m} = \\
\left[\text{Tr}\left(\sum\nolimits_{k=0}^\infty (A_i^\star A_j)^k \right)\right]_{i,j=1,\ldots,m} = \\
\left[\text{Tr}\left(I - A_i^\star A_j)^{-1} \right)\right]_{i,j=1,\ldots,m}
\end{gathered}](/cz/latexrender/pictures/80b18f241ccf1213f1c5f629b9243d99.png "\displaystyle
\begin{gathered}
\sum\nolimits_{k=0}^\infty [ \text{Tr}((A_i^\star A_j)^k)]_{i,j=1,\ldots,m} = \\
\left[\text{Tr}\left(\sum\nolimits_{k=0}^\infty (A_i^\star A_j)^k \right)\right]_{i,j=1,\ldots,m} = \\
\left[\text{Tr}\left(I - A_i^\star A_j)^{-1} \right)\right]_{i,j=1,\ldots,m}
\end{gathered}")
are scalars in the open unit disc. In that case, we are looking at the matrix![\displaystyle
\left[\frac{1}{1-A_i^\star A_j} \right]_{i,j=1,\ldots,m} = \sum_{k=0}^\infty [ (A_i^\star A_j)^k]_{i,j=1,\ldots,m}.](/cz/latexrender/pictures/27b993eef0f76eb2f40ad03a05751502.png "\displaystyle
\left[\frac{1}{1-A_i^\star A_j} \right]_{i,j=1,\ldots,m} = \sum_{k=0}^\infty [ (A_i^\star A_j)^k]_{i,j=1,\ldots,m}.")
. By the Schur Product Theorem (which states that the Hadamard product of two positive semidefinite matrices is positive semidefinite), we see that the matrix is positive semidefinite.
norm of a PSD matrix
?
, 
so that 
, and the spectral spread of the graph is given by the Ky-fan two norm. So whatever we know about Ky Fan norms can be used.
of norms:
is a norm 
is the convex indicator function of a set.
The spectral and trace norms are trace dual, so we have
are also symmetric. It follows that we can achieve the maximum over 
to be 0 zero when 
is negative, and 1 otherwise. Recalling that 
is the inclusion operator between 
norm, and 
, the space of symmetric matrices with the Ky Fan 2-norm, then 
I doubt this will ever be a useful observation 
norm
then 
for 
You can compute these using induction and integration by parts. By Markov’s inequality and Stirling’s approximation,![\displaystyle
\begin{aligned}
\mathbb{P}(X \geq t) & = \mathbb{P}(X^n \geq t^n) \leq \frac{\mathbb{E}X^n}{t^n} = \frac{n!}{(\alpha t)^n} \\ &< \sqrt{2\pi n} \left(\frac{n}{\alpha t e}\right)^n = e^{[\log(2\pi) + \log(n)]/2 + n\log(n) - n\log(\alpha t e)}
\end{aligned}](/cz/latexrender/pictures/62b79c457eeba1b488e314fef2ffa638.png "\displaystyle
\begin{aligned}
\mathbb{P}(X \geq t) & = \mathbb{P}(X^n \geq t^n) \leq \frac{\mathbb{E}X^n}{t^n} = \frac{n!}{(\alpha t)^n} \\ &< \sqrt{2\pi n} \left(\frac{n}{\alpha t e}\right)^n = e^{[\log(2\pi) + \log(n)]/2 + n\log(n) - n\log(\alpha t e)}
\end{aligned}")
![\displaystyle
\left(\frac{1}{2n} + \log(n) - \log(\alpha t) \right) e^{[\log(2\pi) + \log(n)]/2 + n\log(n) - n\log(\alpha t e)};](/cz/latexrender/pictures/6e3dd90cefdfc2dc014577bdc73c0159.png "\displaystyle
\left(\frac{1}{2n} + \log(n) - \log(\alpha t) \right) e^{[\log(2\pi) + \log(n)]/2 + n\log(n) - n\log(\alpha t e)};")
the quantity in the parentheses is monotonic:
is sufficiently large that the quantity in the parentheses is negative for some 
, then we can optimize the approximate tail bound by setting 
, then the root is given by the Lambert W function:
:
? Just eyeballing it, it looks like asymptotically, the moment bound gives you an exponential tail bound with a worse constant. If true, that’s pretty amazing!
denote the spectrum of an invertible matrix. Here’s the question: if 
is contained in the upper open half plane and 
is a projection matrix, then is 
contained in the upper closed half plane?
, and blue are in the spectrum of 
when 
is a contour surrounding the spectrum of 
for 
on the cut plane 
by the formula
is positive then
algebras? ( I’m only interested in the matrix case, but general theory is better than none)
for some 
Here’s a proof:
and 
where 
is an 
matrix with orthonormal columns, given by the SVD of 
is block diagonal in the basis given by 
:
