2
$\begingroup$

In a finite field $q$, $M$ is an $m\times K$ matrix, where $m, $U$ is a sub-space spanned by the row vectors of $M$. $A$ is a $4\times K$ matrix which consists of four non-zero row vectors $a$, $b$, $c$, $d$. Assume we've already known that there always exists at least one $u\in U$ which makes the four inequalities hold simultaneously. I need to find a vector $u\in U$ such that the cardinality (number of non-zero elements) of $u$ is minimized, meanwhile, $au\neq 0$, $bu\neq 0$, $cu\neq 0$ and $du\neq 0$ (inner product) hold simultaneously.

i.e.

minimize $\text{card}(u)$

subject to

$au\neq 0$, $bu\neq 0$, $cu\neq 0$, $du\neq 0$, $u\in U$

How can I solve such a problem?

Thanks.

  • 0
    @Eric: I have converted your answer to a comment. *Answers should be reserved for posts that answer the question.* If you want to bring your question to the front page again so that more people will see it, you can do so by making any edit whatsoever to the body of the question. However, if you do this too many times, the question will go into Community Wiki mode and you won't get any reputation from it.2011-08-31

2 Answers 2

1

Since everything is finite, you could just try all the vectors $\bf u$ of Hamming weight 1 (I've never seen the word cardinality used the way you use it; I think Hamming weight means what you mean by cardinality), then all the vectors of Hamming weight 2, etc., until you find one that works. Were you maybe after something more efficient? Do you have some reason to believe there is a more efficient method?

  • 0
    BTW, cardinality means Hamming weight here. It's defined as "the cardinality of $x\in R^n$, denoted card(x), is the number of nonzero components of x" in the 3rd slide of [link](http://www.stanford.edu/class/ee364b/lectures/l1_slides.pdf).2011-08-19
0

Here is a remark: if you were working over the reals and $U = {\mathbb R}^K$, your problem would be equivalent to the minimum hitting set problem:

MINIMUM HITTING SET: Given a collection of sets, find a set of the smallest possible size which intersects all of them.

Specifically, if we associate the $i$'th row $a_i$ of your matrix with the set $A_i$ of its nonzero entries, then the cardinality you would be asking for would be exactly the size of the minimum hitting set of the collection $A_i$.

Proof: suppose a vector $u$ exists with $a_i^T u \neq 0$ for all $i$. Let $U$ be the set of nonzero entries of the vector $u$. Then naturally $U$ and $A_i$ intersect - if they didn't, $a_i^T u$ would equal zero. So the optimal value you seek is at least the size of the minimum hitting set.

Conversely, suppose a hitting set $U$ of size $k$ existed. Let $u$ be the vector which takes the values of $0$ outside this hitting set, and generate the values on $U$ randomly from the uniform distribution at $[0,1]$. The probability that $a_1^T u = 0$ is zero, and consequently the probability that for at least one $i$, we have $a_i^T u = 0$ is zero. Thus a vector $u$ of cardinality $k$ satisfying your conditions exists.

I believe possible to modify this argument to work over a large enough finite field.

Minimum hitting set is NP-complete, by the way. However, because you have only four sets, you could solve this variation in linear time in $K$.

  • 0
    Then I have to relax the condition and select $u_1=[1~1~0~0]$ as the sub-optimal solution. However, there exists another minimum hitting set solution $u_2=[0~0~0~1]$, which is optimal. My point is, after I find a minimum hitting set, I don't know whether such an optimal solution can be obained or not by combining the row vecotors or $M$. Because I cannot find out all the minimum hitting set and try them one by one.2011-08-20