<p><a href="http://en.wikipedia.org/wiki/Matrix_Chernoff_bound" rel="nofollow">Matrix Chernoff bounds</a> (see also <a href="http://arxiv.org/abs/1004.4389" rel="nofollow">this arXiv paper</a>) are usually used to give upper bounds on the largest eigenvalue of a finite sum of random matrices. Sometimes it can also be used to give a lower bound on the smallest eigenvalue of a finite sum of random <em>positive semidefinite</em> (PSD) matrices.</p>

<p>For PSD matrices, the eigenvalues are the same as the singular values. My question is: </p>

<blockquote>
  <p>Is there any tool, or any other special cases (apart from the PSD case) for which there is a tool, to obtain lower bounds on the singular values of a finite sum of random matrices, or random symmetrical matrices?</p>
</blockquote>

CC BY-SA 3.0
2015-01-05T13:34:45.820Z
[Crossposted](http://math.stackexchange.com/q/1089639/439) on Math.SE. Please do not crosspost the same question, on mutliple StackExchange sites at once. Otherwise, welcome!
Niel de Beaudrap
CC BY-SA 3.0
2015-01-05T13:36:46.657Z
This question is interesting, but potentially borderline for being on-topic: Chernoff bounds and bounds on singular values are clearly of interest in computer science (as are algorithms to compute them), but analytic upper/lower bounds on strictly mathematical objects would seem more a proper subject of mathematics. Perhaps this would be better answered on Math.SE.
Niel de Beaudrap
CC BY-SA 3.0
2015-01-08T16:11:30.930Z
or also [mathoverflow.se]
vzn
<lower-bounds><linear-algebra><randomized-algorithms><matrices><chernoff-bound>
Tools to bound the singular values of a finite sum of random matrices from below?
olivia
# Tools to bound the singular values of a finite sum of random matrices from below?

(Asked by: username_0 on 2015-01-03)

[Matrix Chernoff bounds](http://en.wikipedia.org/wiki/Matrix_Chernoff_bound) (see also [this arXiv paper](http://arxiv.org/abs/1004.4389)) are usually used to give upper bounds on the largest eigenvalue of a finite sum of random matrices. Sometimes it can also be used to give a lower bound on the smallest eigenvalue of a finite sum of random *positive semidefinite* (PSD) matrices.

For PSD matrices, the eigenvalues are the same as the singular values. My question is:

> Is there any tool, or any other special cases (apart from the PSD case) for which there is a tool, to obtain lower bounds on the singular values of a finite sum of random matrices, or random symmetrical matrices?

**Tags:** lower-bounds, linear-algebra, randomized-algorithms, matrices, chernoff-bound

> **Comments:**
> **username_1**: [Crossposted](http://math.stackexchange.com/q/1089639/439) on Math.SE. Please do not crosspost the same question, on mutliple StackExchange sites at once. Otherwise, welcome!  
> **username_1**: This question is interesting, but potentially borderline for being on-topic: Chernoff bounds and bounds on singular values are clearly of interest in computer science (as are algorithms to compute them), but analytic upper/lower bounds on strictly mathematical objects would seem more a proper subject of mathematics. Perhaps this would be better answered on Math.SE.  
> **username_2**: or also [mathoverflow.se]  

---

## 0 answers

