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.)

Improve this question
$\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$
    – Joel Moreira
    Commented Dec 28, 2020 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$
    – Matthias Künzer
    Commented Dec 30, 2020 at 11:09

1 Answer 1

Reset to default
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.$$

Improve this answer
$\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$
    – Matthias Künzer
    Commented Jan 5, 2021 at 14:10
  • $\begingroup$ It may be worth to try solvers like Gurobi or CPLEX (possibly from SageMath). $\endgroup$
    – Max Alekseyev
    Commented Jan 5, 2021 at 15:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .