Przybliżenie niskiego rzędu

W matematyce aproksymacja niskiego rzędu jest problemem minimalizacji , w którym funkcja kosztu mierzy dopasowanie między daną macierzą (danymi) a macierzą aproksymującą (zmienną optymalizacyjną), z zastrzeżeniem, że macierz aproksymująca ma zmniejszoną rangę . Problem jest używany do modelowania matematycznego i kompresji danych . Ograniczenie rangi jest związane z ograniczeniem złożoności modelu, który pasuje do danych. W zastosowaniach często istnieją inne ograniczenia macierzy aproksymującej poza ograniczeniem rangowym, np. nieujemność i struktura Hankla .

Przybliżenie niskiego rzędu jest ściśle związane z:

• analiza głównych składowych ,
• analiza czynnikowa ,
• suma najmniejszych kwadratów ,
• ukryta analiza semantyczna
• regresja ortogonalna i
• dekompozycja trybu dynamicznego .

Definicja

Dany

• specyfikacja struktury ${\ Displaystyle {\ mathcal {S}}: \ mathbb {R} ^ {n_ {p}} \ do \ mathbb {R} ^ {m \ razy n}}$ ,
• wektor parametrów struktury ${\ Displaystyle p \ w \ mathbb {R} ^ {n_ {p}}}$ ,
• norma ${\ Displaystyle \|\ cdot \|}$ i
• pożądana ranga ${\ displaystyle r}$ ,

${\ Displaystyle {\ tekst {minimalizuj}} \ quad {\ tekst {ponad}} {\ widehat {p}} \ quad \| p - {\ widehat {p}} \|\ quad {\ tekst {z zastrzeżeniem} }\quad \operatorname {stopień} {\big (}{\mathcal {S}}({\widehat {p}}){\big )}\leq r.}$

Aplikacje

• Liniowa identyfikacja systemu , w którym to przypadku macierz aproksymująca ma strukturę Hankla .
• Uczenie maszynowe , w którym to przypadku macierz aproksymująca ma strukturę nieliniową.
• Systemy rekomendujące , w których macierz danych zawiera brakujące wartości , a przybliżenie jest kategoryczne .
• Uzupełnienie macierzy odległości , w którym to przypadku występuje dodatnie ograniczenie określoności.
• Przetwarzanie języka naturalnego , w którym to przypadku przybliżenie jest nieujemne .
• Algebra komputerowa , w którym to przypadku przybliżenie ma strukturę Sylwestra .

Podstawowy problem aproksymacji niskiego rzędu

Nieustrukturyzowany problem z dopasowaniem mierzony normą Frobeniusa , tj.

