特異値分解

特異値分解についてお話しします。固有値分解が対象としているのは正方行列でした。特異値分解では、これを一般の行列に拡張します。つまり、行列 A に対して、直交行列 U, V、対角行列 S を用いて \begin{equation} \rm A = U S V^t \end{equation} のように分解します。 このとき、 \begin{equation} \rm S = \begin{pmatrix} s_1 & & \\ & s_2 & \\ & & \ddots \\ \end{pmatrix}, \\ \rm U = \begin{pmatrix} \vec{u_1} & \vec{u_2} & \cdots & \\ \end{pmatrix} \\ \rm V = \begin{pmatrix} \vec{v_1} & \vec{v_2} & \cdots & \\ \end{pmatrix} \end{equation} です。\( \rm S \) は特異値と言います。分解するときに使う直交行列はU, Vの2個になりますが、「正方行列の」という制限が外れます。従って、どんな行列にも使えます。ここで注意すべき点は、対角行列 S の行と列の数が異なるということです。対角からはみ出る要素はゼロになります。また、直交行列 U, V の要素数は異なります。

行列 A は正方行列である必要はありませんが、\( \rm AA^t \) は常に正方行列（対称行列）になります。ということは、この正方行列 \( \rm AA^t \) に対して固有値分解できるということです。つまり、対角行列 D として \begin{equation} \rm AA^t = U D U^t \end{equation} と変形できます。一方で、 \begin{equation} \rm AA^t = U S V^t (U S V^t)^t = U S V^t V S^t U^t = U SS^t U^t \end{equation} ですから、\( \rm D = SS^t \)です。同様に、 \begin{equation} \rm A^t A = V S^t S V^t \end{equation} です。

\begin{equation} \rm S^t S = \begin{pmatrix} s_1^2 & & \\ & s_2^2 & \\ & & \ddots \\ \end{pmatrix} \end{equation} ですから、\( \rm A^t A \) を求めて、その固有値を計算し、その正の平方根をとれば、特異値が求まるということです。

固有値分解

固有値と固有ベクトルの話は少し前にやりました。今回は固有値分解についてです。固有値分解は実質的に対角化そのものです。で、対角化とは何だったかと言いますと、正方行列 A に対して、直交行列 P, 対角行列 D として \begin{equation} \rm {A = P D P^t} \end{equation} のような形にすることです。このとき、 \begin{equation} \rm D = \begin{pmatrix} \lambda_1 & & \\ & \lambda_2 & \\ & & \ddots \\ \end{pmatrix}, \\ \rm P = \begin{pmatrix} \vec{v_1} & \vec{v_2} & \cdots & \\ \end{pmatrix} \end{equation} です。ただし、\( \lambda \) は固有値、\( \vec{v} \) は固有ベクトルです。D は固有値が対角成分に並んだ形になっていますから、対角化です。

で、 \( \rm {A = P D P^t} \) という形に変換したことは、正方行列 A を P の要素（ P に含まれる直交ベクトル）それぞれの和で表したことになります。つまり、 \begin{equation} {\rm A} = \lambda_1 \vec{v_1} \vec{v_1^t} + \lambda_2 \vec{v_2} \vec{v_2^t} + \cdots \end{equation} です。固有値は各項の重みを表していることになりますから、ゼロに近い固有値は無視して計算してしまっても、ある程度の精度が保てます。これは次元削減したことになり、計算コストを下げたりデータ量を減らしたりできます。あとは、\( \rm A \)の累乗の計算が簡単になります。

Google Colaboratoryを使えるようにする

Google Colaboratoryを使おうと思って、net検索すると、Google Driveから「アプリを追加」で対応するようなことが記載されています。で、その通りやって、Google Colaboratoryを登録するのだけど、なぜか関連のフォルダもファイルもできないし、一向に使えるようになりません。

次のようにすると、自動的にGoogle Driveにフォルダやファイルが作成されて、Google Colaboratoryが使える状態になりました。

1. chromeでGoogleにログインする（IDとPWを入力する）
2. chromeから直接Google Colaboratoryのサイトにアクセスする
3. メニューの「ファイル」タブをクリックし、「Python3の新しいノートブック」をクリックする

