Given a finite field $F,$ a matrix $A \in F^{n,m}, \ m>n,$ and a vector $b \in F^n,$ describe the vector(s) $x \in F^m$ that solve $Ax=b$ and such that $\|x\|_0$ is minimal among all solutions. Here, $\|x\|_0$ is just the count of nonzero elements of $x.$
I am working on this problem as part of my dissertation, so I am not looking for a solution to this problem; any and all helpful suggestions will be cited in my paper.
Since I am primarily a teacher completing a graduate program under extreme time constraints (due to a long absence), this has been my first real foray into what it means to do research. I am a bit green with this!
My goal is to provide a non-"brute force" algorithm; that is, an algorithm that does more than simply collecting all answers to $Ax=b$ over the finite field $F$ and traversing the list for the answers for which $\|x\|_0$ is minimal.
Tao, Donoho and others have shown that the $\|x\|_1$ norm is effective as an approximation for the case over the real field, but since I am focused on finite fields, the use of such a norm to derive a similar asymptotically improved approximation algorithm is hopeless.
My dissertation committee is already aware that the problem is $NP-$hard (though, curiously, no actual proof of this result appeared in the literature until late 2014). My goal, then, is to either reduce the number of steps needed for some matrices with respect to "brute force" search of all solutions, or else to come up with a novel less-complex approximation method that recovers some minimal support solutions for finite fields.
In respect to the task set before me above, my working solution is to seek a process that manipulates the system to set apart solution sets according to the maximal number of zeros they can have as components. If successful, I would then traverse the set with the highest such maximal number and recover all minimal support solutions. The worst-case scenario is to receive a system $Ax=b$ whose solutions all have the same weight $\|x\|_0,$ which would of course mean that such an algorithm is no better than the "brute force method" of searching all solutions, but this would improve minimal-weight solution generation for some underdetermined systems over finite fields.
The attempt so far has been to try the following:
(1) Reduce the system $Ax=b$ over the finite field $F$ by finding the RREF, and check for inconsistency (no solution).
(2) Isolate the pivots in the RREF from step 1. Set these equal to the modified $b$ (called $v$) minus the space $A$ generated by the "free" variables: in other words, we now have the subproblem $P = v+A'x'.$
(3) Solve the modified subproblem $P=v+A'x'$ from Step 2 in some way.
I am stuck at step (3). My attempts to surpass this consist of further reducing the RREF in Step 1 by taking multiples of the first row to "zero out" the remaining rows of the last column, leaving the modified problem in (3) in the much more pleasant form $P=A'x'$ (with one row less than Step 2 would appear in general, of course). The result would be to represent some pivot variables in the RREF in terms of the free variables, and then simply substitute as many zeros as possible in the free (and pivot) variables and backsolve to check for consistency.
This was my initial proposal at my preliminary oral exam for my dissertation, and my committee seemed to believe at that time that this method would accomplish my goal.
I am struggling to untangle it four months later, and am beginning to wonder if I (and my committee) may have missed something here. With two months left to go before the Graduate College at my school imposes time limits on me, I am in a bit of a panic, but remain confident that some sort of fruitful analysis can come from this.
I appreciate any and all insights. Thank you!
