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!

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I assume that the vectors are linearly independent? $\endgroup$
    – Geoff Robinson
    Commented Mar 12, 2015 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
    Commented Mar 12, 2015 at 0:27
  • 1
    $\begingroup$ Duh, wasn't this already closed? Did you look at MaxQP (that was in my last comment)... $\endgroup$
    – Suvrit
    Commented Mar 12, 2015 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
    Commented Mar 12, 2015 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
    Commented Mar 12, 2015 at 2:47

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you Igor! I was wondering what the answer is when $n=3.$ Thanks! $\endgroup$
    – KPU
    Commented Mar 12, 2015 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
    Commented Mar 12, 2015 at 2:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .