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

13

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

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

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

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

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

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

Майкл Вехар
источник

Ответы:

12

Рассмотрим задачу максимизации числа удовлетворенных линейных уравнений над некоторым кольцом R , которое часто является NP-сложным, например, в случае R = ZMAX-LIN(R)RR=Z

Возьмем пример этой проблемы: где A - матрица n × m . Пусть k = m + 1 . Построить новую линейная система ~ ~ х = ~ Ь , где ~ является к п × ( к п + т ) матрица, ~ хAx=bAn×mk=m+1A~x~=b~A~kn×(kn+m)x~ теперь мерный вектор, а ~ Ь(kn+m)b~является мерным вектором:kn

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

A~=[AInInInInInInIn],b~=[b00]
Inn×n

Следует отметить , что эта система всегда выполняется вектором . На самом деле, первые м запись о ~ х может быть произвольной, и есть некоторый вектор решения с префиксом.x~=(0bbb)Tmx~

Теперь я утверждаю, что доля уравнений A x = b выполнима тогда и только тогда, когда существует разреженное решение ˜ A ˜ x = ˜ b, которое имеет не менее δ n k нулей. Это потому, что каждая удовлетворенная строка A x = b дает kδAx=bA~x~=b~δnkAx=bk потенциальных нулей, когда продолжается до ˜ xxx~

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

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

Джо Бебель
источник
1
Здорово! Спасибо, что поделились. Так что вы думаете, зависимость от c? Как вы думаете , мы можем решить менее чем за гдеn- размер ввода? poly(n)(nc)n
Майкл Вехар
1
Конечно: если мы предположим, что вам задано, какие элементов x равны нулю, то вы можете просто удалить эти элементы из x, чтобы получить меньший размерный x ′, а также удалить соответствующие столбцы из A, чтобы получить A . Затем используйте исключение Гаусса, чтобы решить, выполнима ли приведенная система A x = b ; если это так, то вы нашли разреженное решение. Затем вы попробуйте все ( пcxxxAAAx=b возможноAx. (nc)Ax
Джо Бебель
1
@MichaelWehar Я не знаю, является ли эта проблема FPT или нет
Джо Бебель
6

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

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

  • ввести новых уравнений x i + y i , k = 0 с k = 1 , , 100 ( n + m ) и 100(n+m)xi+yi,k=0k=1,,100(n+m)
  • ввести новых уравнений x i + z i , k = 1 с k = 1 , , 100 ( n100(n+m)xi+zi,k=1 . k=1,,100(n+m)

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

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

Гамов
источник
4

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

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

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

argentpepper
источник
Ваша ссылка на W [1] -полноту, по-видимому, не имеет "Леммы C.2".
@RickyDemer В версии 1 статьи, которую он связал, есть лемма С.2. Однако версия 2, похоже, имеет другое название и была совсем недавно изменена.
Майкл Вехар
Эта лемма использует параметризацию, отличную от OP.
О, я не знал, что была обновленная версия, я посмотрю на нее и обновлю свой ответ соответственно.
argentpepper
Как я упоминал в своем предыдущем комментарии, «лемма использует параметризацию, отличную от OP», поэтому, даже если мы предположим, что результат верен (несмотря на то, что он был удален из версии 2), вопрос OP о параметризованной сложности будет по-прежнему открытым.