I am looking for an algorithm to solve an underdetermined linear system over finite field (GF(2)) Ax=y. On input $a$ the algorithm needs to output $a$ sparse solutions. i.e. Those $a$ solutions with the minor Hamming weight. Do you known some paper about this?
Asked
Active
Viewed 110 times
1
-
Sounds like a difficult question in general. Basically because this is equivalent to the problem of decoding a linear code (at least if you ask for the solution with the absolute minimal number of non-zero components). I haven't done my homework, but it would not surprise me if this were known to be in one of those nasty NP-complexity classes. The problem of whether a given linear code has words of weight below a certain threshold is one such problem, and looks like this should reduce to that. In other words, no can do :-( – Jyrki Lahtonen Mar 31 '18 at 06:45
-
Of course, it is possible that I made a mistake. Also, if your system has some special structure, then it may tractable. – Jyrki Lahtonen Mar 31 '18 at 06:47
-
@JyrkiLahtonen I had found several papes treating this subject. For example: http://www.gtti.it/gtti14/papers/paper_8.pdf. The "problem" with these papers is that the algorithm presented in is only for $a=1$. – juaninf Mar 31 '18 at 10:56
-
@JyrkiLahtonen Also my system Ax=y is not "large". It is a small system for an instance. Number of equations unknows 200. Number os equations 8. – juaninf Mar 31 '18 at 11:13