$\|x\|_0$ approximation for very large matrices 
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! 
 A: The problem you want to solve reduces to "exact cover by 3-sets" and is therefore NP-hard in general. The following proves this in the case $F=\mathbb{R}$, but the proof holds for an arbitrary field:

B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput. 24 (1995) 227–234.

In the cases where $F=\mathbb{R}$ or $\mathbb{C}$, the problem can be solved in polynomial time when $A$ is drawn at random (with high probability, and for several choices of probability distribution). As you indicated, the sparsest solution can be found by L1 minimization in these cases. This is the subject of compressed sensing, which was developed over the last decade after the seminal work of both Donoho and Candes, Romberg and Tao. See the following book for an introduction to this theory and a thorough survey of the vast literature:

S. Foucart, H. Rauhut, A mathematical introduction to compressive
  sensing, Birkhäuser, 2013.

I am not as familiar with the finite field setting. Unfortunately, much of the theory of compressed sensing leverages norms and inner products, which are not present in this setting.
A: A numerical method and several studies are given in

Exact and Approximate Sparse Solutions of Underdetermined Linear Equations, SIAM J. Sci. Comput., 31(1), 23–44. Sadegh Jokar and Marc E. Pfetsch, DOI:10.1137/070686676

They solve for all sparsest solutions (even if these are not unique) but only up to dimensions in some tens. However, I do not know of any other study doing $\ell^0$ minimization with guarantees in the realm of problems where $\ell^1$ is not equivalent.
