Given a matrix $A \in F^{n \times m},$ $m\gg n,$ and a given $b \in F^n,$ with $F$ any (possibly finite) field, is there an algorithm that approximates the size of the minimal support solution for the system $Ax=b?$

I asked this question yesterday during an (otherwise unusual) conversation with my advisor, after he noticed that brute-force methods for finding solutions as minimal as possible yield solutions with $\|x\|_0 \ll n;$ for instance, he mentioned that for some randomly generated matrix with ten thousand rows and two hundred thousand columns, and for some randomly generated vector with ten thousand entries, vector solutions with weight $\|x\|_0 \approx 20$ were found.

He said something about the support vectors being "very close" without specifying what that meant; perhaps $\|A_j-A_k\|_2$ small with respect to that distance for *unsupported* columns.

Since yesterday, I have started thinking about this question as another possible piece of my dissertation, and would appreciate any direction to literature addressing algorithms that can approximate the size of minimal support solutions quickly, or generate approximate minimal support solutions. I know Donoho has a paper utilizing the approximate $\ell_1$ minimization solution, but I do not know if any techniques exist for minimal support approximation for matrices over finite fields, or if any other approximation techniques have been published.

Thank you in advance for pointing in the direction of any literature or open questions along these lines — exploring this question would be very helpful for my dissertation!