行列積は畳み込みできないか
行列積計算を高速化するために畳み込みを使えないか?
今のところそういう事例はない (あれば行列積の計算量は$ O(n^2\log n))と言われているはず
$ [c]_{i,k}=\sum_j^N[a]_{i,j}[b]_{j,k} という式はいかにも畳み込みという感じがする
行列積をテンソル積の和に分解してみる
$ C=\sum_j^N\bm{a}_j\bm{b}^{\top}_j=\sum_j^N\bm{a}_j\otimes\bm{b}_j=
行列積を内積の行列にしてみる
$ [c]_{i,k}=[\bm a_i^\top\bm b_k]_{i,k}=[\bm a_i\cdot\bm b_k]_{i,k}
畳み込みとフーリエ変換との関係式の証明を書いてみる
$ (x*y)[t]=\mathcal F^{-1}[\mathcal F[x]\odot\mathcal F[y]]
$ \frac1T\sum_{f=1}^T\left(\sum_{t=1}^Tx[t]\omega_T^{-ft}\right)\left(\sum_{t=1}^Ty[t]\omega_T^{-ft}\right)\omega_T^{ft}
$ =\frac1T\sum_{f=1}^T\left(\sum_{t_1=1}^T\sum_{t_2=1}^Tx[t_1]y[t_2]\omega_T^{-f(t_1+t_2)}\right)\omega_T^{ft}
$ =\frac1T\sum_{f=1}^T\left(\sum_{t_1=1}^Tx[t_1]y[t-t_1]\omega_T^{-ft}\right)\omega_T^{ft}
$ =\frac1T\sum_{f=1}^T\sum_{t_1=1}^Tx[t_1]y[t-t_1]
$ =\sum_{t_1=1}^Tx[t_1]y[t-t_1]
$ =(x*y)[t]
これをベクトルっぽく書く
$ \frac1T\sum_{f=1}^T\left(\sum_{t=1}^T\bm x[t]\omega_T^{-ft}\right)\otimes\left(\sum_{t=1}^T\bm y[t]\omega_T^{-ft}\right)\omega_T^{ft}
$ =\frac1T\sum_{f=1}^T\left(\sum_{t_1=1}^T\sum_{t_2=1}^T\bm x[t_1]\otimes\bm y[t_2]\omega_T^{-f(t_1+t_2)}\right)\omega_T^{ft}
$ =\frac1T\sum_{f=1}^T\left(\sum_{t_1=1}^T\bm x[t_1]\otimes \bm y[t-t_1]\omega_T^{-ft}\right)\omega_T^{ft}
$ =\frac1T\sum_{f=1}^T\sum_{t_1=1}^T\bm x[t_1]\otimes\bm y[t-t_1]
$ =\sum_{t_1=1}^T\bm x[t_1]\otimes\bm y[t-t_1]
これは計算量が減ってない
$ \left(\sum_{t=1}^T\bm x[t]\omega_T^{-ft}\right)\otimes\left(\sum_{t=1}^T\bm y[t]\omega_T^{-ft}\right) が行列の形になるため、
$ \frac1T\sum_{f=1}^T\left(\sum_{t=1}^T\bm x[t]\omega_T^{-ft}\right)\otimes\left(\sum_{t=1}^T\bm y[t]\omega_T^{-ft}\right)\omega_T^{ft} の計算量は$ \omicron(n^3\log n)
以前にこれについて考えた時になんか$ \{A_n\}を得た後に$ A_0を求めるみたいな効率の悪い話になった気がする
内積の形にしたものは内積の計算が$ \Omicron(n)なので$ O(n^3)