Negatif olmayan en küçük kareler - Non-negative least squares
| Bir serinin parçası |
| Regresyon analizi |
|---|
| Modeller |
| Tahmin |
| Arka fon |
Olarak matematiksel optimizasyonu , problemi negatif olmayan en küçük kareler ( NNLS ) türüdür kısıtlı en küçük kareler katsayıları negatif hale gelmesine izin verilmez sorun. Yani, bir A matrisi ve y yanıt değişkenlerinin bir (sütun) vektörü verildiğinde amaç,
- x ≥ 0'a tabidir .
Burada x ≥ 0 , x vektörünün her bir bileşeninin negatif olmaması gerektiği anlamına gelir ve ‖·‖ 2 Öklid normunu belirtir .
Negatif olmayan en küçük kareler problemleri matris ayrıştırmada alt problemler olarak ortaya çıkar , örneğin PARAFAC algoritmaları ve negatif olmayan matris/tensör çarpanlarına ayırma . İkincisi, NNLS'nin bir genellemesi olarak düşünülebilir.
NNLS'nin bir başka genelleştirmesi, eşzamanlı üst ve alt sınırları α i ≤ x ben ≤ β i olan sınırlı değişkenli en küçük karelerdir (BVLS) .
İkinci dereceden programlama versiyonu
NNLS problemi, ikinci dereceden programlama problemine eşdeğerdir.
burada Q = A T A ve c = - A T y . Bu sorun, bir konveks olarak, Q, bir pozitif yarı kesin olmayan olumsuzluk kısıtlamaları dışbükey uygun bir set oluşturmaktadır.
algoritmalar
Bu problemi çözmek için yaygın olarak kullanılan ilk algoritma, Lawson ve Hanson tarafından 1974 tarihli Solving Least Squares Problems adlı kitaplarında yayınlanan aktif küme yöntemidir . Gelen pseudocode aşağıdaki gibi bu algoritma görünür:
- Girişler:
- m × n boyutunda gerçek değerli bir A matrisi ,
- m boyutunun gerçek değerli bir vektörü y ,
- gerçek bir değer ε , durdurma kriteri için tolerans.
- Başlat:
- P = ∅ olarak ayarlayın .
- Takım R = {1, ..., n }.
- x'i n boyutunda tamamen sıfır bir vektöre ayarlayın .
- Set ağırlık = A , T ( y - bir x ) .
- Let w R gelen dizinler ile alt vektörü göstermek R
- Ana döngü: while R ≠ ∅ ve max( w R ) > ε :
- Let j içinde R ' olması endeksi maks ( w R ) içinde ağırlık .
- Ekle j için P .
- Kaldır j den R .
- Let bir P olmak A dahil değişkenlere sınırlı P .
- s , x ile aynı uzunlukta bir vektör olsun . Let s p gelen dizinler ile alt vektörü göstermek P ve izin s R ' den dizinleri ile alt vektörü göstermek R .
- Küme s P = (( A P ) T A P ) -1 ( A P ) T y
- s R'yi sıfıra ayarla
- min( s P ) ≤ 0 iken :
- Let α = dakika x ben/x ben - s beniçin i de P burada s i ≤ 0 .
- Ayar X için X + α ( s - x ) .
- Taşı R tüm dizinler j içinde p öyle ki x j ≤ 0 .
- Küme s P = (( A P ) T A P ) -1 ( A P ) T y
- s R'yi sıfıra ayarlayın .
- Set x için s .
- Set ağırlık için bir T ( y - bir x ) .
- çıktı: x
Bu algoritma, bir çözüme ulaşmak için sınırlı sayıda adım atar ve ilerledikçe aday çözümünü sorunsuz bir şekilde iyileştirir (böylece makul sayıda yinelemede kesildiğinde iyi yaklaşık çözümler bulabilir), ancak büyük ölçüde nedeniyle uygulamada çok yavaştır. sözde tersin hesaplanması (( A P ) T A P ) -1 . Bu algoritmanın Varyantlar mevcuttur MATLAB rutin olarak lsqnonneg ve SciPy olarak optimize.nnls .
1974'ten beri birçok gelişmiş algoritma önerilmiştir. Fast NNLS (FNNLS), Lawson-Hanson algoritmasının optimize edilmiş bir versiyonudur. Diğer algoritmalar varyasyonlarını Landwebwer'in 'ın gradyan iniş yöntemi ve koordinat-bilge optimizasyonu üzerinde kuadratik programlama problemi dayalı.