
> 
> Given a field $\mathbb{F}$ and a consistent underdetermined system $Ax=b$ over $\mathbb{F},$ $A\in \mathbb{F}^{m \times N}$ and $b \in \mathbb{F}^m,$ finding a vector $z \in \mathbb{F}^N$ such that $Az=b$ and $\|z\|\_0 \leq \|x\|\_0$ for all $x \in \mathbb{F}^N$ such that $Ax=b$ is NP-hard. 
> 
> 
> 


I have been working on this question for a while, and I think I have reached a solution via modifying a proof from Foucart's Compressive Sensing text. 


This question is cross-posted in [StackExchange-Theoretical Computer Science](https://cstheory.stackexchange.com/q/37615) as well, so if that is not allowed, let me know and I will take one of the posts down. 


To the proof: we reduce from 3-SET-COVER, which asks whether there exists a (nonoverlapping) partition $C\_j, j \in J$ within a given collection $\mathbf{C}$ of three-element subsets of some set $S,$ where $S$ has cardinality $|S|=m=3k$ for some natural number $k$ (hence without loss of generality we can refer to $S$ as the set $[m]=\{1, \ldots, m\}$ ).Papadimitriou and Steiglitz have shown that 3-SET-COVER is NP-Complete by reduction from 3-D MATCHING. 


Here, $\|x\|\_0$ simply means the number of nonzero components in the vector $x.$ 


For a given set $S$ and collection $\mathbf{C\_i}, i \in [N]$ of three-element subsets of $S$ as described above, construct a matrix $A \in \mathbb{F}^{m \times N}$ with columns $a\_i$ such that $a\_{i,j}=1$ if j $\in C\_i$ and $a\_{i,j}=0$ if $j \not \in C\_i.$ Additionally, let $b=\mathbf{1},$ the vector in $\mathbb{F}^m$ whose components are all equal to $1 \in \mathbb{F}.$ It is obvious this system can be constructed in polynomial time on $m$ and $N.$ 


Let $z$ be such that $Az=b$ and $\|z\|\_0 \leq \|x\|\_0$ for all $x$ such that $Ax=b.$ If $\|z\|\_0 < \frac{m}{3}$ then $\|Az\|<3\cdot\frac{m}{3}=m=\|b\|\_0,$ a contradiction since $\|b\|\_0=m.$ Hence $\|z\|\_0 \geq \frac{m}{3}.$ 


Run an algorithm solving for a minimal support solution of $Ax=b$ with output $z.$ There are two cases remaining: first, if $\|z\|\_0 = \frac{m}{3},$ then $C\_j, j \in supp(z) $ covers $[m]$ exactly. Second, if $\|z\|\_0 > \frac{m}{3}$ then the collection $\mathbf{C}$ contains no subcollection covering $[m]$ exactly; if such a subcollection $C\_j \subset \mathbb{C}$ existed, the $\frac{m}{3}$ corresponding columns $a\_j$ add to $\mathbf{1},$ contradicting the initial assumption for the second part. 


This means any algorithm solving the $\ell\_0$ minimization problem solves any 3-EXACT COVER problem through a polynomial transformation, and the proof is complete. 


=====


Is this proof valid? My main worry is that if $\mathbb{F}$ is a finite field, then the cyclic nature of addition could produce a cover, but the cover could not be exact, since this minimal support solution involves columns of $A$ corresponding to overlapping subsets within $\mathbf{C}$ in this case. 


Thanks for any help ahead of time! 



NP-Hardness of finding minimal-support solutions of underdetermined systems over any field
This proof looks correct to me. You don't have to worry about cancellations since the only way $z\in\mathbb{F}^N$ can have $|z|\_0=m/3$ and $Az={\bf 1}$ is if $z$ is the indicator function for an exact 3-cover. To see this, let $Z=\{j\in[m]:j\in C\_i\text{ for some }i\in[N]\text{ st }z\_i\neq0\}$. Note that $|Z|\leq3|z|\_0$ with equality holding iff $C\_i\cap C\_{i'}=\emptyset$ for all $i,i'\in[N]$ st $z\_i,z\_{i'}\neq0$.


