7
$\begingroup$

Suppose given $n\ge 1$ and a subspace $U$ in $\mathbb{Q}^n$. It is given as $\mathbb{Q}$-span of certain known vectors.

For $x \in U$, we let the Hamming weight of $x$ be the number of its nonzero entries.

Is it possible to find an element of minimal Hamming weight in $U\smallsetminus\{0\}$? Is there an algorithm?

(All I could find is concerned with the case of vector spaces over finite fields. Or, on the other hand, with vectors of minimal Euclidean length in lattices.)

$\endgroup$
2
  • $\begingroup$ Well, you can look at all vectors with weight one (there are only $n$ of them up to scaling) to see if they belong to $U$, if not move to weight two, and so on... but presumably you want a faster algorithm. $\endgroup$ Dec 28 '20 at 10:41
  • 1
    $\begingroup$ For weight $2$, I would need to check whether the intersections with $n(n-1)/2$ subspaces of dimension $2$ are nonzero. This amounts to adding two standard basis vectors to my $\mathbb{Q}$-linear basis of $U$ and to check the resulting tuple of vectors for linear independence. Likewise for larger weights. In practice, this algorithm will work in small cases. $\endgroup$ Dec 30 '20 at 11:09
3
+50
$\begingroup$

Here is an Integer Linear Programming approach to this problem.

First, let's multiply given vectors by a suitable integer to make them all having integer components. Second, we notice that if certain rational coefficients deliver the minimum Hamming weight, then by scaling them, we can obtain integer coefficients delivering the same weight. Therefore, we can focus on the problem of finding an integer linear combination of integer vectors with the smallest nonzero number of nonzero components.

Let $v_1,\dots,v_m$ be given integer vectors. Let $c_i$ for $i\in\{1,\dots,m\}$ be integer variables corresponding to the coefficients in a linear combination. For each component $j\in\{1,\dots,n\}$, we further introduce two binary variables $p_j,q_j\in\{0,1\}$ and three inequalities: $$\sum_{i=1}^m v_{ij} c_i \geq p_j - Mq_j,$$ $$\sum_{i=1}^m v_{ij} c_i \leq -q_j + Mp_j,$$ $$p_j + q_j \leq 1,$$ where $M$ is a large positive constant (chosen empirically). The third inequality here restricts values to three possible cases: $(p_j,q_j)=(1,0)$ when the $j$-th component in the linear combination is positive; $(p_j,q_j)=(0,1)$ when the $j$-th component is negative; and $(p_j,q_j)=(0,0)$ when the $j$-th component is zero. Notice that the large value of $M$ when it comes with a nonzero coefficient makes the corresponding inequality silent (automatically satisfied).

Next, we exclude the zero linear combination by requiring $$\sum_{j=1}^n p_j + q_j \geq 1.$$

Finally, since $\sum_{j=1}^n p_j + q_j$, in fact, equals the weight of the linear combination, our objective is $$\text{minimize}\quad \sum_{j=1}^n p_j + q_j.$$

$\endgroup$
2
  • $\begingroup$ Thanks! That worked efficiently for a 12-dimensional subspace of a 64-dimensional space. We have used Magma's MinimalIntegerSolution. Trying to push the boundary then, for a 20-dimensional subspace of a 144-dimensional space, it produced an overflow. $\endgroup$ Jan 5 at 14:10
  • $\begingroup$ It may be worth to try solvers like Gurobi or CPLEX (possibly from SageMath). $\endgroup$ Jan 5 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.