<p>Consider the problem $\text{MAX-LIN}(R)$ of maximizing the number of satisfied linear equations over some ring $R$, which is often NP-hard, for example in the case $R=\mathbb{Z}$ </p>

<p>Take an instance of this problem, $Ax=b$ where $A$ is a $n\times m$ matrix. Let $k=m+1$. Construct a new linear system $\tilde{A}\tilde{x} = \tilde{b}$, where $\tilde{A}$ is a $kn \times (kn+m)$ matrix, $\tilde{x}$ is now a $(kn+m)$ dimensional vector, and $\tilde{b}$ is a $kn$ dimensional vector:</p>

<p>$$\tilde{A} = \begin{bmatrix}
 A &amp; I_n &amp; &amp;  &amp; \\
 &amp; I_n &amp; -I_n &amp; &amp; \\
 &amp; &amp; I_n &amp; -I_n &amp; \\
 &amp; &amp; &amp; \ddots &amp;\ddots  \\
 &amp; &amp; &amp; &amp; I_n &amp; -I_n \\
\end{bmatrix}, \tilde{b} = \begin{bmatrix} b \\ 0 \\ \vdots \\ 0 \end{bmatrix}$$
where $I_n$ is the $n \times n$ identity matrix.</p>

<p>Note that this system is always satisfied by the vector $\tilde{x} = \begin{pmatrix} 0 &amp; b &amp; b &amp; \cdots &amp;  b \end{pmatrix}^T$. In fact, the first $m$ entries of $\tilde{x}$ can be arbitrary, and there is some solution vector with that prefix.</p>

<p>I now claim that $\delta$ fraction of equations of $Ax=b$ are satisfiable iff there exists a sparse solution of $\tilde{A}\tilde{x}=\tilde{b}$ which has at least $\delta nk$ zeros. This is because every satisfied row of $Ax=b$ yields $k$ potential zeros when $x$ is extended to $\tilde{x}$</p>

<p>Thus, if we find the sparsity of the sparsest solution to $\tilde{A}\tilde{x}=\tilde{b}$, we have also maximized $\delta$, by dividing the sparsity by $k$. </p>

<p>Therefore, I believe your problem is NP-hard.</p>

CC BY-SA 3.0
2015-12-16T15:31:32.537Z
Cool!  Thank you for sharing.  So what do you think the dependence is on c?  Do you think we can solve it in less than $poly(n) \cdot {n \choose c}$ where $n$ is the input size?
Michael Wehar
CC BY-SA 3.0
2015-12-20T08:24:37.077Z
Sure: if we assume you're given which $c$ elements of $x$ are zero, then you can simply remove those elements from $x$ to get a lower dimensional $x'$ and also remove the corresponding columns from $A$ to get $A'$. Then use gaussian elimination to decide if the reduced system $A' x' = b$ is feasible; if it is, then you've found a sparse solution. Then, you try all $\binom{n}{c}$ possible $A'x'$.
Joe Bebel
CC BY-SA 3.0
2015-12-20T08:42:18.587Z
@MichaelWehar I don't know whether this problem is FPT or not though
Joe Bebel
CC BY-SA 3.0
2015-12-16T10:37:15.963Z
2015-12-16T10:37:15.963Z
Joe Bebel
<p>The problem is NP-complete, by reduction from the following problem: 
Given an $m\times n$ matrix $A$ with integer entries and an integer vector $b$ with $n$ entries, does there exist a 0-1 vector $x$ with $Ax=b$?</p>

<p>For every coordinate $x_i$ of vector $x$,  </p>

<ul>
<li>introduce $100(n+m)$ new equations $x_i+y_{i,k}=0$ with $k=1,\ldots,100(n+m)$, and  </li>
<li>introduce $100(n+m)$ new equations $x_i+z_{i,k}=1$ with $k=1,\ldots,100(n+m)$.  </li>
</ul>

<p>Furthermore use the old equation system $Ax=b$.</p>

<p>There exists a 0-1 solution to the original system $Ax=b$, if and only if the new system has a solution in which at least $100(n+m)n$ variables are zero.</p>

CC BY-SA 3.0
2015-12-16T16:29:29.717Z
2015-12-16T16:29:29.717Z
Gamow
<p>This is called the Sparsest Solution Vector problem, and <a href="http://statweb.stanford.edu/~donoho/Reports/2005/NonNegative-R5.pdf" rel="nofollow">it is indeed NP-hard</a>.</p>

