Timeline for Upper bound for $\mathbb P(|f(A+XX^T)-f(A)| > \epsilon)$, where $A$ is a fixed pd matrix and $X$ has random iid entries
Current License: CC BY-SA 4.0
25 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 18, 2020 at 16:02 | vote | accept | dohmatob | ||
| Jun 11, 2020 at 8:23 | history | edited | dohmatob | CC BY-SA 4.0 |
added 84 characters in body
|
| Jun 11, 2020 at 8:12 | history | edited | dohmatob | CC BY-SA 4.0 |
added 32 characters in body
|
| Jun 11, 2020 at 8:05 | comment | added | dohmatob | Also, one can work out the details of your suggestion above by constructing a Gershgorin confidence set for the eigenvalues of $XX^T$. My guess is that something like this is done under the hood in the "book proof" of Weyl's inequality. | |
| Jun 11, 2020 at 8:04 | comment | added | dohmatob | @oferzeitouni Thanks for pointing out that Berry-Esseen is a sub-optimal overkill for my problem. I've updated my answer with a "direct" computation which leverages sub-Gaussianity, combined with Weyl's inequality. | |
| Jun 10, 2020 at 20:11 | comment | added | ofer zeitouni | I am not sure why one needs Berry Esseen. For all I can tell, a simple estimate based on variance would do. Namely, the difference between the eigenvalues of $XX^T$ and $1$ is, with high probability, bounded by $n$ times $1/\sqrt{k}$ (just bound the individual off-diagonal entries of $XX^T$; each such entry is a sum of independent random variables). As for your proof, sorry but I don't have the time now to check it. | |
| Jun 10, 2020 at 17:43 | comment | added | dohmatob | @oferzeitouni I've added an answer based on Berry-Esseen. I'd be grateful if you could take a look and tell me what you think. Thanks in advance! | |
| Jun 10, 2020 at 17:27 | history | edited | dohmatob | CC BY-SA 4.0 |
added 9 characters in body
|
| Jun 10, 2020 at 17:24 | answer | added | dohmatob | timeline score: 1 | |
| Jun 10, 2020 at 12:45 | history | edited | dohmatob | CC BY-SA 4.0 |
added 193 characters in body
|
| Jun 10, 2020 at 9:36 | history | edited | dohmatob | CC BY-SA 4.0 |
added 239 characters in body
|
| Jun 10, 2020 at 9:31 | history | edited | dohmatob | CC BY-SA 4.0 |
added 239 characters in body
|
| Jun 10, 2020 at 6:23 | history | edited | dohmatob | CC BY-SA 4.0 |
deleted 21 characters in body
|
| Jun 9, 2020 at 21:08 | history | edited | dohmatob | CC BY-SA 4.0 |
added 24 characters in body
|
| Jun 9, 2020 at 20:24 | history | edited | dohmatob | CC BY-SA 4.0 |
added 786 characters in body
|
| Jun 9, 2020 at 18:19 | history | edited | dohmatob | CC BY-SA 4.0 |
added 261 characters in body
|
| Jun 9, 2020 at 17:42 | history | edited | dohmatob | CC BY-SA 4.0 |
added 24 characters in body
|
| Jun 9, 2020 at 17:38 | comment | added | dohmatob | @oferzeitouni Thanks for the comments. $X$ has real iid entries which are distributed according to $N(0,\sigma^2/k)$. See corrected question. | |
| Jun 9, 2020 at 17:37 | history | edited | dohmatob | CC BY-SA 4.0 |
added 24 characters in body
|
| Jun 9, 2020 at 17:05 | comment | added | ofer zeitouni | In the regime $k\to \infty$ , $XX^T\sim kI_n$. In particular, there is no hope for what you want, as $f(A+XX^T)\to\infty$. Did you mean to normalize $XX^T$? Also, what are entries $N(0,\sigma^2 I)$? are the entries real? complex? | |
| Jun 9, 2020 at 15:44 | comment | added | dohmatob | $A$ is a fixed $n$ by $n$ matrix, where $n$ is small (say, $ n = 100$). In particular, $n$ doesn't go to $\infty$. As for $k$, one may limit onself to the regime $k \rightarrow \infty$, if that helps. If this clarifies the situation, please let me know (so I can update the question with these poiints). | |
| Jun 9, 2020 at 11:21 | comment | added | ofer zeitouni | The short answer is that if $\lambda_n>>n$ then you have concentration, and quantitative answers depend on regimes (for example, if all eigenvalues of $A$ are much larger than $n$ then you have good concentration). The question is too open ended for me to seriously answer. If there is a specific asymptotic regime that you care about then please write it. | |
| Jun 9, 2020 at 7:57 | comment | added | dohmatob | Sure, $n$, $k$, $\lambda_1$, and $\lambda_n$, and $\sigma$ are all problem data, and so I'd expect any reasonable answer to depend on them. | |
| Jun 9, 2020 at 6:24 | comment | added | ofer zeitouni | Any reasonable answer must depend on how $\lambda_n$ is close to $0$. This is because the minimal eigenvalue of $A+XX^T$ will be of order $\sqrt{n}$ and least. So if for example $\lambda_n=e^{-n}$ then there is a huge difference between $f(A)$ and $f(A+XX^T)$ if $n$ is large. | |
| Jun 8, 2020 at 13:19 | history | asked | dohmatob | CC BY-SA 4.0 |