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 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!


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.