CC BY-SA 3.0
2015-12-16T17:14:34.887Z
2015-12-16T17:14:34.887Z
R B
<p>This problem is <em>hard</em>, in various settings. As stated in the other answers to this question, the problem is NP-complete over the integers.</p>

<p>In signal processing, the matrix and the vectors have rational entries, and this problem is sometimes called the <em>sparse reconstruction problem</em>. In this setting, the problem is <a href="http://dx.doi.org/10.1137/S0097539792240406" rel="nofollow">NP-complete</a> (see Theorem 1).</p>

<p>In coding theory, the entries are from a finite field, and this problem is sometimes called the <em>maximum-likelihood decoding</em> problem. In this setting, the problem is <a href="http://dx.doi.org/10.1109/TIT.1978.1055873" rel="nofollow">NP-complete</a> and <a href="http://conference.itcs.tsinghua.edu.cn/ICS2011/content/paper/33.pdf" rel="nofollow">not in subexponential time</a>, assuming the exponential time hypothesis. Furthermore, according to a previous version of <a href="http://arxiv.org/abs/1311.3054v1" rel="nofollow">a paper on arXiv</a> (see Lemma C.2 in version 1 of the paper), the problem is W[1]-complete.</p>

CC BY-SA 3.0
2015-12-17T06:51:26.803Z
@RickyDemer There is a Lemma C.2 in version 1 of the paper that he linked.  However, version 2 seems to have a different title and was very recently changed.
Michael Wehar
CC BY-SA 3.0
2015-12-17T14:43:41.370Z
Oh I didn't realize there was an updated version, I'll take a look at it and update my answer accordingly.
argentpepper
CC BY-SA 3.0
2015-12-17T22:26:45.210Z
Well, the parameter in the linked paper is *k*, which corresponds to the number of *nonzero* entries in a solution vector (in their equivalent setting, it is the cardinality of a subset of vectors); this number wants to be minimized. The original problem asked about *c*, the number of *zero* entries in a solution vector; this number wants to be maximized. So they are equivalent if we consider *c* to be *n* - *k*.
argentpepper
CC BY-SA 3.0
2015-12-16T16:07:56.627Z
2015-12-17T16:50:57.940Z
2015-12-17T16:50:57.940Z
argentpepper
<p>How hard is it to find the sparsest solution to a system of linear equations?</p>

<p>More formally, consider the following decision problem:</p>

<p><strong>Instance:</strong> A system of linear equations with integer coefficients and a number $c$.</p>

<p><strong>Question:</strong> Does there exist a solution to the system with at least $c$ variables assigned to zero?</p>

<p>I'm also trying to determine what the dependence is on $c$.  That is, maybe the problem is FPT with parameter $c$.</p>

<p>Any ideas or references are really appreciated.</p>

<np-hardness><linear-algebra><linear-programming><matrices><sparse-matrix>
Finding the sparsest solution to a system of linear equations
Michael Wehar
# Finding the sparsest solution to a system of linear equations

(Asked by: username_0 on 2015-12-16)

How hard is it to find the sparsest solution to a system of linear equations?

More formally, consider the following decision problem:

**Instance:** A system of linear equations with integer coefficients and a number $c$.

**Question:** Does there exist a solution to the system with at least $c$ variables assigned to zero?

I'm also trying to determine what the dependence is on $c$. That is, maybe the problem is FPT with parameter $c$.

Any ideas or references are really appreciated.

**Tags:** np-hardness, linear-algebra, linear-programming, matrices, sparse-matrix

---

## 4 answers

### Answer by username_1 on 2015-12-16. Score: 12

Consider the problem $\text{MAX-LIN}(R)$ of maximizing the number of satisfied linear equations over some ring $R$, which is often NP-hard, for example in the case $R=\mathbb{Z}$

Take an instance of this problem, $Ax=b$ where $A$ is a $n\times m$ matrix. Let $k=m+1$. Construct a new linear system $\tilde{A}\tilde{x} = \tilde{b}$, where $\tilde{A}$ is a $kn \times (kn+m)$ matrix, $\tilde{x}$ is now a $(kn+m)$ dimensional vector, and $\tilde{b}$ is a $kn$ dimensional vector:

$$\tilde{A} = \begin{bmatrix}
A & I\_n & & & \\
& I\_n & -I\_n & & \\
& & I\_n & -I\_n & \\
& & & \ddots &\ddots \\
& & & & I\_n & -I\_n \\
\end{bmatrix}, \tilde{b} = \begin{bmatrix} b \\ 0 \\ \vdots \\ 0 \end{bmatrix}$$
where $I\_n$ is the $n \times n$ identity matrix.

