Is there a polynomial algorithm to solve the problem?

Question

Suppose that $v_1,\ldots,v_m\in\mathbb{C}^d$ satisfying $\sum_{i=1}^mv_iv_i^*=I_d$. Consider the optimization problem $$ \operatorname{min} \bigg\|\sum_{i=1}^m\varepsilon_iv_iv_i^*\bigg\|\\ s.t. \quad\varepsilon_i\in\{-1,+1\} ,\\ i=1,2,\ldots,m, $$ where the norm is matrix spectral norm. The objective function describes the least discrepancy of the two groups of the matrices partitioned in $\{v_1,\ldots,v_m\}$. Is there a polynomial algorithm to solve the integer programming?

Answer 1

Consider the special case $d=1$ and $v_1, ..., v_m \in \mathbb{R}$. Then your assumption is $\sum_{i=1}^m v_i^2 = 1$ and your objective function is $\min |\sum_{i=1}^m \epsilon_i v_i^2|$.

This is a version of the optimization version of the partition problem, so it is NP-hard. Specifically, you can transform any instance $a_1, ..., a_m \in \mathbb{N}$ of the partition problem into one satisfying your constraints by defining $v_i = \sqrt{\frac{a_i}{\sum_{i=1}^m a_i}}$.

If you want to enforce $d>1$, you can transform an instance $a_1, …, a_m \in \mathbb{N}$ of the partition problem into an instance of your problem as follows. Set the first coordinate of each $v_i$ to $\sqrt{\frac{a_i}{\sum_{i=1}^m a_i}}$ and set all other coordinates to zero. Then $v_i v_i^*$ is a $d \times d$ matrix with $(1,1)$ the only non-zero entry. Then $\|\sum_{i=1}^m \epsilon_i v_i v_i^*\|$ is just $|\sum_{i=1}^m \epsilon_i (v_i)_1 (v_i)_1|$, so the optimization problem is the same as in the case $d=1$.

However, with this construction $\sum_{i=1}^m v_i v_i^* \neq I_d$. To fix this, add to the instance of your problem additional vectors $v_{m+1}, …, v_{m+2d-2}$ with $v_{m+2i-3} = \frac{1}{\sqrt{2}} e_i$ and $v_{m+2i-2}=\frac{1}{\sqrt{2}}e_i$ for $i=2,…,d$. This ensures that $\sum_{i=1}^{m+2d-2} v_i v_i^* = I_d$. Furthermore, the optimal value of the objective does not change, because you can just choose $\epsilon_{m+2i-3}=-\epsilon_{m+2i-2}$ to cancel the contributions of each pair of vectors $v_{m+2i-3}$ and $v_{m+2i-2}$ for $i=2,...d$.

Therefore, a solution to your problem that could solve such instances would yield a solution to the partition problem. So your problem is NP-hard.