Suppose we have $n$ unit 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 reciprocal of the smaller 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!

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!

Suppose we have $n$ unit 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 reciprocal of the smaller 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.

Suppose we have $n$ unit 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 reciprocal of the smaller 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!