Marchenko–Pasturの法則

同義語:Marchenko–Pastur lawMarčenko–Pastur lawMarchenko–Pastur分布Marchenko–Pastur distribution

概要

Marchenko–Pasturの法則(Marchenko–Pastur law)とは、成分が独立で平均 $0$、分散 $1$ の同じ分布に従う $N\times M$ 行列 $X$ について、標本共分散行列 $\frac1MXX^{\mathsf T}$ の固有値の経験分布が、$N/M\to y\in(0,\infty)$ のとき、区間 $[(1-\sqrt y)^2,(1+\sqrt y)^2]$ の上の Marchenko–Pastur 分布($y>1$ では $0$ に質量 $1-1/y$ の原子つき)に確率収束の意味で弱収束するという定理である。極限は成分の分布の形によらない。行列のべきの跡を 2 部グラフの上の閉じた道で数えると、極限のモーメントは奇数の高さからの上りの数で重みづけた Dyck 経路の数になる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Wignerの半円則, 実対称行列, Catalan数, 分布収束

Marchenko–Pastur の法則(Marchenko–Pastur law)は、標本共分散行列の固有値の分布についての極限定理である。$N\times M$ の行列 $X$ の成分が独立同分布で、平均 $0$、分散 $1$ の同じ分布に従うとする。$N$ 次の行列 $S=\frac1MXX^{\mathsf T}$ は、各列を $N$ 次元の観測とみたときの標本共分散行列である。$N,M\to\infty$、$N/M\to y\in(0,\infty)$ とすると、$S$ の固有値の経験分布は区間 $[(1-\sqrt y)^2,(1+\sqrt y)^2]$ の上の決まった分布($y>1$ のときは $0$ の原子つき)に近づく(V. A. Marchenko と L. A. Pastur, 1967、MaP67)。
真の共分散行列は単位行列なので、観測の数 $M$ が次元 $N$ よりはるかに多ければ $S$ の固有値はみな $1$ に近い。$N$ と $M$ が同じ程度だと、固有値は $1$ の周りに幅 $4\sqrt y$ の程度に広がったまま残る。高次元のデータの 主成分分析 で、雑音だけから大きな固有値が出ることの説明になる。証明は Wignerの半円則 と同じモーメント法で、行列のべきの跡を 2 部グラフの上の閉じた道で数える。極限のモーメントは Dyck 経路を「奇数の高さからの上り」の数で重みづけて数えた多項式になる。

問い答え
仮定は成分が独立同分布、平均 $0$、分散 $1$、$N/M\to y\in(0,\infty)$(thm-mp-main)
極限はMarchenko–Pastur 分布 $\mu_y$(def-mp-law)
極限のモーメントDyck 経路の重みつきの数 $\beta_k(y)$(lem-mp-dyck、prop-mp-moments)
$y=1$ の場合半円分布の $x\mapsto x^2$ による像(ex-mp-square)
反例成分の独立性や、分布が $N$ によらないことを外すと成り立たない(ex-mp-counter)

設定と定義

$N$ 次実対称行列 $A$ の固有値を重複を込めて $\lambda_1,\dots,\lambda_N$ とし、経験固有値分布 を $L_A:=\frac1N\sum_i\delta_{\lambda_i}$ とする。$\langle L_A,x^k\rangle=\frac1N\operatorname{tr}A^k$ である(Wignerの半円則 と同じ記法)。

標本共分散行列

$\xi$ を $E[\xi]=0$、$E[\xi^2]=1$ をみたす実確率変数とする。各 $N$ について正の整数 $M=M(N)$ をとり、$X_N=(x_{ij})$ を成分が独立で $\xi$ と同じ分布に従う $N\times M$ 行列とする。
$$ S_N:=\frac1MX_NX_N^{\mathsf T} $$
を 標本共分散行列 という。$L_N:=L_{S_N}$ とおく。

$S_N$ は半正定値なので固有値は $0$ 以上である。$S_N$ の階数は $\min(N,M)$ 以下なので、$N>M$ なら $S_N$ は少なくとも $N-M$ 個の固有値 $0$ をもつ。

Marchenko–Pastur 分布

$y>0$ について $a:=(1-\sqrt y)^2$、$b:=(1+\sqrt y)^2$ とし、
$$ f_y(x):=\frac{\sqrt{(b-x)(x-a)}}{2\pi yx}\quad(a\le x\le b) $$
とおく($[a,b]$ の外では $0$)。$\mathbb{R}$ の上の確率測度
$$ \mu_y(dx):=\Bigl(1-\frac1y\Bigr)^{+}\delta_0(dx)+f_y(x)\,dx $$
を、比 $y$ の Marchenko–Pastur 分布 という。ここで $t^+=\max(t,0)$ である。

$\mu_y$ の全質量が $1$ であることは prop-mp-moments の証明で確かめる($f_y$ の積分は $y\le1$ で $1$、$y>1$ で $1/y$ である)。$y>1$ の原子 $1-1/y$ は、$N-M$ 個の固有値 $0$ の割合の極限である。

Marchenko–Pastur の法則

def-mp-sample の状況で $N\to\infty$、$N/M(N)\to y\in(0,\infty)$ とする。すべての有界連続関数 $f\colon\mathbb{R}\to\mathbb{R}$ と $\varepsilon>0$ について
$$ \lim_{N\to\infty}P\bigl(\lvert\langle L_N,f\rangle-\langle\mu_y,f\rangle\rvert>\varepsilon\bigr)=0 $$
である。すなわち $L_N$ は確率収束の意味で $\mu_y$ に弱収束する。

規約の違い

AGZ10 Exercise 2.1.18(pp. 20–21)は、成分の分散が $1/N$ の $N\times M$ 行列 $Y$ と $W=YY^{\mathsf T}$、$M/N\to\alpha\ge1$ で同じ定理を述べ、極限の密度を $\sqrt{(x-b_-)(b_+-x)}/(2\pi x)$、$b_\pm=(1\pm\sqrt\alpha)^2$ と書く。$W=\frac MN S$ なので、この記事の $\mu_y$($y=1/\alpha$)の $x\mapsto x/y$ による像にあたる。

モーメント法

この節では $\xi$ のすべてのモーメントが有限であると仮定し、$r_k:=\max(1,E[\lvert\xi\rvert^k])$ とおく。

Dyck 経路の重みつきの数え上げ

長さ $2k$ の Dyck 経路 とは、各項が $\pm1$ の列 $(s_1,\dots,s_{2k})$ で、部分和 $h_t:=s_1+\dots+s_t$(高さ、$h_0=0$)がすべて $0$ 以上で $h_{2k}=0$ となるものである。$s_t=+1$ を上り、$-1$ を下りという。その総数は Catalan数 $C_k$ である。経路 $P$ の上りのうち、出発の高さ $h_{t-1}$ が奇数のものの数を $u_{\mathrm{odd}}(P)$、偶数のものの数を $u_{\mathrm{even}}(P)$ と書き、
$$ \beta_k(y):=\sum_{P}y^{u_{\mathrm{odd}}(P)},\qquad \gamma_k(y):=\sum_Py^{u_{\mathrm{even}}(P)} $$
とおく(和は長さ $2k$ の Dyck 経路の全体、$\beta_0=\gamma_0=1$)。$\beta_k(1)=C_k$ である。

重みつきの数の漸化式

形式的冪級数 $B(z):=\sum_{k\ge0}\beta_k(y)z^k$ は
$$ B=1+zB+zyB(B-1) $$
をみたす。すなわち $k\ge1$ について $\beta_k=(1-y)\beta_{k-1}+y\sum_{j=0}^{k-1}\beta_j\beta_{k-1-j}$ である。

最初に高さ 0 へ戻る時刻で分ける

$k\ge1$ とし、長さ $2k$ の Dyck 経路 $P$ が最初に高さ $0$ へ戻る時刻を $2j+2$ とする。$P$ は、上り $1$ 歩、高さを $1$ 上げた長さ $2j$ の Dyck 経路 $P_1$、下り $1$ 歩、長さ $2(k-1-j)$ の Dyck 経路 $P_2$ を並べたものに一意に分かれ、逆にこの形の列は Dyck 経路である。
$P_1$ の部分は高さが $1$ ずれているので、$P_1$ の中で偶数の高さから出る上りは、$P$ の中では奇数の高さから出る。最初の上りは高さ $0$ から出る。よって
$$ u_{\mathrm{odd}}(P)=u_{\mathrm{even}}(P_1)+u_{\mathrm{odd}}(P_2),\qquad u_{\mathrm{even}}(P)=1+u_{\mathrm{odd}}(P_1)+u_{\mathrm{even}}(P_2) $$
である。$j$ と $P_1,P_2$ について和をとると、$\beta_k=\sum_{j}\gamma_j\beta_{k-1-j}$、$\gamma_k=y\sum_j\beta_j\gamma_{k-1-j}$ である。$\Gamma(z):=\sum\gamma_kz^k$ とおくと
$$ B=1+z\Gamma B,\qquad \Gamma=1+zyB\Gamma $$
である。第 1 式から $z\Gamma B=B-1$ なので、第 2 式は $\Gamma=1+y(B-1)$ となる。これを第 1 式に入れて $B=1+zB(1+y(B-1))$ を得る。$z^k$ の係数を比べると漸化式になる。$\square$

漸化式から順に計算すると次のとおりである。$y=1$ の列は Catalan 数である。

$k$$\beta_k(y)$$\beta_k(1)$
$1$$1$$1$
$2$$1+y$$2$
$3$$1+3y+y^2$$5$
$4$$1+6y+6y^2+y^3$$14$
$5$$1+10y+20y^2+10y^3+y^4$$42$

係数は Narayana 数 $\frac1k\binom kr\binom k{r-1}$ である($y^{r-1}$ の係数。$k\le8$ で数え上げと照合した)。この記事の証明はこの閉じた式を使わない。

跡の展開

行列の積の定義から
$$ \langle L_N,x^k\rangle=\frac1{NM^k}\sum_{\mathbf{i},\mathbf{j}}\prod_{t=1}^kx_{i_tj_t}x_{i_{t+1}j_t} $$
である。和は $\mathbf{i}=(i_1,\dots,i_k)\in\{1,\dots,N\}^k$、$\mathbf{j}=(j_1,\dots,j_k)\in\{1,\dots,M\}^k$ にわたり、$i_{k+1}:=i_1$ とする。行の頂点 $r_1,\dots,r_N$ と列の頂点 $c_1,\dots,c_M$ をもつ 2 部グラフの上で、各項は $2k$ 歩の閉じた道
$$ r_{i_1}\to c_{j_1}\to r_{i_2}\to c_{j_2}\to\dots\to c_{j_k}\to r_{i_1} $$
にあたる。辺 $\{r_i,c_j\}$ を 1 回通るごとに因子 $x_{ij}$ がつく。道の頂点と辺からなるグラフを $G$ とし、その行の頂点の数を $a$、列の頂点の数を $b$、辺の数を $e$ とする。$G$ は連結なので $a+b\le e+1$ で、等号は $G$ が木のときに限る。
2 つの道が、行の添字の全単射と列の添字の全単射で移り合うとき同値という。同値類は $(2k)^{2k}$ 個以下で、$(a,b)$ の同値類は $N(N-1)\cdots(N-a+1)\,M(M-1)\cdots(M-b+1)\le N^aM^b$ 本の道からなる。期待値は同値類の上で一定で、Hölder の不等式から絶対値は $r_{2k}$ 以下である。

モーメントの極限

$N\to\infty$、$N/M\to y$ のとき、$k\ge1$ について $E\langle L_N,x^k\rangle\to\beta_k(y)$ である。

2 部グラフの木の上の道を数える

どの道が残るか。 成分は独立で平均 $0$ なので、期待値が $0$ でない道では各辺が 2 回以上通られる。よって $2e\le2k$ で、$a+b\le k+1$ である。$a\ge1$ に注意する。$a+b\le k$ の同値類の寄与は、絶対値が
$$ (2k)^{2k}r_{2k}\frac{N^aM^b}{NM^k}=(2k)^{2k}r_{2k}\Bigl(\frac NM\Bigr)^{a-1}M^{a+b-k-1}\le(2k)^{2k}r_{2k}\Bigl(\frac NM\Bigr)^{a-1}\frac1M $$
以下で、$N/M$ は有界なので $0$ に近づく。
残るのは $a+b=k+1$ の同値類である。このとき $e=k$ で、$G$ は木で、各辺はちょうど 2 回通られ、期待値は $E[\xi^2]^k=1$ である。
Dyck 経路との対応。 そのような道の時刻 $t$ の高さを、出発点 $r_{i_1}$ からの $G$ の中での距離とする。辺を初めて通るとき、行き先はまだ訪れていない頂点である(訪れた頂点と通った辺は連結なので、訪れた頂点どうしを結ぶ新しい辺は閉路を作る)。出発点から現在地への $G$ の道の頂点はすでに訪れているので、行き先は距離が $1$ 大きい。辺を 2 回目に通るときは距離が $1$ 小さくなる。距離が大きくなる向きに 2 回目を通ると、その先から出発点へ戻るにはその辺を 3 回目に通るしかないからである。よって高さの列は長さ $2k$ の Dyck 経路 $P$ になる。2 部グラフなので、偶数の高さの頂点は行の頂点である。出発点以外の行の頂点は奇数の高さから上って初めて訪れるので、$a-1=u_{\mathrm{odd}}(P)$ である。
逆に Dyck 経路 $P$ が与えられると、上りでは新しい頂点(高さの偶奇で行か列か決まる)へ進み、下りでは来た辺を戻ることで、頂点に初めて訪れた順に名をつけた道がただ 1 つ決まる。同値類の代表は初めて訪れた順の名で決まるので、これは同値類と Dyck 経路の全単射である。
よって $a=1+u_{\mathrm{odd}}(P)$、$b=k+1-a$ として、この部分の寄与は
$$ \sum_P\frac{N(N-1)\cdots(N-a+1)\,M(M-1)\cdots(M-b+1)}{NM^k}\longrightarrow\sum_Py^{a-1}=\beta_k(y) $$
である(各項は $(N/M)^{a-1}(1+O(1/N))$ である)。$\square$

分散の評価

$k\ge1$ について、$N$ によらない定数 $c_k$($k$、$r_{4k}$、$\sup_N N/M$ による)があって、$\operatorname{Var}\langle L_N,x^k\rangle\le c_k/N$ である。

2 本の道

要点:共分散が $0$ でない 2 本の道は辺を共有し、合わせた $4k$ 歩で各辺が 2 回以上通られるので、頂点の数は $2k+1$ 以下である。

詳しい証明を開く

分散は $N^{-2}M^{-2k}\sum\operatorname{Cov}(x(w),x(w'))$ と書ける($w,w'$ は $2k$ 歩の閉じた道、$x(w)$ は因子の積)。2 本の道のグラフが辺を共有しなければ $x(w),x(w')$ は独立で共分散は $0$ である。ある辺が 2 本を合わせて 1 回だけ通られるなら、$E[x(w)x(w')]$ も $E[x(w)]E[x(w')]$ も $0$ である。

よって共分散が $0$ でない組では、合わせたグラフは連結で、辺の数は $2k$ 以下、行の頂点の数 $a\ge1$ と列の頂点の数 $b$ は $a+b\le2k+1$ をみたす。組の同値類は $(4k)^{4k}$ 個以下、各同値類の組は $N^aM^b$ 個以下、共分散の絶対値は $2r_{4k}$ 以下なので、分散は $2(4k)^{4k}r_{4k}\max N^{a-2}M^{b-2k}$ 以下である。$N^{a-2}M^{b-2k}\le(N/M)^{a-1}N^{-1}$ なので主張を得る。$\square$

2 次のモーメント

$k=2$ では $\operatorname{tr}S_N^2=M^{-2}\sum_{i,i',j,j'}x_{ij}x_{i'j}x_{i'j'}x_{ij'}$ である。期待値が $0$ でない項は、$i=i'$ かつ $j\ne j'$($NM(M-1)$ 項、期待値 $1$)、$i\ne i'$ かつ $j=j'$($N(N-1)M$ 項、期待値 $1$)、$i=i'$ かつ $j=j'$($NM$ 項、期待値 $\mu_4:=E[\xi^4]$)である。よって
$$ E\langle L_N,x^2\rangle=1+\frac{N-1}M+\frac{\mu_4-1}M\longrightarrow1+y=\beta_2(y) $$
である。はじめの 2 種はそれぞれ Dyck 経路 $(+,-,+,-)$、$(+,+,-,-)$ にあたり、$u_{\mathrm{odd}}$ はそれぞれ $0$、$1$ である。$\mu_4$ は極限に現れない。

極限の分布の特定

Dyck 経路の数 $\beta_k(y)$ が def-mp-law の $\mu_y$ のモーメントであることを、Stieltjes 変換で確かめる。

半円形の重みの積分

$0\le a< b$ とし、$w$ を $[a,b]$ の外の実数とする。$c_0:=\frac{a+b}2$ とおくと
$$ \int_a^b\frac{\sqrt{(b-x)(x-a)}}{w-x}\,dx=\begin{cases}\pi\bigl(w-c_0-\sqrt{(w-a)(w-b)}\bigr)&(w>b)\\ \pi\bigl(w-c_0+\sqrt{(a-w)(b-w)}\bigr)&(w< a)\end{cases} $$
である。

余弦で置換する

要点:$x=c_0+\rho\cos\theta$($\rho:=\frac{b-a}2$)と置換すると、$\int_0^\pi\frac{\sin^2\theta}{c-\cos\theta}d\theta=\pi(c-\sqrt{c^2-1})$($c>1$)に帰着する。

詳しい証明を開く

置換で $\sqrt{(b-x)(x-a)}=\rho\sin\theta$、$dx=-\rho\sin\theta\,d\theta$($0\le\theta\le\pi$)である。$c>1$ について、$t=\tan(\theta/2)$ と置換して $\int_0^\pi\frac{d\theta}{c-\cos\theta}=\int_0^\infty\frac{2\,dt}{(c-1)+(c+1)t^2}=\frac{\pi}{\sqrt{c^2-1}}$ である。$\sin^2\theta=(1-c^2)+(c-\cos\theta)(c+\cos\theta)$ なので $\int_0^\pi\frac{\sin^2\theta}{c-\cos\theta}d\theta=-\pi\sqrt{c^2-1}+\int_0^\pi(c+\cos\theta)\,d\theta=\pi(c-\sqrt{c^2-1})$ である。

$w>b$ なら $c:=(w-c_0)/\rho>1$ で、積分は $\rho\int_0^\pi\frac{\sin^2\theta}{c-\cos\theta}d\theta=\pi(w-c_0-\sqrt{(w-c_0)^2-\rho^2})$ である。$w< a$ なら $c:=(c_0-w)/\rho>1$ で、分母は $-\rho(c+\cos\theta)$ であり、$\theta\mapsto\pi-\theta$ で同じ積分に帰着して $-\pi(c_0-w-\sqrt{(c_0-w)^2-\rho^2})$ を得る。$(w-c_0)^2-\rho^2=(w-a)(w-b)$ である。$\square$

Marchenko–Pastur 分布のモーメント

$\mu_y$ は確率測度で、$k\ge1$ について $\int x^k\,\mu_y(dx)=\beta_k(y)$ である。

Stieltjes 変換の 2 次方程式

$a=(1-\sqrt y)^2$、$b=(1+\sqrt y)^2$ なので $c_0=1+y$、$\sqrt{ab}=\lvert1-y\rvert$ である。$w>b$ について $G(w):=\int\frac{\mu_y(dx)}{w-x}$ とおき、$R(w):=\sqrt{(w-a)(w-b)}>0$ とする。
$G$ の計算。 $\frac1{x(w-x)}=\frac1w\bigl(\frac1x+\frac1{w-x}\bigr)$ を使う。$J:=\int_a^b\frac{\sqrt{(b-x)(x-a)}}x\,dx$ は、$a>0$ なら lem-mp-integral の $w=0$ の場合の符号を変えたもので $\pi(c_0-\sqrt{ab})$ である。$a=0$($y=1$)なら $x=4\sin^2\varphi$ と置換して $J=\int_0^{\pi/2}8\cos^2\varphi\,d\varphi=2\pi$ で、同じ式が成り立つ。よって $f_y$ の部分の寄与は
$$ \frac1{2\pi yw}\Bigl(J+\pi(w-c_0-R(w))\Bigr)=\frac{w-\lvert1-y\rvert-R(w)}{2yw} $$
である。$y\le1$ ならこれが $G(w)$ である。$y>1$ なら原子の寄与 $\frac{1-1/y}w=\frac{2y-2}{2yw}$ を足す。どちらの場合も
$$ G(w)=\frac{w-1+y-R(w)}{2yw} $$
である。$R(w)=w-c_0-\frac{2y}w+O(w^{-2})$($w\to\infty$)から $wG(w)\to1$ で、$f_y$ の部分の質量($w\to\infty$ での $wG$ の極限への寄与)は $y\le1$ で $1$、$y>1$ で $1/y$ である。よって $\mu_y$ は確率測度である。
2 次方程式。 $R(w)^2=(w-1+y)^2-4yw$ なので、$G$ は $ywG^2-(w-1+y)G+1=0$ の根である。
モーメント。 $0< z< 1/b$ について $m(z):=\int\frac{\mu_y(dx)}{1-zx}$ とおく。$\mu_y$ は $[0,b]$ に集中し $0\le zx\le zb< 1$ なので、等比級数を項別に積分して $m(z)=\sum_{k\ge0}z^k\int x^k\,d\mu_y$ で、この冪級数は $\lvert z\rvert< 1/b$ で収束する。$w=1/z$ とおくと $m(z)=wG(w)$ なので、2 次方程式は
$$ m=1+zm+zym(m-1)\qquad(0< z< 1/b) $$
となる。両辺は $\lvert z\rvert< 1/b$ で収束する冪級数で、区間 $(0,1/b)$ の上で一致するので係数も一致する。よって $\int x^k\,d\mu_y$ は lem-mp-dyck と同じ漸化式と同じ初項 $1$ をもち、$\beta_k(y)$ に等しい。$\square$

主定理の証明

モーメントから弱収束へ、切り落とし

段 1:$\xi$ のすべてのモーメントが有限な場合。 多項式 $Q$ について、prop-mp-mean、prop-mp-var、prop-mp-moments と Chebyshevの不等式 から、$\langle L_N,Q\rangle\to\langle\mu_y,Q\rangle$(確率収束)である。
$f$ を有界連続、$\lvert f\rvert\le M_0$、$\delta>0$ とし、$B:=b+1$ とおく。Weierstrass の近似定理により $[0,B]$ で $\lvert f-Q\rvert\le\delta$ となる多項式 $Q$ をとり、$c>0$ と $r\ge1$ を $x>B$ で $M_0+\lvert Q(x)\rvert\le cx^r$ となるようにとる。$L_N$ と $\mu_y$ は $[0,\infty)$ に集中し、$\mu_y$ は $[0,b]$ に集中するので
$$ \lvert\langle L_N,f\rangle-\langle\mu_y,f\rangle\rvert\le2\delta+\lvert\langle L_N,Q\rangle-\langle\mu_y,Q\rangle\rvert+c\,B^{-j}\langle L_N,x^{r+j}\rangle $$
である($j\ge1$、$x^r\mathbf 1_{x>B}\le B^{-j}x^{r+j}$)。最後の項は $c\,B^{-j}\beta_{r+j}(y)\le c\,b^r(b/B)^j$ に確率収束する($\beta_{r+j}(y)=\int x^{r+j}d\mu_y\le b^{r+j}$)。$j$ を大きくとれば、確率 $1-o(1)$ で $\delta$ 以下である。
段 2:切り落とし。 一般の場合を示す。$[0,\infty)$ の上の確率測度の列の弱収束は、$x\mapsto\sqrt x$ による像の弱収束と同値で($x\mapsto x^2$ と $\sqrt x$ はどちらも連続)、像の弱収束は有界 Lipschitz 関数で確かめれば足りる(極限が確定した測度なので、確率収束についても同じ)。よって $f(x)=h(\sqrt x)$、$h$ は有界で Lipschitz 定数 $\ell$、の形の $f$ で示せばよい。
$C>0$ について $\xi_C:=\xi\mathbf 1_{\lvert\xi\rvert\le C}-E[\xi\mathbf 1_{\lvert\xi\rvert\le C}]$、$s_C^2:=E[\xi_C^2]$、$\hat\xi:=\xi_C/s_C$ とし、$X_N$ の各成分に同じ規則を当てた行列を $\hat X_N$、$\hat S_N:=\frac1M\hat X_N\hat X_N^{\mathsf T}$ とする。$\hat\xi$ は有界で平均 $0$、分散 $1$ なので、段 1 から $L_{\hat S_N}\to\mu_y$(確率収束)である。
$A:=X_N/\sqrt M$、$\hat A:=\hat X_N/\sqrt M$ の特異値を大きい順に $\sigma_1\ge\dots\ge\sigma_q$、$\hat\sigma_1\ge\dots\ge\hat\sigma_q$($q=\min(N,M)$)とする。$S_N$ の固有値は $\sigma_i^2$ と $N-q$ 個の $0$ である。$(N+M)$ 次の対称行列 $D(A):=\begin{pmatrix}0&A\\A^{\mathsf T}&0\end{pmatrix}$ の固有値は $\pm\sigma_i$ と $N+M-2q$ 個の $0$ である(特異値分解 から)。Hoffman–Wielandt の不等式(AGZ10 Lemma 2.1.19:$N$ 次実対称行列 $U,V$ の固有値を小さい順に並べて $\sum_i(\lambda_i(U)-\lambda_i(V))^2\le\operatorname{tr}(U-V)^2$。この記事では証明しない)を $D(A),D(\hat A)$ に当てると、$2\sum_i(\sigma_i-\hat\sigma_i)^2\le2\sum_{i,j}(A-\hat A)_{ij}^2$ を得る。よって Cauchy–Schwarz の不等式から
$$ E\lvert\langle L_N,f\rangle-\langle L_{\hat S_N},f\rangle\rvert\le\frac\ell N\,E\sum_{i\le q}\lvert\sigma_i-\hat\sigma_i\rvert\le\ell\Bigl(E\frac1N\sum_{i,j}(A-\hat A)_{ij}^2\Bigr)^{1/2}=\ell\,\bigl(E[(\xi-\hat\xi)^2]\bigr)^{1/2} $$
である。右辺は $N$ によらず、$C\to\infty$ で $0$ に近づく(優収束定理と $E[\xi]=0$ から $\xi_C\to\xi$($L^2$)、$s_C\to1$)。$C$ を大きくとってから $N\to\infty$ として結論を得る。$\square$

例

$y=1$ と半円分布

$y=1$ では $a=0$、$b=4$、$\mu_1(dx)=\frac1{2\pi}\sqrt{(4-x)/x}\,dx$ である。これは Wignerの半円則 の半円分布 $\sigma(dx)=\frac1{2\pi}\sqrt{4-x^2}\,dx$ の $x\mapsto x^2$ による像である。実際、$\int x^k\,d\mu_1=\beta_k(1)=C_k=\int x^{2k}\,d\sigma$ で、どちらもコンパクトな台をもつので、モーメントが一致すれば測度も一致する(Weierstrass の近似定理)。密度の変換 $2\cdot\frac1{2\pi}\sqrt{4-s}\cdot\frac1{2\sqrt s}$ でも確かめられる(AGZ10 Exercise 2.1.18 (vii))。

次元と観測数が同じ程度のとき

$N=400$、$M=800$($y=1/2$)とする。成分が独立な標準正規分布なら、真の共分散行列は単位行列で、すべての固有値が $1$ である。しかし $S_N$ の固有値の分布は、ほぼ区間 $[(1-\sqrt{1/2})^2,(1+\sqrt{1/2})^2]=[0.0857\ldots,2.914\ldots]$ に広がる。最大の固有値が $2.9$ 程度でも、それだけでは信号の証拠にならない。$\mu_{1/2}$ の平均は $\beta_1=1$、2 次のモーメントは $\beta_2=3/2$ で、分散は $y=1/2$ である。乱数(種 20261105、試行 1 回)で作った $S_N$ では $\frac1N\operatorname{tr}S_N=1.0027$、$\frac1N\operatorname{tr}S_N^2=1.5043$ だった。
$y\to0$ では $\mu_y$ は $1$ の近くの幅 $4\sqrt y$ の区間に集まり、$\delta_1$ に近づく。$N$ を固定して $M\to\infty$ とすると、大数の法則 により $S_N$ の各成分は単位行列の成分に概収束する。この極限と整合する。

反例:条件を外すと成り立たないこと

thm-mp-main の仮定を 1 つずつ外す。どの行でも残りの仮定(平均 $0$、分散 $1$ など)はみたされ、極限は $\mu_y$ にならない。

外す条件反例成り立たなくなること
成分の独立性すべての成分を同じ $\xi\sim N(0,1)$ とする($x_{ij}=\xi$)$S_N=\xi^2\mathbf 1\mathbf 1^{\mathsf T}$ は階数 1 で、$L_N\to\delta_0$
分布が $N$ によらないこと$x_{ij}=\varepsilon_{ij}\eta_{ij}\sqrt M$、$\eta_{ij}$ は確率 $1/M$ で $1$ の Bernoulli、$\varepsilon_{ij}=\pm1$ は等確率成分がすべて $0$ の行の割合が $e^{-1}$ に近づき、$y< 1$ でも $L_N$ が $0$ に質量 $e^{-1}$ 以上を残す
比 $N/M$ が収束すること$N/M$ が $1/2$ と $2$ を交互にとる$L_N$ は $\mu_{1/2}$ と $\mu_2$ の近くを行き来し、収束しない
反例の確かめ

確かめ:

3 行の確かめを開く

1 行目:$X_N=\xi\mathbf 1_N\mathbf 1_M^{\mathsf T}$ なので $S_N=\xi^2\mathbf 1_N\mathbf 1_N^{\mathsf T}$ で、固有値は $N\xi^2$ と $N-1$ 個の $0$ である。$L_N=\frac{N-1}N\delta_0+\frac1N\delta_{N\xi^2}$ は $\delta_0$ に弱収束する。各成分は平均 $0$、分散 $1$ である。

2 行目:各成分は平均 $0$、分散 $M\cdot\frac1M=1$ で、各 $N$ ごとに独立同分布である。成分がすべて $0$ の行では $S_N$ のその行と列が $0$ になり、そのような行が $Z$ 個あれば $S_N$ は固有値 $0$ を $Z$ 個以上もつ。各行が $0$ である確率は $(1-1/M)^M\to e^{-1}$ で、行は独立なので 大数の法則 から $Z/N\to e^{-1}$(確率収束)である。$\mu_y$($y< 1$)は $0$ に原子をもたず、$0$ の近く $[0,a)$ に質量をもたないので、有界連続な $f$ で $f(0)=1$、$[a/2,\infty)$ で $0$、値が $[0,1]$ のものをとると $\langle L_N,f\rangle\ge Z/N$ だが $\langle\mu_y,f\rangle=0$ である。この例では $\xi$ の分布が $N$ とともに変わり、4 次のモーメント $M$ が発散する。乱数(種 20261105、$N=2000$、$M=4000$)では $0$ の行の割合は $0.374$ だった。

3 行目:$N/M=1/2$ となる部分列では $L_N\to\mu_{1/2}$、$2$ となる部分列では $L_N\to\mu_2$ で、$\mu_2$ は $0$ に原子 $1/2$ をもつが $\mu_{1/2}$ はもたない。

平均 $0$ の仮定は、極限については外しても結論が変わらない。分散を $1$ のまま $E[\xi]=m\ne0$ とすると、$X_N=m\mathbf 1\mathbf 1^{\mathsf T}+X_N'$($X_N'$ の成分は平均 $0$、分散 $1$)で、$X_NX_N^{\mathsf T}-X_N'X_N'^{\mathsf T}$ の階数は $2$ 以下である。階数 $2$ 以下の摂動では、固有値の交互性(Weyl の不等式)から、各半直線 $(-\infty,t]$ に入る固有値の数の差が $2$ 以下なので、経験固有値分布の分布関数の差は $2/N$ 以下で、極限は変わらない。ただし $S_N$ の最大固有値は $Nm^2$ の程度に飛び出す。

応用

  • 高次元の統計。次元 $N$ と標本の数 $M$ が同じ程度の 主成分分析 では、雑音だけでも標本共分散行列の固有値は $[(1-\sqrt y)^2,(1+\sqrt y)^2]$ に広がる。この区間からはみ出す固有値が、信号の候補になる。
  • 自由確率論。$\mu_y$ は自由 Poisson 分布とも呼ばれ、自由確率論 で Poisson の小数の法則の自由版の極限として現れる(AGZ10 Exercise 5.3.27, p. 368)。半円分布が自由中心極限定理の極限であることの類似である。
  • Stieltjes 変換の方法。prop-mp-moments の 2 次方程式は、行列のレゾルベントの跡の満たす方程式としても導かれる(AGZ10 Exercise 2.4.8, p. 50)。この方法はモーメントを使わない。

歴史と出典

出典

定理は V. A. Marchenko と L. A. Pastur による(MaP67)。モーメント法による証明の筋は AGZ10 Exercise 2.1.18(pp. 20–21)の (i)〜(vi) にあり、2 部グラフの上の道と Dyck 経路を使う。この記事の数え上げは、同じ筋を最初に高さ $0$ へ戻る時刻での分解に直したものである。ランダム行列の他のアンサンブルとの関係は ランダム行列 にある。

関連項目

参考文献

[1]
V. A. Marčenko, L. A. Pastur, Distribution of eigenvalues in certain sets of random matrices, Mathematics of the USSR-Sbornik, 1967
[2]
Greg W. Anderson, Alice Guionnet, Ofer Zeitouni, An Introduction to Random Matrices, Cambridge Studies in Advanced Mathematics 118, Cambridge University Press, 2010, Exercise 2.1.18(pp. 20–21)、Lemma 2.1.19(p. 21)、Exercise 2.4.8(p. 50)、Exercise 5.3.27(p. 368)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する