Znalezienie najrzadszego rozwiązania układu równań liniowych

13

Jak trudno jest znaleźć najrzadsze rozwiązanie układu równań liniowych?

Bardziej formalnie, rozważ następujący problem decyzyjny:

Instancja: układ równań liniowych o współczynnikach całkowitych i liczbie $c$ .

Pytanie: Czy istnieje rozwiązanie dla systemu z co najmniej $c$ zmiennymi przypisanymi do zera?

Próbuję również ustalić, na czym polega zależność od $c$ . To znaczy, może problemem jest FPT z parametrem $c$ .

Wszelkie pomysły lub referencje są bardzo mile widziane.

— Michael Wehar
źródło

12

Rozważ problem $\text{MAX-LIN}(R)$ polegający na maksymalizacji liczby spełnionych równań liniowych w pewnym pierścieniu $R$ , który często jest NP-twardy, na przykład w przypadku $R=\mathbb{Z}$

Weźmy przykład tego problemu, gdzie jest macierzą . Niech . Skonstruuj nowy układ liniowy , gdzie jest macierzą , jest teraz wektorem wymiarowym , a $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}$ jest wektorem wymiarowym : $kn$

gdziejestmacierzą tożsamości.

\tilde{A} = [\begin{matrix} A & I_{n} \\ I_{n} & - I_{n} \\ I_{n} & - I_{n} \\ ⋱ & ⋱ \\ I_{n} & - I_{n} \end{matrix}], \tilde{b} = [\begin{matrix} b \\ 0 \\ ⋮ \\ 0 \end{matrix}]

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

I_{n}

$I_n$

n \times n

$n \times n$

Należy pamiętać, że system ten jest zawsze spełniony przez wektor . W rzeczywistości pierwsze wpisów może być dowolne i istnieje jakiś wektor rozwiązania z tym prefiksem. $\tilde{x} = \begin{pmatrix} 0 & b & b & \cdots & b \end{pmatrix}^T$ $m$ $\tilde{x}$

Teraz twierdzą, że część równania są spe IFF istnieje rzadki roztwór , która ma co najmniej zera. Jest tak, ponieważ każdy spełniony wiersz daje potencjalnych zer, gdy jest rozszerzone do $\delta$ $Ax=b$ $\tilde{A}\tilde{x}=\tilde{b}$ $\delta nk$ $Ax=b$ $k$ $x$ $\tilde{x}$

Zatem jeśli znajdziemy rzadkość najrzadszego rozwiązania , zmaksymalizujemy również , dzieląc rzadkość przez . $\tilde{A}\tilde{x}=\tilde{b}$ $\delta$ $k$

Dlatego uważam, że twój problem jest trudny NP.

— Joe Bebel
źródło

1

Chłodny! Dziękuję za podzielenie się. Jak myślisz, jaka jest zależność od c? Czy uważasz, że możemy rozwiązać to w mniej niż gdzie jest rozmiarem wejściowym?

p o l y (n) \cdot (\binom{n}{c})

$poly(n) \cdot {n \choose c}$

n

$n$

— Michael Wehar,

1

Jasne: jeśli założymy, że podano ci, które elementów są równe zero, możesz po prostu usunąć te elementy z aby uzyskać niższy wymiar a także usunąć odpowiednie kolumny z aby uzyskać . Następnie użyj eliminacji gaussowskiej, aby zdecydować, czy możliwy jest zredukowany układ ; jeśli tak, to znalazłeś rzadkie rozwiązanie. Następnie wypróbuj wszystkie możliwe .

c

$c$

x

$x$

x

$x$

x^{'}

$x'$

A

$A$

A^{'}

$A'$

A^{'} x^{'} = b

$A' x' = b$

(\binom{n}{c})

$\binom{n}{c}$

A^{'} x^{'}

$A'x'$

— Joe Bebel,

1

@MichaelWehar Nie wiem, czy ten problem dotyczy FPT, czy nie

— Joe Bebel,

6

Problemem jest NP-zupełny, przez redukcję z następującym problemem: podany w macierzy wpisami całkowite i całkowitej wektora z pozycji, nie istnieje do 0-1 wektor z ? $m\times n$ $A$ $b$ $n$ $x$ $Ax=b$

Dla każdej współrzędnej wektora , $x_i$ $x$

wprowadzić nowych równań z , i $100(n+m)$ $x_i+y_{i,k}=0$ $k=1,\ldots,100(n+m)$
wprowadzić nowych równań z . $100(n+m)$ $x_i+z_{i,k}=1$ $k=1,\ldots,100(n+m)$

Ponadto użyj starego układu równań . $Ax=b$

Istnieje rozwiązanie 0-1 oryginalnego układu , tylko wtedy, gdy nowy system ma rozwiązanie, w którym co najmniej zmiennych wynosi zero. $Ax=b$ $100(n+m)n$

— Gamow
źródło

4

Nazywa się to problemem Sparsest Solution Vector i rzeczywiście jest trudne w NP .

— RB
źródło

4

Ten problem jest trudny w różnych ustawieniach. Jak stwierdzono w innych odpowiedziach na to pytanie, problem jest NP-zupełny w stosunku do liczb całkowitych.

W przetwarzaniu sygnału macierz i wektory mają racjonalne wpisy, a problem ten jest czasem nazywany problemem rzadkiej rekonstrukcji . W tym ustawieniu problem jest NP-zupełny (patrz Twierdzenie 1).

W teorii kodowania wpisy pochodzą z pola skończonego, a problem ten jest czasem nazywany problemem dekodowania o najwyższym prawdopodobieństwie . W tym ustawieniu problem jest NP-zupełny, a nie w czasie podwykonawczym , przy założeniu wykładniczej hipotezy o czasie. Ponadto, zgodnie z poprzednią wersją artykułu na arXiv (patrz Lemat C.2 w wersji 1 artykułu), problem polega na ukończeniu W [1].

— argentpepper
źródło

Twoje odniesienie do kompletności W [1] nie wydaje się mieć „Lemmy C.2”.

@RickyDemer W wersji 1 artykułu, do którego prowadzi link, znajduje się Lemma C.2. Jednak wersja 2 wydaje się mieć inny tytuł i została bardzo niedawno zmieniona.

— Michael Wehar,

Ten lemat wykorzystuje inną parametryzację niż PO.

Och, nie zdawałem sobie sprawy, że istnieje zaktualizowana wersja, przyjrzę się jej i odpowiednio zaktualizuję swoją odpowiedź.

— argentpepper

Jak wspomniałem w poprzednim komentarzu, „lemat używa innej parametryzacji niż OP”, więc nawet jeśli założymy, że wynik jest prawdziwy (pomimo usunięcia z wersji 2), pytanie OP dotyczące sparametryzowanej złożoności nadal będzie otwarte.