<blockquote>
  <p>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. </p>
</blockquote>

<p>A proof exists in the literature from Simon Foucart for the cases where the base field is $\mathbb{R}$ or $\mathbb{C}.$ Although Foucart didn't prove this exact problem, but something similar, and although Foucart's work was not concerned with finite field case, I believe my interpretation and extension of Foucart's proof establishes NP-Hardness for any field of any characteristic. </p>

<p>What I intend to do here is to merely check this proof for validity; since I am a doctoral candidate writing my dissertation in mathematics and my since my (now retired) advisor is unfamiliar with combinatorial optimization, I figured this board would be the best place to turn for guidance on this problem, as its proof is needed for the backdrop leading to the main analysis of underdetermined systems in my thesis. </p>

<p>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. </p>

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

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

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

<p>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 &gt; \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. </p>

<p>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. </p>

<p>=====</p>

<p>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. </p>

<p>Thanks for any help ahead of time! </p>

CC BY-SA 3.0
2017-02-25T08:31:31.263Z
Crossposted at http://mathoverflow.net/q/262983
Emil Jeřábek
CC BY-SA 3.0
2017-02-26T02:58:28.597Z
This question has now been answered at http://mathoverflow.net/questions/262983/np-hardness-of-finding-minimal-support-solutions-of-underdetermined-systems-over and hence is closed.
Thomas Rasberry
<np-hardness><optimization><linear-algebra><compressed-sensing>
Complexity of Underdetermined Systems
Thomas Rasberry
# Complexity of Underdetermined Systems

(Asked by: username_0 on 2017-02-24)

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

A proof exists in the literature from Simon Foucart for the cases where the base field is $\mathbb{R}$ or $\mathbb{C}.$ Although Foucart didn't prove this exact problem, but something similar, and although Foucart's work was not concerned with finite field case, I believe my interpretation and extension of Foucart's proof establishes NP-Hardness for any field of any characteristic.

What I intend to do here is to merely check this proof for validity; since I am a doctoral candidate writing my dissertation in mathematics and my since my (now retired) advisor is unfamiliar with combinatorial optimization, I figured this board would be the best place to turn for guidance on this problem, as its proof is needed for the backdrop leading to the main analysis of underdetermined systems in my thesis.

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!

**Tags:** np-hardness, optimization, linear-algebra, compressed-sensing
> **Comments:**
> **username_1**: Crossposted at http://mathoverflow.net/q/262983  
> **username_0**: This question has now been answered at http://mathoverflow.net/questions/262983/np-hardness-of-finding-minimal-support-solutions-of-underdetermined-systems-over and hence is closed.  

---

## 0 answers

