Pogoń za bazą

Poszukiwanie podstaw to matematyczny problem optymalizacji formy

${\ Displaystyle \ min _ {x} \ | x \ | _ {1} \ quad {\ tekst {podlega}} \ quad y = Ax,}$

gdzie x jest N -wymiarowym wektorem rozwiązania (sygnał), y jest M -wymiarowym wektorem obserwacji (pomiarów), A jest macierzą transformacji M × N (zwykle macierzą pomiaru), a M < N .

Stosuje się ją zwykle w przypadkach, gdy istnieje niedookreślony układ równań liniowych y = Ax , który musi być dokładnie spełniony, a pożądane jest najrzadsze rozwiązanie w sensie L _{1 .}

Gdy pożądana jest wymiana dokładnej równości Ax i y w zamian za rzadsze x , preferowane jest odszumianie pogoni za bazą .

Problemy z poszukiwaniem bazy można przekształcić w problemy programowania liniowego w czasie wielomianowym i odwrotnie, dzięki czemu oba typy problemów są wielomianowo równoważne.

Równoważność programowania liniowego

Problem pogoni za bazą można przekształcić w problem programowania liniowego, zauważając to najpierw

${\ Displaystyle {\ rozpocząć {wyrównane} \|x\|_ {1} &=|x_{1}|+|x_{2}|+\ldokropki +|x_{n}|\\&=(x_{1}^{+}+x_{1}^{-})+( x_{2}^{+}+x_{2}^{-})+\ldokropki +(x_{n}^{+}+x_{n}^{-})\end{wyrównane}}}$

gdzie ${\ Displaystyle x_ {i} ^ {+}, x_ {i} ^ {-} \ geq 0}$ . $_$ ograniczenia _ ${\ Displaystyle |x_ {i}|}$ ma być przechowywany w ${\ Displaystyle x_ {i} ^ {+}}$ lub ${\ Displaystyle x_ {i} ^ {-}}$ w zależności od tego, czy ${\ displaystyle x_ {i}}$ jest odpowiednio większy lub mniejszy od zera. Chociaż zakres wartości i może potencjalnie $spełnić$ ograniczenie, osoby $.$ znajdą gdzie jeden lub oba z ${\ displaystyle x_ {i} ^ {+}}$ lub ${\ displaystyle x_ {i} ^ {-}}$ wynosi zero, co daje relację ${\ Displaystyle | x_ {i} | = (x_ {i} ^ {+} + x_ {i} ^ {-})}$ .

Na podstawie tego rozwinięcia problem można przekształcić w postać kanoniczną jako:

${\ Displaystyle {\ rozpocząć {wyrównane} i {\ tekst {Znajdź wektor}} & & (\ mathbf {x ^ {+}}, \ mathbf {x ^ {-}} ) \\& {\ text {to minimalizuje }}&&\mathbf {1} ^{T}\mathbf {x^{+}} +\mathbf {1} ^{T}\mathbf {x^{-}} \\&{\text{podlega} }&&A\mathbf {x^{+}} -A\mathbf {x^{-}} =\mathbf {y} \\&{\text{and}}&&\mathbf {x^{+}} ,\ mathbf {x^{-}} \geq \mathbf {0} .\end{wyrównane}}}$

Zobacz też

• Odszumianie pogoni za podstawą
• Skompresowane wykrywanie
• Widmo częstotliwości
• Testy grupowe
• Lasso (statystyki)
• Analiza widmowa metodą najmniejszych kwadratów
• Pasujący pościg
• Rzadkie przybliżenie

Referencje i dalsze czytanie

•   Stephen Boyd, Lieven Vandenbergh: Convex Optimization , Cambridge University Press, 2004, ISBN 9780521833783 , s. 337–337
•   Simon Foucart, Holger Rauhut: matematyczne wprowadzenie do wykrywania kompresji . Springer, 2013, ISBN 9780817649487 , s. 77–110

Linki zewnętrzne

• Shaobing Chen, David Donoho: Podstawowy pościg
• Terence Tao : Wykrywanie skompresowane . Seria wykładów Mahlera (slajdy)