Let, $D\in\mathbb{C}^{1\times M}$ is a row vector with $M$ elements


$V\in\mathbb{C}^{3^M\times M}$ is a given matrix


$T$ is a scalar (real and $>1$)


$\textbf{The problem at hand is as follows:}$


$$\min\_{Y}||D-S||\_1$$



How to solve this optimization problem efficiently?
You can model this as an integer quadratic program. Let $x\_i$ be a nonnegative integer variable indicating the number of times index $i$ is selected ($i=1,\dots,2^M$). Rewrite the equation defining $S$ as $$S=\frac{1}{T}\sum\_{i=1}^{2^M} V(i,:)x\_i$$and add one more constraint:$$\sum\_{i=1}^{2^M} x\_i = T.$$


Whether this solves "efficiently" or not is an empirical matter. Given that the number of integer variables is exponential in $M$, I would expect the problem to become intractable for all but the very small values of $M$.


