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.

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

$\endgroup$
  • 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 Dec 16 '15 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 Dec 20 '15 at 8:24
  • 1
    $\begingroup$ @MichaelWehar I don't know whether this problem is FPT or not though $\endgroup$ – Joe Bebel Dec 20 '15 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.

$\endgroup$
4
$\begingroup$

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

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

$\endgroup$
  • $\begingroup$ Your reference for W[1]-completeness does not appear to have a "Lemma C.2". ​ ​ $\endgroup$ – user6973 Dec 16 '15 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 Dec 17 '15 at 6:51
  • $\begingroup$ That lemma uses a different parameterization from the OP. ​ ​ $\endgroup$ – user6973 Dec 17 '15 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 Dec 17 '15 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 Dec 17 '15 at 21:06

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.