The Maximal $\ell_2$ norm of a signed sum of vectors

Suppose we have $n$ vectors in $\mathbb{R}^n.$ Consider the signed sum of these vectors: $$U(s_1,\ldots,s_n)=s_1 v_1+s_2 v_2 + \ldots + s_n v_n$$ where $s_j$'s can only take values of $+1$ or $-1.$ I am interested in the maximal $\ell_2$ norm of the vector $U$ over all possible values of $(s_1,\ldots,s_n).$

This maximal $\ell_2$ norm of $U$ is certainly a function of $v_1,\ldots,v_n.$ For example, when $n=2,$ an easy argument in geometry shows that this maximal $\ell_2$ norm is proportional to the largest singular value of the matrix $V$ with $v_1,\ldots,v_n$ as columns. However, this is not true for $n=3$. I was wondering whether there is any existing result on this maximal $\ell_2$ norm as a function of the matrix $V,$ or is there an algorithm that solves this problem in linear time.

In particular, I was wondering what this function is for $n=3.$ Is it some function of the singular values? Thanks!

• I assume that the vectors are linearly independent? – Geoff Robinson Mar 12 '15 at 0:09
• 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. – Christian Remling Mar 12 '15 at 0:27
• Duh, wasn't this already closed? Did you look at MaxQP (that was in my last comment)... – Suvrit Mar 12 '15 at 1:30
• 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! – KPU Mar 12 '15 at 2:25
• 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}|$. – Noam D. Elkies Mar 12 '15 at 2:47

• Thank you Igor! I was wondering what the answer is when $n=3.$ Thanks! – KPU Mar 12 '15 at 2:26