Нахождение разреженного решения системы линейных уравнений

Насколько сложно найти самое редкое решение системы линейных уравнений?

Более формально рассмотрим следующую проблему решения:

Экземпляр: система линейных уравнений с целыми коэффициентами и числом $c$ .

Вопрос: существует ли решение для системы с хотя бы $c$ переменными, присвоенными нулю?

Я также пытаюсь определить, какая зависимость от $c$ . То есть, возможно, проблема в FPT с параметром $c$ .

Любые идеи или ссылки действительно приветствуются.

Рассмотрим задачу максимизации числа удовлетворенных линейных уравнений над некоторым кольцом R , которое часто является NP-сложным, например, в случае R = $\text{MAX-LIN}(R)$$R$$R=\mathbb{Z}$

Возьмем пример этой проблемы: где A - матрица n × m . Пусть k = m + 1 . Построить новую линейная система ~ ~ х = ~ Ь , где ~ является к п × ( к п + т ) матрица, ~ $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}$является мерным вектором:$kn$

гдеяпявляетсяп×пединичная матрица.

Следует отметить , что эта система всегда выполняется вектором . На самом деле, первые м запись о ~ х может быть произвольной, и есть некоторый вектор решения с префиксом.$\tilde{x} = \begin{pmatrix} 0 & b & b & \cdots & b \end{pmatrix}^T$$m$$\tilde{x}$

Теперь я утверждаю, что доля уравнений A x = b выполнима тогда и только тогда, когда существует разреженное решение ˜ A ˜ x = ˜ b, которое имеет не менее δ n k нулей. Это потому, что каждая удовлетворенная строка A x = b дает $\delta$$Ax=b$$\tilde{A}\tilde{x}=\tilde{b}$$\delta nk$$Ax=b$$k$ потенциальных нулей, когда продолжается до ˜ $x$$\tilde{x}$

Таким образом, если мы найдем разреженность разреженного решения для , мы также развернутыйб, путем деления разреженности путемк.$\tilde{A}\tilde{x}=\tilde{b}$$\delta$$k$

Поэтому я считаю, что ваша проблема NP-трудна.

Задача является NP-полной за счет сокращения из следующей задачи: Учитывая матрицу A с целочисленными элементами и целочисленный вектор b с n элементами, существует ли вектор 0-1 x с A x = b ?$m\times n$$A$$b$$n$$x$$Ax=b$

Для каждой координаты $x_i$ вектора , $x$

• ввести новых уравнений x i + y i , k = 0 с k = 1 , … , 100 ( n + m ) и $100(n+m)$$x_i+y_{i,k}=0$$k=1,\ldots,100(n+m)$
• ввести новых уравнений x i + z i , k = 1 с k = 1 , … , 100 ( $100(n+m)$$x_i+z_{i,k}=1$ . $k=1,\ldots,100(n+m)$

Кроме того, используйте старую систему уравнений .$Ax=b$

Существует решение 0-1 исходной системы , если и только если новая система имеет решение, в котором по меньшей мере 100 ( n + m ) n переменных равны нулю.$Ax=b$$100(n+m)n$

Это называется проблемой Sparsest Solution Vector, и она действительно NP-трудная .

Эта проблема сложная , в разных настройках. Как указано в других ответах на этот вопрос, проблема является NP-полной по целым числам.

При обработке сигналов матрица и векторы имеют рациональные записи, и эту проблему иногда называют проблемой разреженной реконструкции . В этом случае проблема является NP-полной (см. Теорему 1).

В теории кодирования записи поступают из конечного поля, и эту проблему иногда называют проблемой декодирования с максимальным правдоподобием . В этом случае проблема является NP-полной, а не в субэкспоненциальном времени , если принять гипотезу экспоненциального времени. Кроме того, согласно предыдущей версии статьи об arXiv (см. Лемму C.2 в версии 1 статьи), проблема заключается в W [1] -полной.