Nezáporné nejmenší čtverce - Non-negative least squares

v matematická optimalizace, problém nezáporné nejmenší čtverce (NNLS) je typ omezené nejmenší čtverce problém, kdy se koeficienty nesmí stát zápornými. To znamená vzhledem k matici $A$ a (sloupcový) vektor proměnné odezvy $y$ , cílem je najít^[1]

{ displaystyle operatorname {arg , min} limity _ { mathbf {x}} | mathbf {Axe} - mathbf {y} | _ {2}}

podléhá

X \geq 0

.

Tady $X \geq 0$ znamená, že každá složka vektoru $X$ by měly být nezáporné a $‖\cdot‖₂$ označuje Euklidovská norma.

Nezáporné problémy nejmenších čtverců se objeví jako podproblémy maticový rozklad, např. v algoritmech pro PARAFAC^[2] a nezáporná maticová / tenzorová faktorizace.^[3]^[4] Ten lze považovat za zobecnění NNLS.^[1]

Další zobecnění NNLS je omezená proměnná nejmenších čtverců (BVLS), se současnou horní a dolní hranicí $α ᵢ \leq X ᵢ \leq β ᵢ$ .^[5]^:291^[6]

Kvadratická programovací verze

Problém NNLS je ekvivalentní problému a kvadratické programování problém

{ displaystyle operatorname {arg , min} limity _ { mathbf {x geq 0}} left ({ frac {1} {2}} mathbf {x} ^ { mathsf {T}} mathbf {Q} mathbf {x} + mathbf {c} ^ { mathsf {T}} mathbf {x} right),}

kde $Q$ = $A ᵀ A$ a $C$ = $- A ᵀ y$ . Tento problém je konvexní, tak jako $Q$ je pozitivní semidefinit a omezení non-negativity tvoří konvexní proveditelnou množinu.^[7]

Algoritmy

První široce používaný algoritmus pro řešení tohoto problému je metoda aktivní sady publikovali Lawson a Hanson ve své knize z roku 1974 Řešení problémů nejmenších čtverců.^[5]^:291 v pseudo kód, tento algoritmus vypadá následovně:^[1]^[2]

Vstupy:
- matice se skutečnou hodnotou $A$ dimenze $m \times n$ ,
- vektor se skutečnou hodnotou $y$ dimenze $m$ ,
- skutečná hodnota $ε$ , tolerance pro kritérium zastavení.
Inicializovat:
- Soubor $P = \emptyset$ .
- Soubor $R = {1, ..., n$ }.
- Soubor $X$ na nulový vektor dimenze $n$ .
- Soubor $w = A ᵀ (y - A X)$ .
- Nechat $w R$ označte sub-vektor s indexy z R
Hlavní smyčka: while R ≠ ∅ a max (w^R)> ε:
- Nechat $j$ v $R$ být indexem $max (w R)$ v $w$ .
- Přidat $j$ na $P$ .
- Odstranit $j$ z $R$ .
- Nechat $A P$ být $A$ omezeno na proměnné obsažené v $P$ .
- Nechat $s$ být vektor stejné délky jako $X$ . Nechat $s P$ označte sub-vektor s indexy z Pa nechte $s R$ označte sub-vektor s indexy z R.
- Soubor $s P = ((A P) ᵀ A P) -1 (A P) ᵀ y$
- Soubor $s R$ na nulu
- Zatímco min (s^P) ≤ 0:
  - Nechat $α = min X i / X i - s i pro i v P kde s i \leq 0$ .
  - Soubor $X$ na $X + α (s - X)$ .
  - Přesunout do $R$ všechny indexy $j$ v $P$ takhle $X j \leq 0$ .
  - Soubor $s P = ((A P) ᵀ A P) -1 (A P) ᵀ y$
  - Soubor $s R$ na nulu.
- Soubor $X$ na $s$ .
- Soubor $w$ na $A ᵀ (y - A X)$ .
Výstup: X

Tento algoritmus vyžaduje konečný počet kroků k dosažení řešení a plynule vylepšuje své kandidátské řešení, jak to jde (takže může najít dobré přibližné řešení, když je odříznut při rozumném počtu iterací), ale je v praxi velmi pomalý, a to hlavně kvůli výpočet pseudoinverze $((A ᴾ) ᵀ A ᴾ) ⁻¹$ .^[1] Varianty tohoto algoritmu jsou k dispozici v MATLAB jako rutina lsqnonneg^[1] a v SciPy tak jako optimalizovat.nnls.^[8]

Od roku 1974 bylo navrženo mnoho vylepšených algoritmů.^[1] Fast NNLS (FNNLS) je optimalizovaná verze algoritmu Lawson-Hanson.^[2] Mezi další algoritmy patří varianty Landweber je klesání metoda^[9] a souřadnicová optimalizace na základě výše uvedeného kvadratického programovacího problému.^[7]