${\ Displaystyle {\ tekst {minimalizuj}} \ quad {\ tekst {ponad}} {\ widehat {D}} \$

ma rozwiązanie analityczne w zakresie dekompozycji macierzy danych na wartości osobliwe . Wynik jest określany jako lemat o przybliżeniu macierzy lub twierdzenie Eckarta – Younga – Mirsky'ego . Problem ten został pierwotnie rozwiązany przez Erharda Schmidta w nieskończenie wymiarowym kontekście operatorów całkowych (chociaż jego metody można łatwo uogólnić na dowolne operatory zwarte w przestrzeniach Hilberta), a później ponownie odkryli C. Eckart i G. Young. L. Mirsky uogólnił wynik na dowolne normy unitarnie niezmienne. Pozwalać

${\ Displaystyle D = U \ Sigma V ^ {\ wierzchołek} \ w \ mathbb {R} ^ {m \ razy n}, \ quad m \ równoważnik n }$

być rozkładem na wartości osobliwe $ldots$ gdzie $\$${\ Displaystyle \ Sigma =: \ operatorname {diag} (\ sigma _ {1}, \$$\ Displaystyle$ 1 $ldots$ σ . r ${\ Displaystyle R \ w \ {1 \ kropki, m-1 \}}$ , partycja ${\ Displaystyle U}$ , Σ $\ Sigma}$ i ${\ displaystyle V}$ w następujący sposób: V {\ displaystyle V}

${\ Displaystyle U =: {\ rozpocząć {bmatrix} U_ {1} i U_ {$

gdzie ${\ Displaystyle U_ {1}}$ jest ${\ Displaystyle m \ razy r}$ , ${\ displaystyle \ Sigma _ {1}}$ jest ${\ displaystyle r \ razy r}$ i U 1 {\ Displaystyle U_ {1}} ${\ Displaystyle V_ {1}}$ jest ${\ Displaystyle r \ razy n}$ . Następnie macierz rankingowa $osobliwej$ uzyskana z rozkładu obciętej wartości

${\ Displaystyle {\ widehat {D}} ^ {*} = U_ {1} \ Sigma _ {1} V_ {1} ^ {\ szczyt},}$

jest taki, że

${\ Displaystyle \| D - {\ widehat {D}} ^ {*} \| _ {\ tekst {F}} = \ min _ {\ operatorname {ranga} ({\ widehat {D}}) \ równoważnik r }\|D-{\widehat {D}}\|_{\text{F}}={\sqrt {\sigma _{1}^{2}+\cdots +\sigma _{r}^{2 }}}.}$

Minimalizator $\ sigma _ {r + 1} \ neq \ sigma _ { r}}$ unikalny wtedy i tylko wtedy, gdy $σ$ .

Dowód twierdzenia Eckarta – Younga – Mirsky'ego (dla normy widmowej )

Niech ${\ Displaystyle m \ równoważnik n} ZA$ rzeczywistą (prawdopodobnie prostokątną) macierzą z $\ Displaystyle A \ in \ mathbb {R} ^ {m \ razy n}}$ . Przypuszczam, że

${\ Displaystyle A = U \ Sigma V ^ {\ wierzchołek}}$

jest rozkładem na wartości osobliwe ${\ displaystyle A}$ . $Przypomnijmy$$wpisami$ że i są ortogonalnymi a $jest$ macierzą diagonalną z $)$${\ Displaystyle (\ sigma _ {1}, \ sigma _ {2}, \ cdots, \ sigma _ {m})}$ takie, że ${\ Displaystyle \ sigma _ {1 }\geq \sigma _{2}\geq \cdots \geq \sigma _{n}\geq 0}$ .

$}$ najlepsze przybliżenie rangi do $displaystyle$ widmowej, oznaczone przez , $przez$ ZA {

${\ Displaystyle A_ {k}: = \ suma _ {i = 1} ^ {k} \ sigma _ {i} u_ {i} v_ {i }^{\top }}$

gdzie i oznaczają odpowiednio kolumnę $\$$U}$$ja$$}$ i $displaystyle V$ .

Po pierwsze, zauważ, że mamy

${\ Displaystyle \| AA_ {k} \|_ {2} = \ lewo \|\ suma _ {i = 1} ^ {\ kolor {czerwony} {n}} \ sigma _ {i}u_{i}v_{i}^{\top }-\sum _{i=1}^{\color {red}{k}}\sigma _{i}u_{i}v_{i} ^{\top }\right\|_{2}=\left\|\sum _{i=\color {red}{k+1}}^{n}\sigma _{i}u_{i}v_ {i}^{\top }\right\|_{2}=\sigma _{k+1}}$

Dlatego musimy pokazać, że jeśli $i$ i gdzie $\ Displaystyle X}$ Y $Y}$ mają $Displaystyle K}$ kolumny wtedy ${\ Displaystyle \|AA_ {k} \|_ {2} = \ sigma _ {k + 1} \ równoważnik \|AB_ {k}\|_ {2}}$ .

Ponieważ ma $kolumny$$}$ musi istnieć nietrywialna liniowa kombinacja pierwszych kolumn $, tj.$$k + 1$ displaystyle

${\ Displaystyle w = \ gamma _ {1} v_ {1} + \ cdots + \ gamma _ {k + 1} v_ {k + 1 },}$

tak, że ${\ Displaystyle Y ^ {\ top} w = 0}$ . ${\ Displaystyle \ gamma _ {1} ^ {2} + \ cdots + \ gamma _ {k + 1} ^ {2} = 1}$ możemy $,$$+$ że równoważnie . Dlatego,

${\ Displaystyle \| AB_ {k} \|_ {2} ^ {2} \ geq \| (AB_ {k}) w \|_ {2} ^ {2} = \| Aw \ | _{2}^{2}=\gamma _{1}^{2}\sigma _{1}^{2}+\cdots +\gamma _{k+1}^{2}\sigma _{k +1}^{2}\geq \sigma _{k+1}^{2}.}$

