2
$\begingroup$

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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .