I have an optimization problem: For a fixed matrix $A \in F_2^{M \times N}$ find a vector $\mathbf x \in F_2^{N \times 1}$ such that the vector $\mathbf y = A \mathbf x \in F_2^{M \times 1}$ has maximum Hamming weight/$L_0$ norm.
- Recall that the hamming weight/L0 norm of a vector $\mathbf y \in F_2^M$ is the number of 1-entries in the vector: $hamming(\mathbf y) \equiv |\{ i : \mathbf y[i] = 1 \}|$.
- All the algebra occurs over $F_2$.
Compactly, we wish to solve for $\mathbf x^*$ given $A$:
$$ \mathbf x^\star \equiv \arg \max_{\mathbf x \in F_2^{N \times 1}} |\{ i: (A \mathbf x)[i] = 1 \}| $$
I don't what problems of this type are called, and what their asymptotic complexity is. It seems to me that there is a tension between the linear-algebra that occurs over $F_2$ and the counting of 1-entries that occurs over $\mathbb Z$. I was hoping for references to:
- Algorithms to solve such a system of constraints if it is easy.
- Complexity theoretic results about the hardness of such problems if it is hard.
Note formally speaking, $L_0$ is number of non-zero entries. In our case, we have only $0/1$ entries. So, number of non-zero entries is the same as number of one-entries.