Wynik wynika z pierwiastka kwadratowego z obu stron powyższej nierówności.

Dowód twierdzenia Eckarta – Younga – Mirsky'ego (dla normy Frobeniusa )

Niech ${\ Displaystyle m \ równoważnik n} ZA$ rzeczywistą (prawdopodobnie prostokątną) macierzą z $\ Displaystyle A \ in \ mathbb {R} ^ {m \ razy n}}$ . Przypuszczam, że

${\ Displaystyle A = U \ Sigma V ^ {\ wierzchołek}}$

jest rozkładem wartości osobliwych ZA $\ displaystyle A}$ .

$displaystyle k}$ że najlepsze przybliżenie rangi do $\$$jest$ oznaczone przez , podane przez

${\ Displaystyle A_ {k} = \ suma _ {i = 1} ^ {k} \ sigma _ {i} u_ {i} v_ {i} ^ {\szczyt }}$

gdzie i oznaczają odpowiednio kolumnę $\$$U}$$ja$$}$ i $displaystyle V$ .

Po pierwsze, zauważ, że mamy

$\ Displaystyle \| AA_ {k} \ |_{F}^{2}=\left\|\suma _{i=k+1}^{n}\sigma _{i}u_{i}v_{i}^{\top }\right\ |_{F}^{2}=\suma _{i=k+1}^{n}\sigma _{i}^{2}}$

Dlatego musimy pokazać, że jeśli $i$ i gdzie $\ Displaystyle X}$ Y $Y}$ mają $Displaystyle K}$ wtedy kolumny

${\ Displaystyle \| AA_ {k} \|_ {F} ^ {2} = \ suma _ {i = k + 1} ^ {n} \ sigma _ {i} ^ {2} \ równoważnik \| A-B_{k}\|_{F}^{2}.}$

$\displaystyle \sigma _{1}(A)\leq \sigma _{1}(A')+\sigma _{1}(A'')}$ normą $jeśli$ to $′$ . Załóżmy, że i ${\ Displaystyle A'_ {k}$$A''_ {k}}$$do$$Displaystyle$$odpowiednio$ przybliżenie rangi za pomocą SVD opisanej powyżej Wtedy dla dowolnego ${\ Displaystyle i, j \ geq 1}$

