Encontrar la solución más escasa para un sistema de ecuaciones lineales

¿Qué tan difícil es encontrar la solución más escasa para un sistema de ecuaciones lineales?

Más formalmente, considere el siguiente problema de decisión:

Instancia: Un sistema de ecuaciones lineales con coeficientes enteros y un número $c$ .

Pregunta: ¿Existe una solución para el sistema con al menos $c$ variables asignadas a cero?

También estoy tratando de determinar cuál es la dependencia de $c$ . Es decir, tal vez el problema es FPT con el parámetro $c$ .

Cualquier idea o referencia es realmente apreciada.

Considere el problema de maximizar el número de ecuaciones lineales satisfechas sobre algún anillo R , que a menudo es NP-duro, por ejemplo en el caso R = $\text{MAX-LIN}(R)$$R$$R=\mathbb{Z}$

Tomemos una instancia de este problema, donde A es una matriz n × m . Deje k = m + 1 . Construya un nuevo sistema lineal ˜ A ˜ x = ˜ b , donde ˜ A es una matriz k n × ( k n + m ) , ˜ x es ahora un vector dimensional ( k n + m ) y ˜ $Ax=b$$A$$n\times m$$k=m+1$$\tilde{A}\tilde{x} = \tilde{b}$$\tilde{A}$$kn \times (kn+m)$$\tilde{x}$$(kn+m)$$\tilde{b}$es un vector dimensional :$kn$

dondeInes lamatriz de identidadn×n.

Tenga en cuenta que este sistema siempre se satisface por el vector . De hecho, los primeros m entradas de ~ x puede ser arbitraria, y hay algo de vector solución con ese prefijo.$\tilde{x} = \begin{pmatrix} 0 & b & b & \cdots & b \end{pmatrix}^T$$m$$\tilde{x}$

Ahora afirmo que la fracción de las ecuaciones de A x = b son satisfactorias si existe una solución dispersa de ˜ A ˜ x = ˜ b que tiene al menos δ n k ceros. Esto se debe a que cada fila satisfecha de A x = b produce k ceros potenciales cuando x se extiende a ˜ $\delta$$Ax=b$$\tilde{A}\tilde{x}=\tilde{b}$$\delta nk$$Ax=b$$k$$x$$\tilde{x}$

Por lo tanto, si encontramos la escasez de la solución más escasa para , también hemos maximizadoδ, dividiendo la escasez pork.$\tilde{A}\tilde{x}=\tilde{b}$$\delta$$k$

Por lo tanto, creo que su problema es NP-hard.

El problema es NP-completo, por reducción del siguiente problema: Dada una matriz A con entradas enteras y un vector entero b con n entradas, ¿existe un vector x 0-1 con A x = b ?$m\times n$$A$$b$$n$$x$$Ax=b$

Para cada coordenada $x_i$$x$

• $100(n+m)$$x_i+y_{i,k}=0$$k=1,\ldots,100(n+m)$
• $100(n+m)$$x_i+z_{i,k}=1$$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.

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

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.