これで、Google Driveに「Colab Notebooks」というフォルダができ、その中に「Untitled0.ipynb」というファイルができているはずです。

MinGWでOpenCVを使えるようにする

前回、MSYS2をインストールして、gcc関連のパッケージを導入しましたので、C++のプログラムがコンパイルできるはずです。で、以下のようなC++プログラムを「test01.cpp」というファイル名で用意したとします。

#include <iostream>
using namespace std;
int main(){
  cout << "Hello, World." << endl;
  return 0;
}

MinGW 64bitのshellを起動し、test01.cppを作ったディレクトリに移動します。

cd f:\OpecCV

で、以下のコマンドを入力します。

gcc test01.cpp -o test01 -lstdc++

そうしますと、「test01.exe」という実行ファイルができます。これを実行しますと、「Hello, World」が表示されます。

次に、OpenCVを導入します。OpenCVは、コンピュータ・ビジョンに関する機能を持つライブラリです。MSYS2ではOpenCVパッケージが用意されていて、以下のようにするとインストールできます。

pacman -S mingw-w64-x86_64-opencv

で、以下のようなC++プログラムを「test02.cpp」というファイル名で用意したとします。

#include <opencv2/core/core.hpp>
#include <opencv2/highgui.hpp>
#include <iostream>
using namespace cv;
using namespace std;
int main()
{
    Mat img = cv::imread("image.png");
    imshow("image", img);
    waitKey(0);
    return 0;
}

このプログラムをgccでコンパイルするのですが、設定が色々面倒ですので、以下のようなMakefileを作ります。

#Makefile
INC = -I "C:\msys64\mingw64\include\opencv4"
DIR =  -L "C:\msys64\mingw64\bin"
FLAGS = -lstdc++ -lopencv_core410 -lopencv_highgui410 -lopencv_imgcodecs410
OBJS = test02

main:
 gcc $(INC) $(DIR) test02.cpp -o $(OBJS) $(FLAGS)

で、以下のようにmakeすると、実行ファイルができます。

make

この実行ファイルを実行すれば、画像が表示されます。

MSYS2を通してMinGWを使う

Windows10でC++プログラミングをするとき、統合開発環境としてVisual Studioを使うのが一般的だと思います。ただ、Visual Studioをインストールすると、Windows10の設定を色々変えるので、不都合が生じるのが不安です（実際に生じたわけではありません）。代替措置としてgccを使うことを考えます。Windowsでgccを使えるようにする開発環境として、MinGW (Minimalist GNU for Windows)があります。今回は、これをWindows10にインストールします。

ただ、MinGWの最低限の機能だけをインストールするというわけにもいかないでしょう。gccのバージョンは一定期間ごとにupdateされますし、ライブラリだって利用したいでしょう。そうすると、色んなパッケージをインストールすることになるのですが、それらも管理していかないといけません。で、MSYS2 (Minimal SYStem 2)というのを使います。これは、Windows上で動作するプログラム開発環境を提供するシステムです。UnixやLinuxと同様にshell(bash)端末でコマンドを使って操作します。 ということで、これからやることは、

MSYS2をインストールする

MinGWをインストールする

です。

まず、MSYS2のページにアクセスして、MSYS2のインストーラー「msys2-x86_64-20190524.exe」をダウンロードします。

次に、ダウンロードした「msys2-x86_64-20190524.exe」を実行します。基本的にポップアップ画面の右下の「次へ」をクリックしていけば、「C:\msys64」にMSYS2がインストールされます。Windowsのメニューで「MSYS2 64bit」をクリックして、以下のようなshellが現れればインストール成功です。

で、パッケージのデータベースを更新します。

pacman -Sy

そして、以下のコマンドでパッケージを更新します。

pacman -Su

ここで、以下のような警告メッセージが出たら、MSYS2を一旦閉じ、もう一度立ち上げ直して上記コマンドを再度実行します。

警告: terminate MSYS2 without returning to shell and check for updates again
警告: for example close your terminal window instead of calling exit

警告メッセージが出なくなればOKです。

次に、MinGW-w64(64bit)とその関連パッケージをインストールします。

pacman -S base-devel
pacman -S mingw-w64-x86_64-toolchain

