Minimal Support Solutions of a Linear System (Dissertation)

Question

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 reducing a known $NP-$hard problem to my problem (perhaps via utilizing the subset sum problem, explaining the nature of my previous post here).

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.

Answer 1

The problem of determining a minimum support solution of a linear system is indeed NP-hard. Here is a reduction that works over the binary field $\mathbb{F}_2$. Given a graph $G$, an odd dominating set is a set $S \subseteq V(G)$ such that $|N_G[v] \cap S|$ is odd for all $v \in V(G)$. Here $N_G[v]$ means the set of neighbours of $v$ together with $v$ itself. Sutner proved that every graph has an odd dominating set and that the problem of finding a minimum size odd dominating set is NP-hard.

Given a graph $G$, let $A$ be the binary adjacency matrix of $G$, and let $A'=A+I$. Let $\mathbb{1}$ be the all ones vector. Note that the solutions of $A'x=\mathbb{1}$ correspond precisely to the odd dominating sets of $G$. By Sutner's result, this system is feasible, and computing a minimum support vector for it is NP-hard.