完全に理解した気がする

#やさしくしてね❤️
今回は $n$ 次元空間中に与えられた点集合への部分空間やアフィン空間の当てはめ(fitting)を考える。
※アフィン空間は部分空間を一般の位置に平行移動したもの

(例えば平面状の点列への直線のfittingとか、、、)


fittingはまず低次元のものから始めて徐々に正確性の高い高次元の空間をfittingしていく。
これは信号処理やパターン認識において「カルーネン・レーベ展開」と言ったり、統計学では「主成分分析」と言ったりする。

#部分空間の当てはめ
$n$次元部分空間$\mathcal{R^n}$に$N$点$x_1,...,x_N$が与えられた時、それらにもっとも近い$r$次元部分空間を求める問題を考える。
(当然$N\geq r$である)

例えば平面状に存在する点から原点を通る線を求めるとか、、、


![fig1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/695441/e8e95fd7-0f4b-a90f-b922-256a0c86d804.png)

<details>https://www.researchgate.net/figure/A-simple-example-illustrating-the-behavior-of-PCA-left-and-our-algorithm-right-in_fig1_261128809
<summary>引用元


部分空間を求めるってことはそれを張る基底を求めるって事

当てはめる$r$次元部分空間$\mathcal{U}$(なんかおかしい)の正規直交基底を$u_1,...,u_r$とする。
ここで、$\mathcal{R^n}$全体の正規直交基底に拡張したものを{$u_1,...,u_n$}とすると、上であげた問題は
$u_1,...u_r$の張る部分空間$\mathcal{U}$(おかしい)が、与えられた$N$点に近いような$\mathcal{R^n}$の正規直交基底{$u_i$}を求めることと言い換えられる。

各点$x_\alpha$の部分空間$\mathcal{U}$（お）までの距離は、$\mathcal{U}$からの反射影$P_\mathcal{U^\bot}x_\alpha$ の長さに等しい。[^1]
[^1]: fig. 7.2参照

$1$章でやった通り $P_\mathcal{U^\bot}=\sum_{i=r+1}^nu_iu_i^T$は$\mathcal{U}$の直交補空間$\mathcal{U^\bot}$への射影行列である。


したがって、$N$点$x_1,...x_N$から、部分空間$\mathcal{U}$までの距離の二乗和は
$$J=\Sigma_{\alpha=1}^N\||P_\mathcal{U^\bot}x_\alpha\||^2$$
と書ける。

<details>$$\||x\||^2=\||P_\mathcal{U}x\||^2+\||P_\mathcal{U^\bot}x\||$$ <summary>式1.12
</summary></details>
より、これは次のように直せる。

$$
J=\Sigma_{\alpha=1}^N(\||x_\alpha\||^2-\|P_\mathcal{U}x_\alpha\||^2|=\Sigma_{\alpha=1}^N\||x_\alpha\||^2-\Sigma_{\alpha=1}^N\||P_\mathcal{U}x_\alpha\||^2)
$$

この$2$乗和を最小にするには、各点の部分空間$\mathcal{U}$への射影長の$2$乗和
$$
K=\Sigma_{\alpha=1}^N\||P_\mathcal{U}x_\alpha\||^2
$$
を最大にすることでもある。
![fig2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/695441/92a78c39-5dbe-60d3-0943-6649a3550693.png)


<details>https://gigazine.net/news/20200126-3d-games-vector/<summary>引用元
</details></summary>
まあこの角度を小さくすることが再現度の高さにつながるって言いたい

#階層的当てはめ

まずは1次元部分空間(すなわち直線)への当てはめを考える。
基底を$v$(単位ベクトル)とすると各点$x_\alpha$のその方向への射影長は<$x_\alpha,v$>である。
全ての点に対する2乗和は以下のようになる。
$$
K=\Sigma_{\alpha=1}^N\<x_\alpha,v\>^2=\Sigma_{\alpha=1}^Nv^Tx_\alpha x_\alpha^Tv=\<v,(\Sigma_{\alpha=1}^Nx_\alpha x_\alpha^T)v>=\<v, \Sigma v\>
$$
ただし
$$
\Sigma=\Sigma_{\alpha=1}^Nx_\alpha x_\alpha^T
$$
とおいた。
これはモーメント行列や散乱行列、共分散行列と呼ぶ。
$$
\<v, \Sigma v\>
$$
は対称行列$\Sigma$の単位ベクトル$v$に対する二次形式なので(Appendix参照)、
これを最大にする$v$は行列$\Sigma$の最大固有値に対する単位固有ベクトルであり、
それに対する$K$の値が$\Sigma$の最大固有値に等しい。
$$
\Sigma=\Sigma_{\alpha=1}^Nx_\alpha x_\alpha^T
$$
より$\Sigma$は半正値対称行列であり、固有値は全て非負である。
その固有値を $\sigma_1^2,...\sigma_n^2≥0$ と書くと$\Sigma$は以下のように固有値分解することができる。
$$
\Sigma=\sigma_1^2u_1u_1^T+\cdots+\sigma_n^2u_nu_n^T 
$$
$$
ただし,\sigma_1^2≥\cdots≥\sigma_n^2≥0
$$

つまり点集合{$x_\alpha$} ,$\alpha=1,...,N$に当てはまる$1$次元部分空間$\mathcal{U}_1$の基底は

