id:Cryolite:20080611
いや、それ無理なんじゃないの?的な感想。
 \sum^W_{h=1}\sum^W_{i=1}\left(\sum^K_{j}x_j \delta_{hij}\right)^n,\delta_{hij}=0or1*1って、

  • n乗のせいでΣの交換ができない(hとiを回しているΣは交換できるけど無意味)
  • x_{j}\delta_{hij}がhij全部に依存する

訳で、例えば式変形して計算数減らそうというアプローチは無駄ではないかと。x_j\delta_{hij}になんら法則性がない限りただの三重ループにしかならなそうな。つまり\left(\sum_j^K x_j\delta(hij)\right)^nが簡約できない。
じゃあ\delta_{hij}がほとんど0だっていう条件は使えるかっていうとこれも微妙。
x_1\delta_{hi1}+x_2\delta_{hi2}+\cdots+x_K\delta_{hiK}\delta_{hij}がソートしてあればO(KW^2)のKを相当小さくするこごができるけど、id:Cryolite氏の状況だとまあそんな都合のいいことはなさそうで、ソート自体にもO(K)のコストがかかるから意味がない。
なので、ここはO(KW^2)のコストを受け入れるより仕方がないのではないかなぁと。

ところで、n乗の中身を簡単にできないかと色々いじってたのですが

x_1\delta_{hi1}+x_2\delta_{hi2}+\cdots+x_K\delta_{hiK}って内積っぽくね?ってことで内積にしてみた。
\left( \begin{array}{ccc} x_1 & x_2 & \cdots & x_K \\ \end{array} \right) \left( \begin{array}{ccc} \delta_{hi1} \\ \delta_{hi2} \\ \vdots \\ \delta_{hiK} \\ \end{array} \right)
で、\delta_{hij} = \delta_{hj}\delta'_{ij}と書けるとか書いてあるんで、縦ベクトルの方を
\left( \begin{array}{ccc}\delta_{h1} & & & 0 \\            & \delta_{h2} & &\\                     & & \ddots \\ 0           & & &          \delta_{hK} \\ \end{array} \right)\left( \begin{array}{ccc} \delta'_{i1} \\ \delta'_{i2} \\ \vdots \\ \delta'_{iK} \end{array} \right)
と分解してみた。以下xの横ベクトル、行列、δの縦ベクトルは{\bf x}^T,Y,{\bf\delta'}で表すことにする。
するとn乗の部分は
\left( {\bf x}^T Y{\bf\delta'} \right)^n
 = {\bf x}^T \left( Y ({\bf\delta'}{\bf x}^T) \right)^{n-1} Y{\bf\delta'}
 = {\bf x}^T \left( \begin{array}{ccc} \delta_{h1}\delta'_{i1}x_1^{n-1} & & & 0 \\ & \delta_{h2}\delta'_{i2}x_2^{n-1} & & \\ & & \ddots & \\ 0 & & & \delta_{hK}\delta'_{iK}x_K^{n-1} \\ \end{array}\right) Y{\bf\delta'}
 = \left( \delta_{h1}\delta'_{i1}x_1^{n} + \delta_{h2}\delta'_{i2}x_2^{n}+ \cdots + \delta_{hK}\delta'_{iK}x_K^{n}  \right)
と、明らかにトンデモな結果が出る。どこかで地雷を踏んでいるのは間違いない。この式に従うと例えば(1+1+1+1)^4 = 4になる。しかし困ったことに手元の教科書isbn:4274065782isbn:4130620010行列計算は合法なはずなのである。Yが対角行列だからおかしくなるのかと思いきやそんなことはなく、どうも{\bf\delta'}{\bf x}^Tとやって行列を作った瞬間に怪しくなるようなのだが・・・識者の意見を請いたいところ。

7/23追記

コメント頂いたisbn:4274065782.34ですが、そこの本文中に書いてあるルール通り計算すると上のようになっちゃうんで。もう少し詳しく書くと
{\bf\delta'}{\bf x}^T
= \left( \begin{array}{ccc} \delta'_i1 \\ \vdots \\ \delta'_iK \\ \end{array} \right) \left( \begin{array}{ccc} x_1 & \cdots & & x_k \\ \end{array} \right)
=\left( \begin{array}{ccc} x_1\delta'_i1 && x_1\delta'_i2 && \cdots && x_1\delta'_iK \\ x_2\delta'_i1 && x_2\delta'_i2 && && \vdots \\ \vdots && && \ddots && \\ x_K\delta'_i1 && && && x_K\delta'_iK \end{array} \right)
なので、
Y({\bf\delta'}{\bf x}^T) = \left( \begin{array}{ccc} \delta_{h1}\delta'_{i1}x_1 & & & 0 \\ & \delta_{h2}\delta'_{i2}x_2 & & \\ & & \ddots & \\ 0 & & & \delta_{hK}\delta'_{iK}x_K \\ \end{array}\right)
ってなっちゃうんですよ。要はタテ×ヨコだから行列、です。

7/26追記

コメントで指摘受けました。
Y({\bf\delta'}{\bf x}^T) = \left( \begin{array}{ccc} x_1\delta'_{i1}\delta_{h1} && x_2\delta'_{i1}\delta_{h1} && \cdots && x_K\delta'_{i1}\delta_{h1} \\ x_1\delta'_{i2}\delta{h2} && x_2\delta'_{i2}\delta_{h2} && && \vdots \\ \vdots && && \ddots && \\ x_1\delta'_{iK}\delta{hK} && && && x_K\delta'_{iK}\delta_{hK} \end{array} \right)
ですよね・・・。なんで対角行列×任意の行列=対角行列だと思ったんだろう。以上、地雷というか自爆オチでした。

*1:元の記事と多少記号の使い方が違いますが、内容は全く同じはずです