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

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.

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 A jest macierzą n × m . Niech k = m + 1 . Skonstruuj nowy układ liniowy ˜ A ˜ x = ˜ b , gdzie ˜ A jest macierzą k n × ( k n + m ) , ˜ x jest teraz wektorem wymiarowym ( k n + m ) , 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$

gdzieInjestmacierzą tożsamościn×n.

Należy pamiętać, że system ten jest zawsze spełniony przez wektor . W rzeczywistości pierwsze m wpisów ˜ x 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 A x = b są spe IFF istnieje rzadki roztwór ~ A ~ x = ~ b , która ma co najmniej hemibursztynianu n k zera. Jest tak, ponieważ każdy spełniony wiersz A x = b daje k potencjalnych zer, gdy x 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 k .$\tilde{A}\tilde{x}=\tilde{b}$$\delta$$k$

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

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 ?A b n x A x = $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.100 ( n + m ) $Ax=b$$100(n+m)n$

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

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].