Numeriska metoder för linjära minsta kvadrater

Numeriska metoder för linjära minsta kvadrater innebär numerisk analys av linjära minsta kvadraters problem.

Introduktion

En allmän inställning till minsta kvadratproblemet $\operatörsnamn {\,min} \,{\big \|}\mathbf {y} -X{\boldsymbol {\beta } }{\big \|}^{2}$ kan beskrivas enligt följande. Antag att vi kan hitta en n av m matris S så att XS är en ortogonal projektion på bilden av X . Då ges en lösning på vårt minimeringsproblem av

{\boldsymbol {\beta }}=S\mathbf {y}

helt enkelt därför att

X{\boldsymbol {\beta }}=X(S\mathbf {y} )=(XS)\mathbf {y}

är exakt en sökt för ortogonal projektion av $\mathbf {y}$ på en bild av X ( se bilden nedan och notera att som förklaras i nästa avsnitt är bilden av X bara ett delrum genererat av kolumnvektorer av X ). Några populära sätt att hitta en sådan matris S beskrivs nedan.

Invertering av normalekvationernas matris

Ekvationen $(\mathbf {X} ^{\rm {T}}\mathbf {X} )\beta =\mathbf {X} ^{\rm {T} }y$ är känd som normalekvationen. Den algebraiska lösningen av normalekvationerna med en fullrangsmatris X ^T X kan skrivas som

{\hat {\boldsymbol {\beta }}}=(\mathbf {X} ^{\rm {T}}\mathbf { X} )^{-1}\mathbf {X} ^{\rm {T}}\mathbf {y} =\mathbf {X} ^{+}\mathbf {y}

där X ⁺ är Moore–Penrose-pseudoinversen av X . Även om denna ekvation är korrekt och kan fungera i många tillämpningar, är det inte beräkningseffektivt att invertera normalekvationsmatrisen ( Gramian-matrisen) . Ett undantag förekommer vid numerisk utjämning och differentiering där ett analytiskt uttryck krävs.

Om matrisen X ^T X är välkonditionerad och positivt bestämd , vilket antyder att den har full rang , kan de normala ekvationerna lösas direkt genom att använda Cholesky-nedbrytningen R ^T R , där R är en övre triangulär matris , vilket ger:

R^{\rm {T}}R{\hat {\boldsymbol {\beta }}}=X^{\rm {T}}\mathbf {y} .

Lösningen erhålls i två steg, ett framåtriktat ersättningssteg , som löser för z :

R^{\rm {T}}\mathbf {z} =X^{\rm {T}}\mathbf {y} ,

följt av en ersättning bakåt, löser ${\hat {\boldsymbol {\beta }}}$ :

R{\hat {\boldsymbol {\beta }}}=\mathbf {z} .

Båda substitutionerna underlättas av den triangulära naturen hos R .

Ortogonala nedbrytningsmetoder

Ortogonala nedbrytningsmetoder för att lösa minsta kvadratproblemet är långsammare än den vanliga ekvationsmetoden men är mer numeriskt stabila eftersom de undviker att bilda produkten X ^T X .

Residualerna skrivs i matrisnotation som

\mathbf {r} =\mathbf {y} -X{\hat {\boldsymbol {\beta }}}.

Matrisen X utsätts för en ortogonal sönderdelning, t.ex. QR-sönderdelningen enligt följande.

X=Q{\begin{pmatrix}R\\0\end{pmatrix}}\

,

där Q är en m × m ortogonal matris ( Q ^T Q=I ) och R är en n × n övre triangulär matris med $r_{ii}>0$ .

Restvektorn vänstermultipliceras med QT ^.

Q^{ \rm {T}}\mathbf {r} =Q^{\rm {T}}\mathbf {y} -\left(Q^{\rm {T}}Q\right){\begin{pmatrix}R \\0\end{pmatrix}}{\hat {\boldsymbol {\beta }}}={\begin{bmatrix}\left(Q^{\rm {T}}\mathbf {y} \right)_{ n}-R{\hat {\boldsymbol {\beta }}}\\\left(Q^{\rm {T}}\mathbf {y} \right)_{mn}\end{bmatrix}}={ \begin{bmatrix}\mathbf {u} \\\mathbf {v} \end{bmatrix}}

Eftersom Q är ortogonal kan summan av kvadraterna av residualerna, s , skrivas som:

s=\|\mathbf {r} \|^{2}=\mathbf {r} ^ {\rm {T}}\mathbf {r} =\mathbf {r} ^{\rm {T}}QQ^{\rm {T}}\mathbf {r} =\mathbf {u} ^{\rm {T}}\mathbf {u} +\mathbf {v} ^{\rm {T}}\mathbf {v}

Eftersom v inte beror på β , uppnås minimivärdet på s när det övre blocket, u , är noll. Därför hittas parametrarna genom att lösa:

R{\hat {\boldsymbol {\beta }}}=\left(Q^{\rm {T}}\mathbf {y} \right)_{n}.

Dessa ekvationer är lätta att lösa eftersom R är övre triangulär.

