w乘h乘n张量,应用HOSVD求核心张量和因子矩阵的时间复杂度
时间: 2023-06-25 22:04:40 浏览: 52
假设 $w\times h\times n$ 张量为 $\mathcal{X}$,其 HOSVD 分解后得到的核心张量为 $\mathcal{G}$,因子矩阵为 $\mathbf{U}^{(w)},\mathbf{U}^{(h)},\mathbf{U}^{(n)}$,其中 $\mathbf{U}^{(w)}\in\mathbb{R}^{w\times r_w},\mathbf{U}^{(h)}\in\mathbb{R}^{h\times r_h},\mathbf{U}^{(n)}\in\mathbb{R}^{n\times r_n}$,$r_w,r_h,r_n$ 分别为对应模式的秩。
核心张量 $\mathcal{G}$ 的大小为 $r_w\times r_h\times r_n$,因此计算核心张量的时间复杂度为 $O(r_wr_hr_n)$。
对于每个模式的因子矩阵,都需要进行奇异值分解,其时间复杂度为 $O(\min(m^2n,\,mn^2))$,其中 $m$ 和 $n$ 分别为对应模式的维度。因此,对于三个模式共需进行三次奇异值分解,总时间复杂度为 $O(r_w^2w+r_h^2h+r_n^2n)$。
因此,对于 HOSVD 分解,总的时间复杂度为 $O(r_w^2w+r_h^2h+r_n^2n+r_wr_hn)$.
相关问题
HOSVD算法求核心张量和因子矩阵的时间复杂度
HOSVD算法求解核心张量和因子矩阵的时间复杂度取决于矩阵/张量的维度和秩。具体地:
1. 核心张量的计算:时间复杂度为 $O(N^3r)$,其中 $N$ 是矩阵/张量的维度,$r$ 是矩阵/张量的秩。
2. 因子矩阵的计算:时间复杂度为 $O(N^2r^3)$。
综合而言,HOSVD算法的时间复杂度主要由核心张量的计算决定,因此总的时间复杂度为 $O(N^3r)$。需要注意的是,当矩阵/张量的秩较小时,HOSVD算法的时间复杂度会比较低,但当秩较大时,计算时间会明显增加。
w乘h乘n的张量X按模态1乘矩阵A1按模态2乘矩阵A2按模态3乘矩阵A3的时间复杂度
假设张量 $X$ 的大小是 $w\times h\times n$,矩阵 $A_1$ 的大小是 $a_1\times w$,矩阵 $A_2$ 的大小是 $a_2\times h$,矩阵 $A_3$ 的大小是 $a_3\times n$。
按模态乘法的定义,我们需要分别计算以下三个乘积:
1. $Y_1 = X\times_1 A_1$,大小为 $a_1\times h\times n$;
2. $Y_2 = Y_1\times_2 A_2$,大小为 $a_1\times a_2\times n$;
3. $Y_3 = Y_2\times_3 A_3$,大小为 $a_1\times a_2\times a_3$。
假设矩阵乘法的时间复杂度为 $O(mnp)$,其中 $m$ 是左矩阵的行数,$n$ 是右矩阵的列数,$p$ 是左矩阵的列数或右矩阵的行数。则按模态乘法的时间复杂度为:
1. $O(whna_1^2)$;
2. $O(whna_1a_2^2)$;
3. $O(whna_1a_2a_3^2)$。
因此,总的时间复杂度为 $O(whna_1^2 + whna_1a_2^2 + whna_1a_2a_3^2)$。