一般化レイリー商最大化・最小化問題 その４

<<前回までの記事>>
第１回，第２回, 第３回

こんにちは～
もうＧＷも終わってしまいますね(:_;)

前回までは対称行列のH-直交行列による
スペクトル分解（対角化）を導くために色々とやってきました．
今日はそれを使って遂にR(x)の最大化問題を解きましょう！！

まずは前回のおさらいです( ..)φ
実対称行列 Aのスペクトル分解は…

A = \sum_{i=1}^n \lambda_i H v_i v_i^t H

と書けるのでした！
ここで λ_i は一般化固有値で v_i は λ_i に対応する一般化固有ベクトルでしたね～

これより，Aの二次形式は

\begin{aligned} x^t A x &= \sum_{i=1}^n \lambda_i x^t H v_i v_i^t H x 
= \sum_{i=1}^n \lambda_i \langle v_i, x \rangle_H^2 \\
&\le \lambda_{\rm max} \sum_{i=1}^n \langle v_i, x \rangle_H^2 = \lambda_{\rm max} \lVert x \rVert_H^2\end{aligned}

と上から抑えられます．
ここで λ_max は最大の λ_i で，最後の等号は v_i がH-正規直交基底をなすことから

x = \sum_{i=1}^n \langle x, v_i \rangle_H v_i

と分解できるので成り立ちます．

従ってx ≠ 0ならば

R(x) = \frac{x^t A x}{x^t H x} = \frac{x^t A x}{\lVert x \rVert_H^2} \le \lambda_{\rm max}

が成り立ちます！
さらに，等号は x が λ_max に対応する一般化固有ベクトル v_max の
時に成り立つことは明らかでしょう！

まとめ： 一般化Rayleigh商は(A, H)の最大一般化固有値 λ_max を最大値に持ち，それは λ_max に対応する一般化固有ベクトル v_max で達成される：

R(x) \le R(v_{\rm max}) = \lambda_{\rm max}\quad \text{for}\ x \neq 0

そのうちこれを解くアルゴリズムなんかについても書けたらいいと思ってます！
それでは～(^^)/

～＊～＊～ 補足 ～＊～＊～

実はこの問題，変数変換を考えると
通常のRayleigh商最大化問題に帰着されます(-_-;) ぉぃぉぃ

Hは実対称なので直交行列で対角化できます：

H = U \Sigma U^t;\quad U^tU = U U^t = I, \quad \Sigma = \mathop{\rm diag}(\sigma_1, \dots, \sigma_n)

さらに，正定値性はσ_i > 0 を保証するので

D = \mathop{\rm diag}(\sqrt{\sigma}_1, \dots, \sqrt{\sigma}_n)

を定義することができます．
従って G = UD とおくと H = GG^tです．

そこで y = G^txと変数変換をすると，
Gが正則（G^-1 = D^-1U^t）であるので

\frac{x^t A x}{x^t H x} = \frac{y^t G^{-1} A G^{-t} y}{y^t y}

となります．
右辺は y に関して通常のRayleigh商だから
G^-1AG^-tの最大固有値に対応する固有ベクトルで最大になります．

Gの定義と変数変換の式から

G^{-1}AG^{-t} y= \lambda y \Leftrightarrow Ax = \lambda H x

になるので，結局答えは(A, H)の最大の一般化固有値という風に結論できますね．

この方式は簡単ですけど，背後に潜む直交性などが隠れてしまいます．
ということで今回は新しい直交性を導入した解法を紹介してきました．