$v=u_1$であり、それに対する射影長の2乗和は$\sigma_1^2$に等しい。
**<font color="Red">前にkndさん担当分のとこで少し話が出たように固有値最大の基底がもっとも広い分散を持つのでまずはそれに合わせてfitting(=近似)しようって話。</font>**

$N$点$x_1,...x_N$が平面上に広がっている場合この近似では不十分なので、次は$u_1$と$u_2$で張る部分空間に当てはめていく。。。。
このようにして最適な近似を求めていく。
また、
$$
J=\Sigma_{\alpha=1}^N\||x_\alpha\||^2-\Sigma_{\alpha=1}^N\||P_\mathcal{U}x_\alpha\||^2=\Sigma_{\alpha=1}^N\||x_\alpha\||^2-K
$$
であり
$$
\Sigma=\Sigma_{\alpha=1}^Nx_\alpha x_\alpha^T
$$
より$$
\Sigma_{\alpha=1}^N\||x_\alpha\||^2=\mathrm{Tr}\Sigma=\sigma_1^2+\cdots+\sigma_n^2
$$
である。
よって$\mathcal{U_r}$への距離の二乗和は
$$
J=\sigma_{r+1}^2+\cdots+\sigma_n^2
$$
**<font color="Red">
つまり部分空間で当てはめていない$\mathcal{R^n}$の残った基底に対する$\Sigma$の固有値の2乗和となる。
</font>**
$$
J=\sigma_{r+1}^2+\cdots+\sigma_n^2
$$
ちなこれを残差(Residual)と呼び、当然当てはめる次元を増やしていけば再現度は高くなる($=J$は小さくなる)

#特異値分解による当てはめ

先ほどは$N$点$x_1,...x_N$によく当てはまる$r$次元部分空間$\mathcal{U_r}$を求めるために、共分散行列$\Sigma$を計算し、固有値分解する手法を紹介した。

ここでは特異値分解を用いた方法を紹介する。
n次元ベクトル$x_\alpha$, $\alpha=1,...,N$を並べた$n\times N$行列を
$$
X=(x_1 \cdots x_N)
$$
とする。
先ほどの共分散行列$
\Sigma=\Sigma_{\alpha=1}^Nx_\alpha x_\alpha^T
$は
$$
\Sigma=XX^T
$$
と書けるので、、、
$N≥n$より行列$X$の特異値分解は
$$
X=\sigma_1u_1v_1^T+\cdots+\sigma_nu_nv_n^T
$$
となる。($\Sigma=XX^T$の固有値は$X$の特異値の$2$乗に等しいため)
また、特異ベクトル$u_i,v_i$はそれぞれ$XX^T$、$X^TX$の固有ベクトルでもある。
ゆえに、$N$点$x_1,...x_N$に$r$次元部分空間$\mathcal{U_r}$を当てはめるには$N$点を並べた行列$X$の特異値分解を用いても良い。
左特異ベクトル$u_1,...u_r$が$\mathcal{U_r}$の基底となり、残差は$
J=\sigma_{r+1}^2+\cdots+\sigma_n^2
$で与えられる。

計算量は特異値分解を用いたほうが少なくて済むため、こちらの方が便利。。。

#アフィン空間の当てはめ
部分空間の当てはめは直線や平面の当てはめの一般化である。
一方で、実際には原点を通らない直線や平面を当てはめる必要も生じる。
アフィン空間とは部分空間を平行移動したものである。
$\mathcal{R^n}$の$r$次元アフィン空間$\mathcal{A^r}$は$n$次元空間$\mathcal{R^n}$中の$1$点$g$と、そこを始点とする$r$本の線型独立なベクトル$u_1,...u_r$によって指定され、任意の$$
x=g+c_1u_1+\cdots+c_ru_r
$$
と表せる点全体である。

基底{$u_i$} ,$i=1,...,r$は正規直交基底と考えることができる。
また、$r$次元アフィン空間を指定するには、$n$次元空間$\mathcal{R^n}$にそれが通る$r+1$点を指定しても良い。
ただし。どの一点を原点とみなしても残りの$r$点が$r$次元部分空間を張るようにとるとする。
このような$r+1$点は**一般の位置**にあるという。

さて、空間$\mathcal{R^n}$に$N$点$x_1,...x_N$ が与えられた時、これを近似する$r$次元アフィン空間$\mathcal{A^r}$を当てはめる問題を考える。ただし$N≥r+1$とする。

$\mathcal{A^r}$を定めるには、それが通る点$g$とそこを始点とする正規直交基底{$u_i$} を定めれば良い。
まずは点$g$を指定する。これは$0$次元のアフィン空間の当てはめであるので、距離の二乗和を最小にする点(=重心)$$
g=\frac{1}{N}\Sigma_\{\alpha=1}^Nx_\alpha
$$
である。
$g$が定まればそこを始点とする$r$次元部分空間を当てはめれば良いので、前々節と同様に$$
\Sigma=\Sigma_{\alpha=1}^N(x_\alpha-g)(x_\alpha-g)^T
$$
を計算し、その固有値分解すると、$u_1,...,u_r$ が$g$の周りにアフィン空間を張る。

さっきも言ったように実際には$X=(x_1-g\cdots x_r-g)$を特異値分解した方が早い。