Timeline for The Maximal $\ell_2$ norm of a signed sum of vectors
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 14, 2015 at 4:41 | history | edited | KPU | CC BY-SA 3.0 |
deleted 23 characters in body
|
| Mar 12, 2015 at 2:47 | comment | added | Noam D. Elkies | There are $2^{n-1}$ possibilities, so for $n=3$ it's just the maximum of four candidates, which is easy to compute. For example, let $G$ be the Gram matrix with $(i,j)$ entry $G_{ij} = v_i \cdot v_j$. Then the maximum norm is at most $\|G\|^{1/2}$ where $\|G\| := \sum_{i,j=1}^3 |G_{ij}|$. Equality holds unless all $G_{i,j}$ entries are nonzero and an odd number of the entries above the diagonal are negative, in which case the maximum is the square root of $\|G\| - 2 \min_{i,j} |G_{ij}|$. | |
| Mar 12, 2015 at 2:44 | comment | added | Suvrit | @KZH Please see my comment to Igor's answer. The google keyword "maxqp charikar" will bring up the relevant search results. | |
| Mar 12, 2015 at 2:27 | history | edited | KPU | CC BY-SA 3.0 |
added 119 characters in body
|
| Mar 12, 2015 at 2:25 | comment | added | KPU | To Geoff: Yes, I am assuming they are linearly independent. Thanks! To Suvrit: Not yet but will try. I thought I didn't ask my question clearly so I posted it again. In particular, I was wondering an analytical solution for $n=3.$ Thanks! | |
| Mar 12, 2015 at 1:36 | answer | added | Igor Rivin | timeline score: 6 | |
| Mar 12, 2015 at 1:30 | comment | added | Suvrit | Duh, wasn't this already closed? Did you look at MaxQP (that was in my last comment)... | |
| Mar 12, 2015 at 0:27 | comment | added | Christian Remling | A trivial bound is $\|U\|_2\le \sqrt{n}\|V\|$, and since the operator norm could be assumed for one of these $\pm 1$ vectors, this is all you can say in general. | |
| Mar 12, 2015 at 0:09 | comment | added | Geoff Robinson | I assume that the vectors are linearly independent? | |
| Mar 11, 2015 at 23:36 | review | First posts | |||
| Mar 11, 2015 at 23:37 | |||||
| Mar 11, 2015 at 23:34 | history | asked | KPU | CC BY-SA 3.0 |