Timeline for Subspaces with all vectors having large $\|x\|_{\infty}/\|x\|_2$ value
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 14, 2021 at 20:10 | vote | accept | Praneeth Kacham | ||
| Jul 13, 2021 at 20:00 | answer | added | Jason Gaitonde | timeline score: 4 | |
| Jul 3, 2021 at 21:44 | comment | added | Sandeep Silwal | You can consider the set of vector that are all supported on a small set of coordinates (the same set for all vectors). If they are supported on $m$ coordaintes then every $x$ will satisfy $\|x\|_{\infty} \ge 1/\sqrt{m}$ which is large if $m$ is sufficiently small (not sure how interesting this example is). Its also probably not the case that a random rotation will get you close to one of these subspaces but also not sure. | |
| Jun 26, 2021 at 17:25 | comment | added | Praneeth Kacham | @kodlu Consider an orthonormal basis, represented by a matrix $U$, for a $k$-dimensional subspace of $\mathbb{R}^{Ck\log(k)}$. As $U$ has $Ck\log(k)$ rows and $\|U\|_F^2 = k$, there must exist a row of $U$, say $U_{i}$ with $\|U_i\|_2 \ge \sqrt{k/Ck\log(k)}$. So, $U \cdot (U_i^T)/\|{U_i^T}\|$ which is a unit vector in the subspace has a coordinate of value $\|U_i\|_2 \ge \sqrt{k/Ck\log(k)} = \sqrt{1/C\log(k)}$. | |
| Jun 26, 2021 at 12:22 | comment | added | kodlu | can you show how you prove the claim in the first sentence | |
| Jun 26, 2021 at 5:41 | history | edited | Daniele Tampieri | CC BY-SA 4.0 |
Used $\mathbf{B}$ for the real field and consequently the real vector space.
|
| Jun 26, 2021 at 2:27 | review | First posts | |||
| Jun 26, 2021 at 6:57 | |||||
| Jun 26, 2021 at 2:16 | history | asked | Praneeth Kacham | CC BY-SA 4.0 |