反復的に再重み付けされた最小二乗法

反復再加重最小二乗法( IRLS ) は、 pノルム形式の目的関数を持つ特定の最適化問題を解くために使用されます。

$${\displaystyle \mathop {\operatorname {arg\,min} } _{\boldsymbol {\beta }}\sum _{i=1}^{n}{\big |}y_{i}-f_{i}({\boldsymbol {\beta }}){\big |}^{p},}$$

各ステップで次の形式の重み付き最小二乗問題を解く反復法: ^[1]

$${\displaystyle {\boldsymbol {\beta }}^{(t+1)}={\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}({\boldsymbol {\beta }}^{(t)}){\big |}y_{i}-f_{i}({\boldsymbol {\beta }}){\big |}^{2}.}$$

IRLS は、一般化線型モデルの最大尤度推定値を見つけるために使用され、ロバスト回帰では、最小二乗誤差ではなく最小絶対誤差を最小化するなどして、正規分布するデータ セット内の外れ値の影響を軽減する方法として、M 推定値を見つけるために使用されます。

線形計画法や凸計画法に対する IRLS の利点の 1 つは、ガウス・ニュートン法やレーベンバーグ・マルカート法の数値アルゴリズムで使用できることです。

IRLSは、圧縮センシング問題におけるℓ ₁最小化と平滑化されたℓ _p最小化（ p  < 1）に使用できます。このアルゴリズムは、一般にスパース解の十分条件である制限付き等長性特性の下で、 ℓ _{1ノルムに対して線形収束率を持ち、} t  < 1のℓ _tに対して超線形であることが証明されています。^{[2] [3]}

線形回帰問題 のL ^pノルムを最小化するパラメータβ  = ( β ₁ , …, β _k ) ^{Tを見つけるには、}

$${\displaystyle {\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}{\big \|}\mathbf {y} -X{\boldsymbol {\beta }}\|_{p}={\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}\left|y_{i}-X_{i}{\boldsymbol {\beta }}\right|^{p},}$$

IRLSアルゴリズムのステップt  + 1では、重み付き線形最小二乗問題を解く必要がある: ^[4]

$${\displaystyle {\boldsymbol {\beta }}^{(t+1)}={\underset {\boldsymbol {\beta }}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}^{(t)}\left|y_{i}-X_{i}{\boldsymbol {\beta }}\right|^{2}=(X^{\rm {T}}W^{(t)}X)^{-1}X^{\rm {T}}W^{(t)}\mathbf {y} ,}$$

ここで、W ^{( t ) は重みの}対角行列であり、通常、すべての要素は次のように初期設定されます。

$${\displaystyle w_{i}^{(0)}=1}$$

各反復後に次のように更新されます。

$${\displaystyle w_{i}^{(t)}={\big |}y_{i}-X_{i}{\boldsymbol {\beta }}^{(t)}{\big |}^{p-2}.}$$

p  = 1の場合、これは最小絶対偏差回帰に対応します（この場合、問題は線形計画法^[5]を使用してアプローチした方が正確になるため、結果は正確になります）。式は次のようになります。

$${\displaystyle w_{i}^{(t)}={\frac {1}{{\big |}y_{i}-X_{i}{\boldsymbol {\beta }}^{(t)}{\big |}}}.}$$

ゼロ除算を避けるために正規化を行う必要があるため、実際の式は次のようになります。

$${\displaystyle w_{i}^{(t)}={\frac {1}{\max \left\{\delta ,\left|y_{i}-X_{i}{\boldsymbol {\beta }}^{(t)}\right|\right\}}}.}$$

ここで、0.0001のような小さな値です。^[5]重み関数におけるの使用は、ロバスト推定におけるHuber損失関数と同等であることに注意してください。^[6]${\displaystyle \delta }$${\displaystyle \delta }$

• 実行可能な一般化最小二乗法
• ワイズフェルドのアルゴリズム（幾何中央値を近似する）は、IRLSの特殊なケースとして見ることができる。

• Åke Björck 著「最小二乗問題の数値解析法」(第 4 章: 一般化最小二乗問題)
• コンピュータグラフィックスのための実用的な最小二乗法。SIGGRAPH コース 11

• 不確定な線形システムを反復的に解く