一旦、MSYS2のshellを閉じて、MinGW 64-bitのshelを起動します。そこで、以下のコマンドを実行して、下のような表示が出ればOKです。

gcc --version

畳み込み積分

今、時間 \( t \) と共に変化する信号 \( x(t) \) が下の図の太線のようになっていたとして、この信号を、先に示した単位インパルス関数を用いて表すことを考えよう。単位インパルス関数は、面積1の長方形 \( \delta_\varepsilon (t) (1 < t < \varepsilon) \) で \( \varepsilon \to 0 \) の極限をとったものとして定義された。そこで、この \( \delta_\varepsilon (t) \) を少しずつずらして、 \( x(t) \) を構成する。\( x(t) \) を離散時間 \( \varepsilon \) で分割すると、下図の赤い矩形のようになる。

時間 \( t \) での高さは、 \( x(k\varepsilon) \delta_\varepsilon (t-k \varepsilon) \varepsilon \) で近似できる。 \( k \) は、時間幅 \( \varepsilon \) が何個あるかを表し、\( x(k \varepsilon) \) は \( t=k \varepsilon \) のときの \( x(t) \) の値を表す。\( \delta_\varepsilon (t-k \varepsilon) \) は \( \delta_\varepsilon (t) \) が時間 \( k \varepsilon \) だけずれたことを表し、\( \delta_\varepsilon (t-k \varepsilon) \varepsilon \) は1である。例えば、\( k=1 \) なら、\( x(\varepsilon) \delta_\varepsilon (t-\varepsilon) \varepsilon \) となるし（下図一つ目）、\( k=-2 \) なら、\( x(-2 \varepsilon) \delta_\varepsilon (t+2 \varepsilon) \varepsilon \) となる（下図二つ目）。

これらを足し合わせると、 \begin{equation} x(t) \approx \sum_{k=-\infty}^\infty x(k\varepsilon) \delta_\varepsilon (t-k \varepsilon) \varepsilon \end{equation} となる。で、近似を等式にするには、\( \varepsilon \to 0 \) の極限をとればよい。そうすると、\( \delta_\varepsilon (t) \) は単位インパルス関数 \( \delta (t) \) となり、次式が得られる。 \begin{equation} x(t) = \int_{-\infty}^\infty x(\tau) \delta(t-\tau) d\tau \end{equation}

重ね合わせの理

重ね合わせの理は、「電気回路で複数の電源があるとき、各電源（起電力）によって流れる電流を求め、それらの足し合わせが回路全体の電流に等しい」という定理です。例えば、以下のような電気回路を考えたとき、この回路に流れる電流はオームの法則から \begin{equation} I = \frac{E_1 + E_2}{R} \end{equation} となります。

重ね合わせの理を使えば、一方の電源を取り除いて、片方ずつ電流を求め、後でそれらを足し合わることで、全体の電流を求めることができます。で、まず、一方の電源 \( E_1 \) を残して、もう一方の電源 \( E_2 \) を短絡しますと、この回路に流れる電流は、 \begin{equation} I_1 = \frac{E_1}{R} \end{equation} となります。

次に、反対側の電源を戻して、先ほど残した電源を短絡します。そうしますと、この回路に流れる電流は、 \begin{equation} I_2 = \frac{E_2}{R} \end{equation} となります。

で、求めた電流をそれぞれ足し合わせると、以下のように回路全体を流れる電流が求められるのです。 \begin{equation} I = \frac{E_1 + E_2}{R} \end{equation} この回路は単純ですので、重ね合わせの理を用いなくても、冒頭のように起電力を足し合わせてオームの法則を適用するやり方で簡単に求めることができます。しかし、回路が複雑になると、重ね合わせの理は重宝することになります。

ここで、\( E_1, E_2 \) を入力、\( I_1, I_2 \) を出力と考えたとき、以下のことが成り立ちます。

1. 入力 \( {E_1 + E_2} \) に対する出力は \( I_1 + I_2 \)
2. 入力 \( \alpha E_1 \) に対する出力は \( \alpha I_1 \) （ \( \alpha \) は定数 ）

このような関係は線形ですし、これを入出力システムとみれば、線形システムということになります（下図）。