${\ Displaystyle {\ rozpocząć {wyrównane} \ sigma _ {i} (A') + \ sigma _ {j} (A'') & = \ sigma _ {1} (A'-A'_ {i-1 })+\sigma _{1}(A''-A''_{j-1})\\&\geq \sigma _{1}(AA'_{i-1}-A''_{ j-1})\\&\geq \sigma _{1}(A-A_{i+j-2})\qquad ({\text{od }}{\rm {pozycja}}(A'_{ i-1}+A''_{j-1})\leq {\rm {rank\,}}(A_{i+j-2})}\\&=\sigma _{i+j-1 }(A).\end{wyrównane}}}$

σ ${\ Displaystyle \ sigma _ {k + 1} (B_ {k}) = 0}$ kiedy ${\ Displaystyle A'= AB_ {k }}$ i ${\ Displaystyle A'' = B_ {k}}$ dochodzimy do wniosku, że dla ${\ Displaystyle i \ geq 1, j = k + 1}$

${\ Displaystyle \ sigma _ {i} (AB_ {k}) \ geq \ sigma _ {k + i} (A).}$

Dlatego,

${\ Displaystyle \| AB_ {k} \ | _ {F} ^ {2} = \ suma _ {i = 1} ^ {n} \ sigma _ {i} (AB_ {k}) ^ { 2}\geq \sum _{i=k+1}^{n}\sigma _{i}(A)^{2}=\|A-A_{k}\|_{F}^{2} ,}$

jako wymagane.

Ważone problemy aproksymacji niskiego rzędu

Norma Frobeniusa równomiernie waży wszystkie elementy błędu aproksymacji ${\ displaystyle D- {\ widehat {D}}}$ . Wcześniejszą wiedzę na temat rozkładu błędów można wziąć pod uwagę, rozważając ważony problem aproksymacji niskiego rzędu

${\ Displaystyle {\ tekst {minimalizuj}} \ quad {\ tekst$

gdzie $\ Displaystyle {\ tekst {vec}} (A)}$$.$ wektoryzuje macierz $kolumnach$ i jest daną dodatnią (pół) określoną macierzą wag

Ogólny ważony problem aproksymacji niskiego rzędu nie dopuszcza rozwiązania analitycznego pod względem rozkładu na wartości osobliwe i jest rozwiązywany lokalnymi metodami optymalizacji, które nie dają żadnej gwarancji znalezienia globalnie optymalnego rozwiązania.

${\ displaystyle W}$${\ Displaystyle \ suma _ {i, j} (W_ {i, j} (A_ {i, j} -B_ {i, j}) )^{2}}$$( ZA$ nieujemnej i macierzy chcemy zminimalizować po macierzach, najwyżej rangi ${\ displaystyle$$B}$ .

Wejściowe problemy aproksymacji L _p niskiego rzędu

Niech ${\ Displaystyle \|A \|_ {p} = \ lewo (\ suma _ {i, j} | A_ {i ,j}^{p}|\right)^{1/p}}$ . Dla ${\ Displaystyle p = 2}$ najszybszy algorytm działa w ${\ Displaystyle nnz (A) + n \ cdot poly (k / \ epsilon)}$ czas. Jeden z ważnych pomysłów, który został wykorzystany, nazywa się Oblivious Subspace Embedding (OSE), został po raz pierwszy zaproponowany przez Sarlosa.

Dla ${\ displaystyle p = 1}$ wiadomo, że ta początkowa norma L1 jest bardziej niezawodna niż norma Frobeniusa w obecności wartości odstających i jest wskazana w modelach, w których założenia Gaussa dotyczące szumu mogą nie mieć zastosowania. Naturalne jest dążenie do zminimalizowania ${\ displaystyle \|BA \|_ {1}}$ . Dla ${\ displaystyle p = 0}$ i ${\ displaystyle p \ geq 1}$ istnieje kilka algorytmów z możliwymi do udowodnienia gwarancjami.

Problem aproksymacji odległości niskiego rzędu

Niech ${\ Displaystyle P = \ {p_ {1}, \ ldots, p_ {m} \}}$ i ${\ Displaystyle Q =\{q_{1},\ldots ,q_{n}\}}$ będą dwoma zbiorami punktów w dowolnej przestrzeni metrycznej. Niech $displaystyle A}$ \ reprezentuje $,$${\ Displaystyle A_ {i, j} = odległość (p_ {i}, q_ {i})}$ . Takie macierze odległości są zwykle obliczane w pakietach oprogramowania i mają zastosowanie do uczenia się rozmaitości obrazów, rozpoznawania pisma ręcznego i wielowymiarowego rozwijania. Próbując zmniejszyć rozmiar ich opisu, można badać aproksymację takich macierzy niskiego rzędu.

Problem z aproksymacją niskiego stopnia rozproszonego/przesyłanego strumieniowo

Problemy aproksymacji niskiego rzędu w ustawieniach rozproszonych i strumieniowych zostały rozważone w.

Reprezentacje obrazu i jądra ograniczeń rangi

Korzystanie z ekwiwalentów

${\ Displaystyle \ operatorname {ranga} ({\ widehat {D}}) \ równoważnik r\quad \iff \quad {\text{są }}P\in \mathbb {R} ^{m\razy r}{\text{ i }}L\in \mathbb {R} ^{r\razy n}{\text{ takie, że }}{\widehat {D}}=PL}$

I

${\ Displaystyle \ operatorname {ranga} ({\ widehat {D}}) \ równoważnik r \ quad \iff \quad {\text{istnieje pełny rząd rang }}R\in \mathbb {R} ^{mr\times m}{\text{ takie, że }}R{\widehat {D}}=0}$

ważony problem aproksymacji niskiego rzędu staje się równoważny problemom optymalizacji parametrów

${\ Displaystyle {\ tekst {minimalizuj}} \ quad {\ tekst$

I

${\ Displaystyle {\ tekst {minimalizuj}} \ quad {\ tekst {ponad}} {\ widehat {D}} {\ tekst {i}} R \ quad \ nazwa operatora {vec} ^ {\ góra} (D- { \widehat {D}})W\operatorname {vec} (D-{\widehat {D}})\quad {\text{podlega}}\quad R{\widehat {D}}=0\quad {\ tekst{i}}\quad RR^{\top }=I_{r},}$

gdzie $tożsamości$ macierzą o rozmiarze $displaystyle r}$ .

Algorytm projekcji naprzemiennych

$, w$$),$ funkcja kosztu jest minimalizowana alternatywnie dla jednej ze zmiennych ( lub a druga jest stała Chociaż jednoczesna minimalizacja zarówno dla $,$ jak i $dla$ jest trudnym problemem optymalizacji dwuwypukłej , minimalizacja tylko dla jednej ze zmiennych jest liniowym problemem najmniejszych kwadratów i może być rozwiązana globalnie i wydajnie.

Wynikowy algorytm optymalizacji (zwany projekcjami naprzemiennymi) jest globalnie zbieżny z liniowym współczynnikiem zbieżności do lokalnie optymalnego rozwiązania ważonego problemu aproksymacji niskiego rzędu. $Należy$ podać wartość początkową parametru $.$ lub Iteracja jest zatrzymywana, gdy spełniony jest warunek zbieżności zdefiniowany przez użytkownika.

Matlabie algorytmu projekcji naprzemiennych dla ważonej aproksymacji niskiego rzędu:

 
          
   
    
       
      funkcja  [dh, f] = wlra_ap  (  d, w, p, tol, maxiter  )  [  m  ,  n  ]  =  rozmiar  (  d  );  r  =  rozmiar  (  p  ,  2  );  f  =  inf  ;  dla  i  =  2  :  maxiter  % minimalizacji po Lbp  =  kron  (  oko  (  n  )  ,  p  );  wl  =            
         
    
       
           (  bp  '  *  w  *  bp  )  \  bp  '  *  w  *  d  (:);  l  =  przekształć  (  vl  ,  r  ,  n  );  % minimalizacji nad P  bl  =  kron  (  l  '  ,  oko  (  m  ));  vp  =  (  bl  '  *  w  *  bl  )       
         
    
             
          
      \  bl  '  *  w  *  d  (:);  p  =  przekształcenie  (  vp  ,  m  ,  r  );  % sprawdź warunek wyjścia  dh  =  p  *  l  ;  dd  =  re  -  dh  ;  f  (  ja  )  =  dd  (:)  '  *  w  *  dd  (:);  jeśli  abs  (  f  (         
 ja  -  1  )  -  fa  (  ja  ))  <  tol  ,  przerwa  ,  koniec  koniec dla 

Algorytm projekcji zmiennych

$zmiennych$ projekcji naprzemiennych wykorzystuje fakt, że problem aproksymacji niskiego rzędu, sparametryzowany w postaci obrazu, jest dwuliniowy $.$ lub Dwuliniowy charakter problemu jest skutecznie wykorzystywany w podejściu alternatywnym, zwanym projekcjami zmiennymi.

Rozważ ponownie ważony problem aproksymacji niskiego rzędu, sparametryzowany w postaci obrazu. Minimalizacja w odniesieniu do $zmiennej ($ problem najmniejszych kwadratów) prowadzi do wyrażenia w postaci zamkniętej błędu aproksymacji jako funkcji ${\ displaystyle P}$

${\ Displaystyle f (P) = {\ sqrt {\ nazwa operatora {vec} ^ {\ góra} (D) {\ duży (} WW (I_ {n} \ czasami P) {\ duży (} (I_ {n} \otimes P)^{\top }W(I_{n}\otimes P){\big )}^{-1}(I_{n}\otimes P)^{\top }W{\Big )}\ nazwa operatora {vec} (D)}}.}$

Pierwotny problem jest $do$$. Można$ kwadratów minimalizacji w odniesieniu w tym celu wykorzystać standardowe metody optymalizacyjne, np. algorytm Levenberga-Marquardta .

Matlabie algorytmu projekcji zmiennych dla aproksymacji ważonej niskiego rzędu:

 
     
      
      funkcja  [dh, f] = wlra_varpro  (  d, w, p, tol, maxiter  )  prob  =  optimset  ();  prob  .  solver  =  'lsqnonlin'  ;  prob  .  options  =  optimset  (  'MaxIter'  ,  maxiter  ,  'TolFun'  ,  tol  );  prob  .  x0  =  p  ;  prob  .  cel  =  @(  str    
     
      
        )  cost_fun  (  p  ,  d  ,  w  );  [  p  ,  fa  ]  =  lsqnonlin  (  prawda  );  [  fa  ,  vl  ]  =  koszt_zabawy  (  p  ,  re  ,  w  );  dh  =  p  *  przekształcenie  (  vl  ,  rozmiar  (  p  ,  2  ),  rozmiar  (  re  

 
    
            
      ,  2  ));  funkcja  [f, vl] = koszt_zabawy  (  p, d, w  )  bp  =  kron  (  oko  (  rozmiar  (  d  ,  2  )),  p  );  vl  =  (  bp  '  *  w  *  bp  )  \  bp  '  *  w  *  d  (:);  f  =  re  (:)  '  *  w  *       (  re  (:)  -  bp  *  vl  ); 

Podejście projekcji zmiennych można zastosować również do problemów aproksymacji niskiego rzędu sparametryzowanych w postaci jądra. Metoda jest skuteczna, gdy liczba wyeliminowanych zmiennych jest znacznie większa niż liczba zmiennych optymalizacyjnych pozostawionych na etapie minimalizacji nieliniowej metodą najmniejszych kwadratów. Problemy takie występują w identyfikacji systemu, sparametryzowanej w postaci jądra, gdzie wyeliminowane zmienne są trajektorią aproksymującą, a pozostałe zmienne są parametrami modelu. W kontekście liniowych systemów niezmiennych w czasie krok eliminacji jest równoważny wygładzaniu Kalmana .

Wariant: przybliżenie niskiego rzędu z ograniczeniami wypukłymi

Zwykle chcemy, aby nasze nowe rozwiązanie nie tylko było niskiej rangi, ale także spełniało inne ograniczenia wypukłe wynikające z wymagań aplikacji. Interesujący nas problem byłby następujący:

${\ Displaystyle {\ tekst {minimalizuj}} \ quad {\ tekst {ponad}} \widehat {p}}\quad \|p-{\widehat {p}}\|\quad {\text{podlega}}\quad \operatorname {ranga} {\duża (}{\mathcal {S}} ({\widehat {p}}){\big )}\leq r{\text{i }}g({\widehat {p}})\leq 0}$

Ten problem ma wiele zastosowań w świecie rzeczywistym, w tym odzyskanie dobrego rozwiązania z niedokładnej (programowanie półokreślone) relaksacji. Jeśli dodatkowe ograniczenie $aby$ problem nazywa się strukturalnym przybliżeniem niskiego rzędu. Bardziej ogólna forma nazywana jest przybliżeniem niskiego rzędu z ograniczeniami wypukłymi.

Ten problem jest pomocny w rozwiązywaniu wielu problemów. Jest to jednak trudne ze względu na połączenie ograniczeń wypukłych i niewypukłych (niskiego rzędu). Różne techniki zostały opracowane w oparciu o różne realizacje ${\ Displaystyle g ({\ widehat {p}}) \ równoważnik 0}$ . Jednak metoda mnożników zmiennego kierunku (ADMM) może być zastosowana do rozwiązania problemu niewypukłego z wypukłą funkcją celu, ograniczeniami rangi i innymi ograniczeniami wypukłymi, a zatem jest odpowiednia do rozwiązania naszego powyższego problemu. Co więcej, w przeciwieństwie do ogólnych problemów niewypukłych, ADMM zagwarantuje zbieżność wykonalnego rozwiązania, o ile jego zmienna dualna będzie zbieżna w iteracjach.

Zobacz też

• Aproksymacja macierzy CUR jest wykonywana z wierszy i kolumn oryginalnej macierzy

• MT Chu, RE Funderlic, RJ Plemmons, Structured low-rank appimation, Linear Algebra and its Applications, tom 366, 1 czerwca 2003 r., strony 157–172 doi : 10.1016 / S0024-3795(02)00505-0

Linki zewnętrzne

• Pakiet C++ do aproksymacji strukturalnie niskiego rzędu