5
$\begingroup$

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!

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

This is, in essence, the most general form of the zero-one quadratic programming problem, and is known to be NP-complete. (see, for example, Computational Aspects of a Branch and Bound Algorithm for Quadratic Zero-One Programming by Pardalos and Rogers in Computing, 1990). Of course, this has not stopped mankind from developing reasonably efficient algorithms in practice.

$\endgroup$
  • $\begingroup$ Thank you Igor! I was wondering what the answer is when $n=3.$ Thanks! $\endgroup$ – KPU Mar 12 '15 at 2:26
  • 2
    $\begingroup$ As I also mentioned in my comments, this problem in the exact incarnation of the OP also goes under the name MaxQP in the theory CS literature, and has been the subject of fairly intense study (it contains the MaxCUT problem as a special case), including bounds obtained from Grothendieck's inequality, etc. $\endgroup$ – Suvrit Mar 12 '15 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.