\[
% general purpose
\newcommand{\ctext}[1]{\raise0.2ex\hbox{\textcircled{\scriptsize{#1}}}}
% mathematics
% general purpose
\DeclarePairedDelimiterX{\parens}[1]{\lparen}{\rparen}{#1}
\DeclarePairedDelimiterX{\braces}[1]{\lbrace}{\rbrace}{#1}
\DeclarePairedDelimiterX{\bracks}[1]{\lbrack}{\rbrack}{#1}
\DeclarePairedDelimiterX{\verts}[1]{|}{|}{#1}
\DeclarePairedDelimiterX{\Verts}[1]{\|}{\|}{#1}
\newcommand{\as}{{\quad\textrm{as}\quad}}
\newcommand{\st}{{\textrm{ s.t. }}}
\DeclarePairedDelimiterX{\setComprehension}[2]{\lbrace}{\rbrace}{#1\,\delimsize\vert\,#2}
\newcommand{\naturalNumbers}{\mathbb{N}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\rationalNumbers}{\mathbb{Q}}
\newcommand{\realNumbers}{\mathbb{R}}
\newcommand{\complexNumbers}{\mathbb{C}}
\newcommand{\field}{\mathbb{F}}
\newcommand{\func}[2]{{#1}\parens*{#2}}
\newcommand*{\argmax}{\operatorname*{arg~max}}
\newcommand*{\argmin}{\operatorname*{arg~min}}
% set theory
\newcommand{\range}[2]{\braces*{#1,\dotsc,#2}}
\providecommand{\complement}{}\renewcommand{\complement}{\mathrm{c}}
\newcommand{\ind}[2]{\mathbbm{1}_{#1}\parens*{#2}}
\newcommand{\indII}[1]{\mathbbm{1}\braces*{#1}}
% number theory
\newcommand{\abs}[1]{\verts*{#1}}
\newcommand{\combi}[2]{{_{#1}\mathrm{C}_{#2}}}
\newcommand{\perm}[2]{{_{#1}\mathrm{P}_{#2}}}
\newcommand{\GaloisField}[1]{\mathrm{GF}\parens*{#1}}
% analysis
\newcommand{\NapierE}{\mathrm{e}}
\newcommand{\sgn}[1]{\operatorname{sgn}\parens*{#1}}
\newcommand*{\rect}{\operatorname{rect}}
\newcommand{\cl}[1]{\operatorname{cl}#1}
\newcommand{\Img}[1]{\operatorname{Img}\parens*{#1}}
\newcommand{\dom}[1]{\operatorname{dom}\parens*{#1}}
\newcommand{\norm}[1]{\Verts*{#1}}
\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil#1\right\rceil}
\newcommand{\expo}[1]{\exp\parens*{#1}}
\newcommand*{\sinc}{\operatorname{sinc}}
\newcommand*{\nsinc}{\operatorname{nsinc}}
\newcommand{\GammaFunc}[1]{\Gamma\parens*{#1}}
\newcommand*{\erf}{\operatorname{erf}}
% inverse trigonometric functions
\newcommand{\asin}[1]{\operatorname{Sin}^{-1}{#1}}
\newcommand{\acos}[1]{\operatorname{Cos}^{-1}{#1}}
\newcommand{\atan}[1]{\operatorname{{Tan}^{-1}}{#1}}
\newcommand{\atanEx}[2]{\atan{\parens*{#1,#2}}}
% convolution
\newcommand{\cycConv}[2]{{#1}\underset{\text{cyc}}{*}{#2}}
% derivative
\newcommand{\deriv}[3]{\frac{\operatorname{d}^{#3}#1}{\operatorname{d}{#2}^{#3}}}
\newcommand{\derivLong}[3]{\frac{\operatorname{d}^{#3}}{\operatorname{d}{#2}^{#3}}#1}
\newcommand{\partDeriv}[3]{\frac{\operatorname{\partial}^{#3}#1}{\operatorname{\partial}{#2}^{#3}}}
\newcommand{\partDerivLong}[3]{\frac{\operatorname{\partial}^{#3}}{\operatorname{\partial}{#2}^{#3}}#1}
\newcommand{\partDerivIIHetero}[3]{\frac{\operatorname{\partial}^2#1}{\partial#2\operatorname{\partial}#3}}
\newcommand{\partDerivIIHeteroLong}[3]{{\frac{\operatorname{\partial}^2}{\partial#2\operatorname{\partial}#3}#1}}
% integral
\newcommand{\integrate}[5]{\int_{#1}^{#2}{#3}{\mathrm{d}^{#4}}#5}
\newcommand{\LebInteg}[4]{\int_{#1} {#2} {#3}\parens*{\mathrm{d}#4}}
% complex analysis
\newcommand{\conj}[1]{\overline{#1}}
\providecommand{\Re}{}\renewcommand{\Re}[1]{{\operatorname{Re}{\parens*{#1}}}}
\providecommand{\Im}{}\renewcommand{\Im}[1]{{\operatorname{Im}{\parens*{#1}}}}
\newcommand*{\Arg}{\operatorname{Arg}}
\newcommand*{\Log}{\operatorname{Log}}
% Laplace transform
\newcommand{\LPLC}[1]{\operatorname{\mathcal{L}}\parens*{#1}}
\newcommand{\ILPLC}[1]{\operatorname{\mathcal{L}}^{-1}\parens*{#1}}
% Discrete Fourier Transform
\newcommand{\DFT}[1]{\mathrm{DFT}\parens*{#1}}
% Z transform
\newcommand{\ZTrans}[1]{\operatorname{\mathcal{Z}}\parens*{#1}}
\newcommand{\IZTrans}[1]{\operatorname{\mathcal{Z}}^{-1}\parens*{#1}}
% linear algebra
\newcommand{\bm}[1]{{\boldsymbol{#1}}}
\newcommand{\matEntry}[3]{#1\bracks*{#2}\bracks*{#3}}
\newcommand{\matPart}[5]{\matEntry{#1}{#2:#3}{#4:#5}}
\newcommand{\diag}[1]{\operatorname{diag}\parens*{#1}}
\newcommand{\tr}[1]{\operatorname{tr}{\parens*{#1}}}
\newcommand{\inprod}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\HadamardProd}{\odot}
\newcommand{\HadamardDiv}{\oslash}
\newcommand{\Span}[1]{\operatorname{span}\bracks*{#1}}
\newcommand{\Ker}[1]{\operatorname{Ker}\parens*{#1}}
\newcommand{\rank}[1]{\operatorname{rank}\parens*{#1}}
% vector
% unit vector
\newcommand{\vix}{\bm{i}_x}
\newcommand{\viy}{\bm{i}_y}
\newcommand{\viz}{\bm{i}_z}
% probability theory
\newcommand{\PDF}[2]{\operatorname{PDF}\bracks*{#1,\;#2}}
\newcommand{\Ber}[1]{\operatorname{Ber}\parens*{#1}}
\newcommand{\Beta}[2]{\operatorname{Beta}\parens*{#1,#2}}
\newcommand{\ExpDist}[1]{\operatorname{ExpDist}\parens*{#1}}
\newcommand{\ErlangDist}[2]{\operatorname{ErlangDist}\parens*{#1,#2}}
\newcommand{\PoissonDist}[1]{\operatorname{PoissonDist}\parens*{#1}}
\newcommand{\GammaDist}[2]{\operatorname{Gamma}\parens*{#1,#2}}
\newcommand{\cind}[2]{\ind{#1\left| #2\right.}} % conditional indicator function
\providecommand{\Pr}{}\renewcommand{\Pr}[1]{\operatorname{Pr}\parens*{#1}}
\DeclarePairedDelimiterX{\cPrParens}[2]{(}{)}{#1\,\delimsize\vert\,#2}
\newcommand{\cPr}[2]{\operatorname{Pr}\cPrParens{#1}{#2}}
\newcommand{\E}[2]{\operatorname{E}_{#1}\bracks*{#2}}
\newcommand{\cE}[3]{\E{#1}{\left.#2\right|#3}}
\newcommand{\Var}[2]{\operatorname{Var}_{#1}\bracks*{#2}}
\newcommand{\Cov}[2]{\operatorname{Cov}\bracks*{#1,#2}}
\newcommand{\CovMat}[1]{\operatorname{Cov}\bracks*{#1}}
% graph theory
\newcommand{\neighborhood}{\mathcal{N}}
% programming
\newcommand{\plpl}{\mathrel{++}}
\newcommand{\pleq}{\mathrel{+}=}
\newcommand{\asteq}{\mathrel{*}=}
\]
はじめに
$n\times n$行列$A$のCholesky分解の計算量は$O(n^3)$であるが、$A$の分解が既に得られているとき、$A+\bm{x}\bm{x}^*$の分解を$O(n^2)$の計算量で求めることができる。本記事ではこの方法を導出する。
主張
$n\in\naturalNumbers,\;A\in\complexNumbers^{n\times n},\;A\succeq O,\;\bm{x}\in\complexNumbers^n$とし、$A$はHermite行列であるとする。 $A+\bm{x}\bm{x}^*$に対してCholesky分解のアルゴリズムを適用すると$O(n^3)$の計算量を要する。 しかし、$A$のCholesky分解$LL^*$が既に得られているとき、$A+\bm{x}\bm{x}^*$のCholesky分解を$O(n^2)$で得ることができる。 $\bm{x}\bm{x}^*$の階数が1以下である(特に0となるのは$\bm{x}=\bm{0}$の時かつその時に限る)ことから、この方法は “rank-one update” と呼ばれている。導出
方針としては、$n\times n$行列の rank-one update を$(n-1)\times(n-1)$行列の問題に帰着させ、以降同様に逐次的に行列の次数を縮小しながら解を構築する。このアルゴリズムの総計算量が$O(n^2)$となるのは明らかであろう。
$A+\bm{x}\bm{x}^*$のCholesky分解を$FF^*$とする。$L$の第$i$列ベクトルを$\bm{l}_i = [0,\dots,0,l_{i,i},\dots,l_{n,i}]^\top\in\complexNumbers^{n\times n}$とし、同様に$F$の第$i$列ベクトルを$\bm{f}_i = [0,\dots,0,f_{i,i},\dots,f_{n,i}]^\top\in\complexNumbers^{n\times n}$とすると次式が成り立つ。
\begin{align*} \sum_{i=1}^n \bm{f}_i\bm{f}_i^* &= \bm{x}\bm{x}^* + \sum_{i=1}^n \bm{l}_i\bm{l}_i^* \\ \bm{f}_1\bm{f}_1^* + \sum_{i=2}^n \bm{f}_i\bm{f}_i^* &= \bm{x}\bm{x}^* + \bm{l}_1\bm{l}_1^* + \sum_{i=2}^n \bm{l}_i\bm{l}_i^* \tag{1} \end{align*}$\bm{f}_i\bm{f}_i^*,\;\bm{l}_i\bm{l}_i^*\;(i=2,3,\dots,n)$の第1行および第1列は0であるから、$\bm{f}_1\bm{f}_1^*$と$\bm{x}\bm{x}^* + \bm{l}_1\bm{l}_1^*$の第1行および第1列が一致する。これより次式が成り立つ。
\[ f_{1,1} = \sqrt{l_{1,1}^2 + |x_1|^2} \eqqcolon r,\; f_{k,1} = \frac{1}{r}\left(l_{1,1}l_{k,1} + \overline{x_1}x_k\right) \; (k=2,3,\dots,n) \tag{2} \]ただし$L$の対角成分が非負の実数であることを前提としている。以上より、$\tilde{\bm{l}_1} \coloneqq [0,l_{2,1},l_{3,1},\dots,l_{n,1}]^\top,\;\tilde{\bm{x}} \coloneqq [0,x_2,x_3,\dots,x_n]^\top$とすると次式が成り立つ。
\[ \bm{f}_1 = r\bm{e}_1 + \frac{l_{1,1}}{r}\tilde{\bm{l}_1} + \frac{\conj{x_1}}{r}\tilde{\bm{x}} \]ここに$\bm{e}_1$は第1要素が1で他は0であるベクトルである。$\bm{f}_1\bm{f}_1^*$の右下$(n-1)\times(n-1)$行列を評価すると次式を得る。
\begin{align*} &\phantom{=} \frac{1}{r^2} \left(l_{1,1}^2\tilde{\bm{l}_1}\tilde{\bm{l}_1}^* + l_{1,1}x_1\tilde{\bm{l}_1}\tilde{\bm{x}}^* + \abs{x_1}^2\tilde{\bm{x}}\tilde{\bm{x}}^* + l_{1,1}\overline{x_1}\tilde{\bm{x}}\tilde{\bm{l}_1}^*\right) \\ &= \left(1 – \frac{\abs{x_1}^2}{r^2}\right)\tilde{\bm{l}_1}\tilde{\bm{l}_1}^* + \frac{l_{1,1}x_1}{r^2}\tilde{\bm{l}_1}\tilde{\bm{x}}^* + \left(1 – \frac{l_{1,1}^2}{r^2}\right)\tilde{\bm{x}}\tilde{\bm{x}}^* + \frac{\overline{x_1}l_{1,1}}{r^2}\tilde{\bm{x}}\tilde{\bm{l}_1}^* \\ &= \tilde{\bm{l}_1}\tilde{\bm{l}_1}^* + \tilde{\bm{x}}\tilde{\bm{x}}^* – \frac{1}{r^2}\left(\abs{x_1}^2\tilde{\bm{l}_1}\tilde{\bm{l}_1}^* + l_{1,1}^2\tilde{\bm{x}}\tilde{\bm{x}}^* – x_1l_{1,1}\tilde{\bm{l}_1}\tilde{\bm{x}}^* – \overline{x_1}l_{1,1}\tilde{\bm{x}}\tilde{\bm{l}_1}^*\right) \\ &= \tilde{\bm{l}_1}\tilde{\bm{l}_1}^* + \tilde{\bm{x}}\tilde{\bm{x}}^* – \bm{y}\bm{y}^* \quad \text{where} \quad \bm{y} = \frac{1}{r}\left(l_{1,1}\tilde{\bm{x}} – x_1\tilde{\bm{l}_1}\right) \end{align*}上式の$\tilde{\bm{l}_1}\tilde{\bm{l}_1}^* + \tilde{\bm{x}}\tilde{\bm{x}}^*$は$\bm{x}\bm{x}^* + \bm{l}_1\bm{l}_1^*$の右下$(n-1)\times(n-1)$行列である。以上より次式が成り立つ。
\[ \bm{f}_1\bm{f}_1^* = \bm{x}\bm{x}^* + \bm{l}_1\bm{l}_1^* – \bm{y}\bm{y}^* \]これを式(1)に適用して次式を得る。
\[ \sum_{i=2}^n \bm{f}_i\bm{f}_i^* = \bm{y}\bm{y}^* + \sum_{i=2}^n \bm{l}_i\bm{l}_i^* \]これは$(n-1)\times(n-1)$行列の rank-one update である。このようにして行列の次数を逐次的に縮小し、最後はスカラーの計算に帰着する。次数$k$の問題に対し式(2)の計算量は$O(k)$であるから、このアルゴリズムの総計算量は$n(n+1)/2$に比例する。
$\square$
実装例
以下はJulia 1.8.0での実装例である。