Note that this system is always satisfied by the vector $\tilde{x} = \begin{pmatrix} 0 & b & b & \cdots & b \end{pmatrix}^T$. In fact, the first $m$ entries of $\tilde{x}$ can be arbitrary, and there is some solution vector with that prefix.

I now claim that $\delta$ fraction of equations of $Ax=b$ are satisfiable iff there exists a sparse solution of $\tilde{A}\tilde{x}=\tilde{b}$ which has at least $\delta nk$ zeros. This is because every satisfied row of $Ax=b$ yields $k$ potential zeros when $x$ is extended to $\tilde{x}$

Thus, if we find the sparsity of the sparsest solution to $\tilde{A}\tilde{x}=\tilde{b}$, we have also maximized $\delta$, by dividing the sparsity by $k$.

Therefore, I believe your problem is NP-hard.

> **Comments:**
> **username_0**: Cool!  Thank you for sharing.  So what do you think the dependence is on c?  Do you think we can solve it in less than $poly(n) \cdot {n \choose c}$ where $n$ is the input size?  
> **username_1**: Sure: if we assume you're given which $c$ elements of $x$ are zero, then you can simply remove those elements from $x$ to get a lower dimensional $x'$ and also remove the corresponding columns from $A$ to get $A'$. Then use gaussian elimination to decide if the reduced system $A' x' = b$ is feasible; if it is, then you've found a sparse solution. Then, you try all $\binom{n}{c}$ possible $A'x'$.  
> **username_1**: @MichaelWehar I don't know whether this problem is FPT or not though  

---

### Answer by username_2 on 2015-12-16. Score: 6

The problem is NP-complete, by reduction from the following problem:
Given an $m\times n$ matrix $A$ with integer entries and an integer vector $b$ with $n$ entries, does there exist a 0-1 vector $x$ with $Ax=b$?

For every coordinate $x\_i$ of vector $x$,

* introduce $100(n+m)$ new equations $x\_i+y\_{i,k}=0$ with $k=1,\ldots,100(n+m)$, and
* introduce $100(n+m)$ new equations $x\_i+z\_{i,k}=1$ with $k=1,\ldots,100(n+m)$.

Furthermore use the old equation system $Ax=b$.

There exists a 0-1 solution to the original system $Ax=b$, if and only if the new system has a solution in which at least $100(n+m)n$ variables are zero.


---

### Answer by username_3 on 2015-12-16. Score: 4

This is called the Sparsest Solution Vector problem, and [it is indeed NP-hard](http://statweb.stanford.edu/~donoho/Reports/2005/NonNegative-R5.pdf).


---

### Answer by username_4 on 2015-12-16. Score: 4

This problem is *hard*, in various settings. As stated in the other answers to this question, the problem is NP-complete over the integers.

In signal processing, the matrix and the vectors have rational entries, and this problem is sometimes called the *sparse reconstruction problem*. In this setting, the problem is [NP-complete](http://dx.doi.org/10.1137/S0097539792240406) (see Theorem 1).

In coding theory, the entries are from a finite field, and this problem is sometimes called the *maximum-likelihood decoding* problem. In this setting, the problem is [NP-complete](http://dx.doi.org/10.1109/TIT.1978.1055873) and [not in subexponential time](http://conference.itcs.tsinghua.edu.cn/ICS2011/content/paper/33.pdf), assuming the exponential time hypothesis. Furthermore, according to a previous version of [a paper on arXiv](http://arxiv.org/abs/1311.3054v1) (see Lemma C.2 in version 1 of the paper), the problem is W[1]-complete.

> **Comments:**
> **username_0**: @RickyDemer There is a Lemma C.2 in version 1 of the paper that he linked.  However, version 2 seems to have a different title and was very recently changed.  
> **username_4**: Oh I didn't realize there was an updated version, I'll take a look at it and update my answer accordingly.  
> **username_4**: Well, the parameter in the linked paper is *k*, which corresponds to the number of *nonzero* entries in a solution vector (in their equivalent setting, it is the cardinality of a subset of vectors); this number wants to be minimized. The original problem asked about *c*, the number of *zero* entries in a solution vector; this number wants to be maximized. So they are equivalent if we consider *c* to be *n* - *k*.  

---

