For a given $n \times m$ matrix A with $m>>n$ and a given vector $\vec b \in \mathbb{F}^{n \times 1}$, and given that $A\vec{x}=\vec{b}$ for at least one $\vec{x} \in \mathbb{F}^{m \times 1}$, describe the set of solutions of this system which have minimal support (or the highest number of zero elements) in $\mathbb{F}^{m \times 1}$.

This problem is the current topic of my dissertation, and a problem I've been working on since the start of the academic year. As I wrote in my previous post here, I am excited about this dissertation, since it is my first foray into research, and since I returned from a long and wayward absence to successfully pass some tough exams and really see my goal of a Ph.D. in sight for the first time after having long lost hope that I would ever get one.

Of course, I would not like to see this solved, but we've been looking for papers out there that address this problem or something like it and have not been able to discover much literature beyond a work by O. L. Mangasariany (1997) on polyhedral concave programs.

My first line of attack is to prove that this problem is $NP$- hard for $\mathbb{F}$ any nontrivial field. I am attempting to do so by connecting the problem to a known $NP-$hard problem (perhaps the subset sum problem, explaining the nature of my first post here) via reduction.

Regardless of whether I succeed in finding or creating such a proof, my main aim will be to develop algorithms that will at least reliably approximate an element from the set of such minimal support solutions as described above. We will examine the problem for finite fields, for the usual infinite fields, and then perhaps analyze the problem over domains or rings in general.

We have examined works on linear programming, general convex analysis, linear algebra, and algorithm analysis, and are not able to find any extant solutions to these problems.

Since my advisor and I are transitioning from a state of picking and assessing literature for problems to honing in on solving this particular problem, I want to make a post here as a query for literature on this topic before I continue under the assumption that there is no paper addressing my problem already.

Again, I am intending this post to be in the spirit of proper professionalism, and I hope I am not breaking any rules in making this, as I am still new to Overflow. Nor am I looking for someone to "solve" the problem or otherwise do any work for me - I just want to make sure I've really gathered all existing approaches to this problem in the literature, if any, before trying one of my own!

Thank you in advance for your help, and for your advice in general, as I continue the journey starting my research career.