Problem poszukiwania reprezentacji bazowej (z ang. basis pursuit) – problem z zakresu matematycznej optymalizacji, a także z zakresu działu nauki znanego jako przetwarzanie sygnałów (działu istotnego choćby dla medycznego obrazowania diagnostycznego); będący następującej postaci:
,
przy czym chcemy jednocześnie rozumieć tutaj jako pewien -wymiarowy wektor (sygnał), poszukiwany jako rozwiązanie; z kolei oznaczenie , jako pewien -wymiarowy wektor obserwacji (pomiarów); zaś , ma być tutaj pewną macierzą odwzorowania,o wymiarach (nazywaną także niekiedy: macierzą związaną z pomiarem). Wersja tego problemu, która stara się zminimalizować normę , okazuje się być problemem NP-trudnym.
Rozważania dotyczącego tego problemu znajdują swoje zastosowanie zazwyczaj w miejscach, gdzie jesteśmy także w stanie stwierdzić istnienie pewnego układu niedookreślonego, który to da się zapisać przy użyciu pojedynczego równania (jak powyżej): ; a który to chcemy nieco zmodyfikować w taki sposób, aby uzyskać pewien nowy układ równań, posiadający pewne dokładne (jednoznaczne, w pewnym sensie) rozwiązanie – przy czym naszym najistotniejszym celem, jest uzyskanie jak najbardziej rzadkiego rozwiązania, w sensie normy .
Niniejsza wersja problemu poszukiwania reprezentacji bazowej, jak też i wiele innych, analogicznych – w pewien sposób – do niniejszej postaci tego problemu; może zostać zapisanych jako pewne problemy programowania liniowego o czasie wielomianowym (i vice versa); co oznacza jednocześnie, że te dwa typy problemów, są względem siebie wielomianowo równoważne (ang. polynomially equivalent).
Zastosowanie do programowania liniowego Problem poszukiwania reprezentacji bazowej można przetłumaczyć na język programowania liniowego, w pierwszej kolejności zauważając, że mamy – w istocie:
przy czym . Powyższa konstrukcja bierze się z położenia (kładziemy): ; przy czym sens tej „zmiany oznaczeń” jest taki, że wartość wyrażenia powinna mieścić się odpowiednio pod oznaczeniem , bądź oznaczeniem , w zależności od tego, czy samo jest większe, czy też mniejsze, od zera.
Przypisy
Kategoria:Programowanie liniowe Kategoria:Metody numeryczne Kategoria:Metody optymalizacji