Appliquer une régression de crête pour un système d'équations sous-déterminé?

9

Lorsque , le problème des moindres carrés qui impose une restriction sphérique à la valeur de peut être écrit comme pour un système surdéterminé. \ | \ cdot \ | _2 est la norme euclidienne d'un vecteur.y=Xβ+eδβ

min yXβ22s.t.  β22δ2
2

La solution correspondante à β est donnée par

β^=(XTX+λI)1XTy ,
qui peut être dérivée de la méthode des multiplicateurs de Lagrange ( λ est le multiplicateur):
L(β,λ)=yXβ22+λ(β22δ2)

Je comprends qu'il existe une propriété qui

(XTX+λI)1XT=XT(XXT+λI)1 .
Le côté droit ressemble au pseudo-inverse de la matrice de régresseur X dans le cas sous-déterminé (avec le paramètre de régularisation ajouté, λ ). Est-ce à dire que la même expression peut être utilisée pour approximer β pour le cas sous-déterminé? Existe-t-il une dérivation distincte pour l'expression correspondante dans le cas sous-déterminé, car la contrainte de restriction sphérique est redondante avec la fonction objectif (norme minimale de β ):

min. β2s.t. Xβ=y .
hatmatrix
la source

Réponses:

12

En commençant par la formulation du problème de régression des crêtes comme

minXβy22+λx22

vous pouvez écrire le problème comme

minAβb22

A=[XλI]

et

b=[y0].

La matrice est de rang complet de la colonne à cause de la partie. Ainsi, le problème des moindres carrés comme solution uniqueAλI

β^=(ATA)1ATb

En écrivant ceci en termes de et , et en simplifiant beaucoup de 0, nous obtenonsXy

β^=(XTX+λI)1XTy

Rien dans cette dérivation ne dépend si a plus de lignes ou de colonnes, ou même si a un rang complet. Cette formule est donc applicable au cas indéterminé. XX

C'est un fait algébrique que pour ,λ>0

(XTX+λI)1XT=XT(XXT+λI)1

Ainsi, nous avons également la possibilité d'utiliser

β^=XT(XXT+λI)1y .

Pour répondre à vos questions spécifiques:

  1. Oui, les deux formules fonctionnent pour le cas indéterminé ainsi que pour le cas surdéterminé. Ils ont également le travail si est inférieur au minimum du nombre de lignes et de colonnes de . La deuxième version peut être plus efficace pour les problèmes indéterminés car est plus petit que dans ce cas. rank(X)XXXTXTX

  2. Je ne suis au courant d'aucune dérivation de la version alternative de la formule qui commence par un autre problème des moindres carrés amortis et utilise les équations normales. Dans tous les cas, vous pouvez le dériver de manière simple en utilisant un peu d'algèbre.

Il est possible que vous pensiez au problème de régression des crêtes sous la forme

minβ22

sujet à

Xβy22ϵ.

Cependant, cette version du problème de régression des crêtes conduit simplement au même problème des moindres carrés amortis .minXβy22+λβ22

Brian Borchers
la source
2
Il convient de noter ce qui se passe dans la limite lorsque passe à 0 si a un rang de ligne complet ou un rang de colonne complet. Si a le rang de colonne complet, alors dans la limite, vous obtenez le pseudoinverse . De même, si a un rang complet, alors à la limite, vous obtenez le pseudo-inverse . Donc, cela fonctionne comme prévu. λXX(XTX)1XTXXT(XXT)1
Brian Borchers
C'est une réponse incroyablement complète et la dérivation des tableaux augmentés (plus l'algèbre que j'ai manquée) est très satisfaisante. Je ne pensais pas au problème de régression des crêtes sous la forme que vous avez présentée à la fin, mais il est intéressant de voir qu'il conduit à la même fonction objective. Un grand merci!
hatmatrix
1
Merci. Je vais insérer un plug sans vergogne ici - Vous pouvez trouver cela (et beaucoup de matériel connexe) dans le manuel sur l'estimation des paramètres et les problèmes inverses que j'ai co-écrit avec Rick Aster et Cliff Thurber.
Brian Borchers
1
Permettez-moi également d'ajouter que le calcul de cette matrice inverse n'est généralement pas la meilleure façon d'utiliser cette formule. En fonction de la taille et la parcimonie possible de vous pourriez être beaucoup mieux à l' aide d' un schéma itératif ou en utilisant simplement la factorisation de Cholesky de la matrice . XXTX+λI
Brian Borchers
Merci pour vos suggestions! J'apprécie la référence à votre livre car j'ai eu du mal à trouver un texbook sur ce matériel. Notre taille de données n'est en fait pas très grande (seulement que nous devrons peut-être appliquer ce nombre de fois à des ensembles de données séparés), donc peut se prêter à l'inverse direct, mais merci pour les pointeurs supplémentaires!
hatmatrix