13
$\begingroup$

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.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
12
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – Michael Wehar
    Commented Dec 16, 2015 at 15:31
  • 1
    $\begingroup$ 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'$. $\endgroup$
    – Joe Bebel
    Commented Dec 20, 2015 at 8:24
  • 1
    $\begingroup$ @MichaelWehar I don't know whether this problem is FPT or not though $\endgroup$
    – Joe Bebel
    Commented Dec 20, 2015 at 8:42
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

This is called the Sparsest Solution Vector problem, and it is indeed NP-hard.

Improve this answer
$\endgroup$
4
$\begingroup$

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 (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 and not in subexponential time, assuming the exponential time hypothesis. Furthermore, according to a previous version of a paper on arXiv (see Lemma C.2 in version 1 of the paper), the problem is W[1]-complete.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Your reference for W[1]-completeness does not appear to have a "Lemma C.2". ​ ​ $\endgroup$
    – user6973
    Commented Dec 16, 2015 at 22:25
  • $\begingroup$ @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. $\endgroup$
    – Michael Wehar
    Commented Dec 17, 2015 at 6:51
  • $\begingroup$ That lemma uses a different parameterization from the OP. ​ ​ $\endgroup$
    – user6973
    Commented Dec 17, 2015 at 7:27
  • $\begingroup$ Oh I didn't realize there was an updated version, I'll take a look at it and update my answer accordingly. $\endgroup$
    – argentpepper
    Commented Dec 17, 2015 at 14:43
  • $\begingroup$ As I mentioned in my previous comment, that "lemma uses a different parameterization from the OP", so even if we assume the result is true (despite having been removed from version 2), the OP's question about parameterized complexity would still be open. ​ ​ $\endgroup$
    – user6973
    Commented Dec 17, 2015 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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