Viz také

Reference

^ ^A ^b ^C ^d ^E ^F Chen, Donghui; Plemmons, Robert J. (2009). Omezení nezápornosti v numerické analýze. Sympózium o zrodu numerické analýzy. CiteSeerX 10.1.1.157.9203.
^ ^A ^b ^C Bro, Rasmus; De Jong, Sijmen (1997). "Rychlý algoritmus nejmenších čtverců omezený na negativitu". Journal of Chemometrics. 11 (5): 393. doi:10.1002 / (SICI) 1099-128X (199709/10) 11: 5 <393 :: AID-CEM483> 3.0.CO; 2-L.
^ Lin, Chih-Jen (2007). „Projected Gradient Methods for Nonnegative Matrix Factorization“ (PDF). Neurální výpočet. 19 (10): 2756–2779. CiteSeerX 10.1.1.308.9135. doi:10.1162 / neco.2007.19.10.2756. PMID 17716011.
^ Boutsidis, Christos; Drineas, Petros (2009). "Náhodné projekce pro nezáporný problém nejmenších čtverců". Lineární algebra a její aplikace. 431 (5–7): 760–771. arXiv:0812.4547. doi:10.1016 / j.laa.2009.03.026.
^ ^A ^b Lawson, Charles L .; Hanson, Richard J. (1995). Řešení problémů nejmenších čtverců. SIAM.
^ Stark, Philip B .; Parker, Robert L. (1995). „Nejmenší čtverce s ohraničenou proměnnou: algoritmus a aplikace“ (PDF). Výpočetní statistiky. 10: 129.
^ ^A ^b Franc, Vojtěch; Hlaváč, Václav; Navara, Mirko (2005). Sekvenční souřadnicový algoritmus pro problém nezáporných nejmenších čtverců. Počítačová analýza obrazů a vzorů. Přednášky z informatiky. 3691. 407–414. doi:10.1007/11556121_50. ISBN 978-3-540-28969-2.
^ „scipy.optimize.nnls“. SciPy v0.13.0 Referenční příručka. Citováno 25. ledna 2014.
^ Johansson, B. R .; Elfving, T .; Kozlov, V .; Censor, Y .; Forssén, P. E .; Granlund, G. S. (2006). „Aplikace šikmé projekce Landweberovy metody na model supervizovaného učení“. Matematické a počítačové modelování. 43 (7–8): 892. doi:10.1016 / j.mcm.2005.12.010.

[chen-1] A ^b ^C ^d ^E ^F Chen, Donghui; Plemmons, Robert J. (2009). Omezení nezápornosti v numerické analýze. Sympózium o zrodu numerické analýzy. CiteSeerX 10.1.1.157.9203.

[bro-2] A ^b ^C Bro, Rasmus; De Jong, Sijmen (1997). "Rychlý algoritmus nejmenších čtverců omezený na negativitu". Journal of Chemometrics. 11 (5): 393. doi:10.1002 / (SICI) 1099-128X (199709/10) 11: 5 <393 :: AID-CEM483> 3.0.CO; 2-L.

[3] Lin, Chih-Jen (2007). „Projected Gradient Methods for Nonnegative Matrix Factorization“ (PDF). Neurální výpočet. 19 (10): 2756–2779. CiteSeerX 10.1.1.308.9135. doi:10.1162 / neco.2007.19.10.2756. PMID 17716011.

[4] Boutsidis, Christos; Drineas, Petros (2009). "Náhodné projekce pro nezáporný problém nejmenších čtverců". Lineární algebra a její aplikace. 431 (5–7): 760–771. arXiv:0812.4547. doi:10.1016 / j.laa.2009.03.026.

[lawson-5] A ^b Lawson, Charles L .; Hanson, Richard J. (1995). Řešení problémů nejmenších čtverců. SIAM.

[6] Stark, Philip B .; Parker, Robert L. (1995). „Nejmenší čtverce s ohraničenou proměnnou: algoritmus a aplikace“ (PDF). Výpočetní statistiky. 10: 129.

[sca-7] A ^b Franc, Vojtěch; Hlaváč, Václav; Navara, Mirko (2005). Sekvenční souřadnicový algoritmus pro problém nezáporných nejmenších čtverců. Počítačová analýza obrazů a vzorů. Přednášky z informatiky. 3691. 407–414. doi:10.1007/11556121_50. ISBN 978-3-540-28969-2.

[8] „scipy.optimize.nnls“. SciPy v0.13.0 Referenční příručka. Citováno 25. ledna 2014.

[9] Johansson, B. R .; Elfving, T .; Kozlov, V .; Censor, Y .; Forssén, P. E .; Granlund, G. S. (2006). „Aplikace šikmé projekce Landweberovy metody na model supervizovaného učení“. Matematické a počítačové modelování. 43 (7–8): 892. doi:10.1016 / j.mcm.2005.12.010.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]