En alternativ nedbrytning av X är singularvärdesuppdelningen (SVD)

X=U\Sigma V^{\rm {T}}\

,

0 där U är m av m ortogonal matris, V är n av n ortogonal matris och $\Sigma$ är en m x n matris med alla dess element utanför huvuddiagonalen lika med . Pseudoinversen av $\Sigma$ erhålls enkelt genom att invertera dess diagonala element som inte är noll och transponera . Därav,

\mathbf {X} \mathbf {X} ^{+}=U\Sigma V^{\rm {T}}V \Sigma ^{+}U^{\rm {T}}=UPU^{\rm {T}},

där P erhålls från $\Sigma$ genom att ersätta dess diagonala element som inte är noll med ettor. Eftersom $(\mathbf {X} \mathbf {X} ^{+})^{*}=\mathbf {X} \mathbf {X} ^{+}$ (egenskapen för pseudoinvers), är matrisen $UPU^{\rm {T}}$ en ortogonal projektion på bilden (kolumnutrymme) av X . I enlighet med ett allmänt tillvägagångssätt som beskrivs i inledningen ovan (hitta XS som är en ortogonal projektion),

S=\mathbf {X} ^{+}

,

och sålunda,

\beta =V\Sigma ^{+}U^{\rm {T}}\mathbf {y}

är en lösning på ett minsta kvadratproblem. Denna metod är den mest beräkningsintensiva, men är särskilt användbar om den normala ekvationsmatrisen, X ^T X , är mycket dåligt konditionerad (dvs om dess villkorsnummer multiplicerat med maskinens relativa avrundningsfel är avsevärt stort). I så fall lägger man bara till numeriskt brus till lösningen att inkludera de minsta singularvärdena i inversionen. Detta kan botas med den trunkerade SVD-metoden, vilket ger ett mer stabilt och exakt svar, genom att explicit nollställa alla singulära värden under en viss tröskel och så ignorera dem, en process som är nära relaterad till faktoranalys .

Diskussion

De numeriska metoderna för linjära minsta kvadrater är viktiga eftersom linjära regressionsmodeller är bland de viktigaste modellerna, både som formella statistiska modeller och för utforskning av datamängder. Majoriteten av statistiska datorpaket innehåller faciliteter för regressionsanalys som använder sig av linjära minsta kvadratberäkningar. Det är därför lämpligt att avsevärda ansträngningar har ägnats åt uppgiften att säkerställa att dessa beräkningar utförs effektivt och med vederbörlig hänsyn till avrundningsfel .

Individuella statistiska analyser görs sällan isolerade, utan är snarare en del av en sekvens av undersökningssteg. Några av de ämnen som är involverade i att överväga numeriska metoder för linjära minsta kvadrater hänför sig till denna punkt. Så viktiga ämnen kan vara

Beräkningar där ett antal liknande, och ofta kapslade , modeller beaktas för samma datamängd. Det vill säga där modeller med samma beroende variabel men olika uppsättningar av oberoende variabler ska beaktas, för i huvudsak samma uppsättning datapunkter.
Beräkningar för analyser som sker i en sekvens när antalet datapunkter ökar.
Särskilda hänsyn för mycket omfattande datamängder.

Anpassning av linjära modeller med minsta kvadrater uppstår ofta, men inte alltid, i samband med statistisk analys . Det kan därför vara viktigt att överväganden om beräkningseffektivitet för sådana problem sträcker sig till alla de hjälpstorheter som krävs för sådana analyser, och inte är begränsade till den formella lösningen av problemet med linjära minsta kvadrater.

Matrisberäkningar, som alla andra, påverkas av avrundningsfel . En tidig sammanfattning av dessa effekter, angående valet av beräkningsmetoder för matrisinversion, gavs av Wilkinson.

Se även

Vidare läsning

Ake Bjorck, Numeriska metoder för problem med minsta kvadrater, SIAM, 1996.
RW Farebrother, Linear Least Squares Computations , CRC Press, 1988.
Barlow, Jesse L. (1993), "Kapitel 9: Numeriska aspekter av att lösa linjära minsta kvadraters problem", i Rao, CR (red.), Computational Statistics , Handbook of Statistics, vol. 9, North-Holland, ISBN 0-444-88096-8
Björck, Åke (1996). Numeriska metoder för minsta kvadraters problem . Philadelphia: SIAM. ISBN 0-89871-360-9 .
Goodall, Colin R. (1993), "Kapitel 13: Computation using the QR-decomposition", i Rao, CR (red.), Computational Statistics , Handbook of Statistics, vol. 9, North-Holland, ISBN 0-444-88096-8
National Physical Laboratory (1961), "Kapitel 1: Linjära ekvationer och matriser: direkta metoder", Modern Computing Methods , Notes on Applied Science, vol. 16 (2:a uppl.), Hennes Majestäts brevpapperskontor
National Physical Laboratory (1961), "Kapitel 2: Linjära ekvationer och matriser: direkta metoder på automatiska datorer", Modern Computing Methods , Notes on Applied Science, vol. 16 (2:a uppl.), Hennes Majestäts brevpapperskontor