Tensor-Train Decomposition 논문 리뷰(작성중)
| Venue | Link |
|---|---|
| SIAM Journal on Scientific Computing, 2011 | SIAM |
논문이 해결하려는 문제
Oseledets [1]의 Tensor-Train Decomposition은 고차원 텐서를 효율적으로 표현하고 계산하기 위한 format을 제안하는 논문이다. 여기서 tensor는 단순히 여러 개의 index를 가지는 multidimensional array로 생각하면 된다. 예를 들어 d-dimensional tensor는 다음과 같이 쓸 수 있다.
A(i_1, i_2, \ldots, i_d)
문제는 차원 d가 커질수록 전체 tensor를 그대로 저장하는 비용이 지수적으로 증가한다는 점이다. Tensor 문헌에서는 각 index 방향을 mode라고 부른다. 예를 들어 행렬 A(i,j)는 row 방향과 column 방향이라는 두 개의 mode를 가지고, 일반적인 tensor A(i_1,\ldots,i_d)는 d개의 mode를 가진다. 각 mode, 즉 각 index 방향의 크기가 모두 n이면 전체 원소 수는 다음과 같다.
n^d
d가 10, 100처럼 커지면 full tensor를 저장하거나 직접 계산하는 것은 사실상 불가능하다. 이것이 논문이 말하는 차원의 저주(curse of dimensionality)이다. 따라서 핵심 질문은 다음과 같다.
고차원 tensor를 적은 수의 parameter로 표현하면서도, 기본적인 선형대수 연산을 안정적으로 수행할 수 있는가?
논문은 선행 연구이자 기존 format으로 canonical decomposition과 Tucker decomposition을 먼저 언급한다. Canonical decomposition은 tensor를 rank-one tensor들의 합으로 표현한다.
A(i_1,\ldots,i_d) = \sum_{\alpha=1}^{r} U_1(i_1,\alpha)U_2(i_2,\alpha)\cdots U_d(i_d,\alpha)
이 format은 parameter 수가 적다는 장점이 있다. 하지만 논문은 canonical rank를 계산하는 문제가 어렵고, fixed canonical rank approximation이 ill-posed할 수 있다는 점을 문제로 지적한다. Tucker format은 canonical decomposition보다 안정적이지만, core tensor의 크기가 차원 수에 대해 커질 수 있다. 모든 Tucker rank가 r이면 core tensor가 대략 r^d개의 parameter를 가지므로, d가 큰 경우에는 여전히 부담스럽다. 이런 배경에서 논문은 Tensor Train format을 제안한다. Tensor Train은 canonical format보다 안정적인 SVD 기반 계산을 사용하고, Tucker format보다 고차원에서 더 compact하게 동작하는 것을 목표로 한다.
| Format | Representation idea | Parameter behavior | Strength | Weakness |
|---|---|---|---|---|
| canonical/CP | rank-one tensor들의 합 | rank가 작으면 대략 O(dnr) | 매우 compact할 수 있음 | canonical rank 계산이 어렵고 fixed-rank approximation이 ill-posed일 수 있음 |
| Tucker | 작은 core tensor와 mode별 factor matrix | 모든 Tucker rank가 r이면 core가 r^d로 성장 | SVD 기반 multilinear approximation으로 비교적 안정적 | d가 커지면 core growth 때문에 저장과 계산이 부담됨 |
| TT | 3D core들을 chain으로 연결하는 TT-format | TT-rank가 작게 유지되면 대략 O(dnr^2) | SVD 기반이고 high-dimensional tensor에 순차적으로 적용 가능 | TT-rank가 커지면 compact하지 않으며 연산 후 rounding이 필요함 |
Tensor Train format의 정의
Tensor Train format은 d-dimensional tensor를 작은 3-dimensional core tensor들의 곱으로 표현한다. 논문에서 TT-format은 다음과 같이 정의된다.
A(i_1,i_2,\ldots,i_d) = G_1(i_1)G_2(i_2)\cdots G_d(i_d)
여기서 G_k(i_k)는 scalar가 아니라 matrix이다. 각 index i_k를 고정하면 G_k(i_k)가 하나의 matrix가 된다. 각 core의 크기는 다음과 같다.
G_k \in \mathbb{R}^{r_{k-1} \times n_k \times r_k}
그리고 양끝 rank는 다음처럼 둔다.
r_0 = r_d = 1
따라서 각 G_k(i_k)의 matrix 크기는 다음과 같다.
G_1(i_1): 1 \times r_1
G_k(i_k): r_{k-1} \times r_k
G_d(i_d): r_{d-1} \times 1
전체를 곱하면 다음과 같은 형태가 된다.
(1 \times r_1) (r_1 \times r_2) \cdots (r_{d-1} \times 1) = 1 \times 1
즉, 최종 결과는 scalar이고, 이것이 tensor의 한 원소 A(i_1,\ldots,i_d)가 된다. 여기서 r_1,\ldots,r_{d-1}을 TT-rank라고 부른다. 모든 mode size, 즉 각 index 방향의 크기가 n이고 TT-rank가 대략 r이라면 저장공간은 다음 정도가 된다.
O(dnr^2)
full tensor의 O(n^d)와 비교하면, TT-rank가 작게 유지되는 경우 훨씬 효율적이다.
TT-rank와 unfolding matrix
논문의 중요한 흐름은 TT-rank를 unfolding matrix의 rank와 연결하는 것이다. 여기서 unfolding은 tensor를 matrix처럼 다시 보는 방법이다. Index들을 앞쪽 묶음과 뒤쪽 묶음으로 나누고, 앞쪽 묶음을 row index로, 뒤쪽 묶음을 column index로 사용하는 것이다. 예를 들어 4-dimensional tensor가 있다고 하자.
A(i_1,i_2,i_3,i_4)
이 tensor를 k=2에서 unfolding한다는 것은 다음처럼 index를 묶는다는 뜻이다.
(i_1,i_2) \mid (i_3,i_4)
그리고 이를 matrix로 다시 쓴다.
A_2((i_1,i_2),(i_3,i_4)) = A(i_1,i_2,i_3,i_4)
즉, (i_1,i_2)는 row index가 되고, (i_3,i_4)는 column index가 된다. 만약
A \in \mathbb{R}^{n_1 \times n_2 \times n_3 \times n_4}
이면 이 unfolding matrix의 크기는 다음과 같다.
A_2 \in \mathbb{R}^{(n_1n_2) \times (n_3n_4)}
일반적으로 k번째 unfolding matrix는 tensor의 앞쪽 index들을 row로, 뒤쪽 index들을 column으로 묶은 matrix이다.
A_k = A(i_1,\ldots,i_k; i_{k+1},\ldots,i_d)
즉, A_k의 row index는 (i_1,\ldots,i_k)이고, column index는 (i_{k+1},\ldots,i_d)이다. matrix 크기는 다음과 같다.
\left(\prod_{s=1}^{k} n_s\right) \times \left(\prod_{s=k+1}^{d} n_s\right)
TT-format에서 k 위치를 자른다는 것은 왼쪽 index 묶음 (i_1,\ldots,i_k)과 오른쪽 index 묶음 (i_{k+1},\ldots,i_d)이 내부 index \alpha_k를 통해서만 정보를 주고받는다는 뜻이다. 이때 r_k는 왼쪽과 오른쪽 사이의 연결 차원, 또는 channel 수처럼 볼 수 있다. 그래서 k번째 unfolding matrix는 다음과 같은 factorization 형태를 갖는다.
A_k(\text{left}; \text{right}) = \sum_{\alpha_k=1}^{r_k} L(\text{left}, \alpha_k) R(\alpha_k, \text{right})
즉, 왼쪽 묶음과 오른쪽 묶음 사이의 communication은 \alpha_k=1,\ldots,r_k라는 유한한 channel을 통해 일어난다. 따라서 이 unfolding matrix의 rank는 r_k보다 클 수 없다. 반대로 A_k의 rank가 r_k라면, SVD나 같은 종류의 matrix factorization이 왼쪽과 오른쪽을 잇는 충분한 r_k개의 channel을 제공한다고 이해할 수 있다.
Theorem 2.1의 핵심은 다음과 같다.
각 unfolding matrix A_k의 rank가 r_k이면, TT-rank가 r_k 이하인 TT decomposition이 존재한다.
이 정리는 단순히 존재성만 말하는 것이 아니다. 증명 과정이 실제로 TT decomposition을 구성하는 방법을 제공한다. 즉, TT decomposition은 고차원 tensor를 여러 개의 unfolding matrix로 보고, 각 unfolding의 low-rank structure를 순차적으로 뽑아내는 방식이다.
TT-SVD 알고리즘
Theorem 2.1의 constructive proof는 TT-SVD 알고리즘으로 이어진다. TT-SVD는 full tensor가 주어졌을 때 이를 TT-format으로 변환하는 알고리즘이다. TT-SVD는 두 가지 입력 관점으로 설명할 수 있다. rank를 정해두는 경우에는 각 unfolding SVD에서 유지할 target rank r_k를 먼저 정한다. 오차 허용치를 정해두는 경우에는 전체 error budget에 맞게 작은 singular value를 버리며, 논문의 approximation setting은 이 truncation으로 rank를 결정한다. rank를 정해두는 경우의 전체 흐름을 pseudo-code로 쓰면 다음과 같다. tolerance 기반으로 쓰는 경우에는 2단계에서 고정 rank 대신 truncation error 기준으로 유지할 singular value 수를 고른다고 보면 된다.
Input
- d-dimensional tensor A
- target ranks r_1,\ldots,r_{d-1}
Set
- C = A
- r_0 = 1
For k = 1,\ldots,d-1
Reshape C into a unfolding matrix.
C_k \in \mathbb{R}^{(r_{k-1}n_k) \times (n_{k+1}\cdots n_d)}
Compute truncated SVD.
C_k \approx U_k \Sigma_k V_k^T
Reshape U_k into the k-th TT core.
G_k \in \mathbb{R}^{r_{k-1} \times n_k \times r_k}
Pass the remaining part to the next step.
C = \Sigma_k V_k^T
Finally
- Reshape C into the last core G_d.
핵심은 매 단계에서 현재 tensor를 matrix로 펼치고, SVD의 left singular vectors를 현재 core로 저장한 뒤, 나머지 \Sigma_k V_k^T를 다음 단계로 넘기는 것이다. 이 과정을 d-1번 반복하면 모든 TT core를 얻을 수 있다. 실제 계산에서는 exact low-rank decomposition보다 approximation이 더 중요하다. 그래서 TT-SVD는 singular value를 truncation하여 rank를 줄인다. 논문은 각 단계에서 truncation error를 조절하면 전체 approximation error를 제어할 수 있음을 보인다. 모든 단계에서 너무 작은 singular value를 제거하면 저장공간은 줄어들고, 그 대신 원래 tensor와의 오차가 생긴다.
TT approximation의 안정성
이 논문에서 TT-format이 중요한 이유 중 하나는 approximation의 안정성이다. canonical decomposition에서는 fixed rank approximation이 항상 잘 행동하지 않는다. 어떤 tensor에 대해 best low-rank approximation이 존재하지 않거나, numerical algorithm이 local minimum에 빠질 수 있다. 반면 TT-format은 unfolding matrix의 SVD에 기반한다. SVD는 matrix approximation에서 안정적인 도구이고, TT-SVD는 이를 순차적으로 적용한다. 논문은 TT-format에서 rank bound가 주어졌을 때 best approximation이 존재한다는 점을 강조한다. 또한 TT-SVD로 얻은 approximation은 best approximation과 비교해 quasi-optimal한 error bound를 가진다.
여기서 quasi-optimal은 optimal한 해와 비교했을 때, 오차가 상수배 정도만 차이 나는 해를 말한다. 즉, 완전히 최적인 해는 아니지만 optimal solution과 같은 order의 error를 가지는 approximation이라고 볼 수 있다. 예를 들어 rank 제한을 만족하는 best TT approximation을 A_{\text{best}}라고 하고, TT-SVD로 얻은 approximation을 B라고 하자. 그러면 논문은 대략 다음 형태의 보장을 제시한다.
\|A - B\|_F \le C \|A - A_{\text{best}}\|_F
여기서 C는 상수이다. 즉, TT-SVD가 항상 optimal approximation을 직접 찾는 것은 아니지만, optimal approximation의 error와 비교했을 때 상수배 이내의 error를 보장한다는 의미이다. 직관적으로 말하면 다음과 같다.
TT-format은 tensor approximation 문제를 여러 개의 matrix approximation 문제로 나누어 다룬다.
이 점이 canonical decomposition과 큰 차이이다. canonical format은 parameter 수가 적을 수 있지만, rank 계산과 approximation 문제가 불안정할 수 있다. TT-format은 약간 더 많은 parameter를 사용하더라도 SVD 기반의 안정적인 계산 절차를 제공한다.
TT-rounding
TT tensor끼리 더하거나, TT matrix를 TT vector에 곱하면 결과도 TT-format으로 표현할 수 있다. 그러나 이런 연산을 하면 TT-rank가 증가한다. rank가 계속 증가하면 저장공간과 계산량이 커지므로, 연산 후에 rank를 다시 줄여야 한다. 논문은 이 절차를 TT-rounding이라고 부른다.
TT-rounding은 floating point arithmetic의 rounding과 비슷한 역할을 한다. 숫자 계산에서 필요 이상으로 긴 소수점(digit)을 줄이듯이, TT-format에서는 필요 이상으로 커진 TT-rank를 줄인다. 이 절차에는 두 가지 불변성과 변화가 섞여 있다. 먼저 오른쪽에서 왼쪽으로 진행하는 QR orthogonalization은 표현 방식, 즉 gauge만 바꾸므로 QR pass는 represented tensor를 보존한다. 반대로 왼쪽에서 오른쪽으로 진행하는 SVD truncation은 작은 singular value를 버리므로 tensor를 조금 바꾸지만, 그 controlled error를 대가로 rank를 줄인다. TT-rounding의 큰 흐름은 다음과 같다.
Input
- TT tensor A with cores G_1,\ldots,G_d
- target accuracy \varepsilon
Set
- \delta = \dfrac{\varepsilon}{\sqrt{d-1}}\|A\|_F
Right-to-left orthogonalization
For k = d,\ldots,2:
Reshape the k-th core into a matrix.
G_k(\alpha_{k-1}, i_k, \alpha_k) \rightarrow \widehat{G}_k(\alpha_{k-1}, (i_k,\alpha_k))
\widehat{G}_k \in \mathbb{R}^{r_{k-1} \times (n_k r_k)}
Compute row-orthogonal QR decomposition.
\widehat{G}_k = R_k Q_k
Reshape Q_k back into the k-th core.
G_k \leftarrow \operatorname{reshape}(Q_k,[r_{k-1},n_k,r_k])
Multiply R_k into the previous core G_{k-1} along the shared rank index.
G_{k-1}^{\text{new}}(\alpha_{k-2},i_{k-1},\beta_{k-1}) = \sum_{\alpha_{k-1}} G_{k-1}(\alpha_{k-2},i_{k-1},\alpha_{k-1}) R_k(\alpha_{k-1},\beta_{k-1})
Left-to-right compression
For k = 1,\ldots,d-1:
Reshape the k-th core into a matrix.
G_k(\alpha_{k-1}, i_k, \alpha_k) \rightarrow \widehat{G}_k((\alpha_{k-1}, i_k), \alpha_k)
\widehat{G}_k \in \mathbb{R}^{(r_{k-1}n_k) \times r_k}
Compute \delta-truncated SVD.
\widehat{G}_k \approx U_k \Sigma_k V_k^T \quad \text{by } \operatorname{SVD}_{\delta}(\widehat{G}_k)
Choose the truncated rank \hat r_k so that the discarded singular values are small enough.
여기서 \delta는 전체 허용 오차 \varepsilon로부터 계산된 truncation threshold이다. 각 compression 단계에서는 버려지는 singular value들의 제곱합이 \delta^2 이하가 되도록 rank를 고르며, 이렇게 하면 누적 rounding error를 전체 허용 오차 \varepsilon 안에서 제어할 수 있다.
\sum_{j > \hat r_k} \sigma_j^2 \le \delta^2
즉, 지배적인 singular value만 남긴다.
\Sigma_k = \operatorname{diag}(\sigma_1,\ldots,\sigma_{\hat r_k})
Reshape U_k back into the k-th core.
G_k \leftarrow \operatorname{reshape}(U_k,[r_{k-1},n_k,\hat r_k])
Multiply the remaining factor \Sigma_k V_k^T into the next core G_{k+1}.
G_{k+1}^{\text{new}}(\gamma_k,i_{k+1},\alpha_{k+1}) = \sum_{\alpha_k} (\Sigma_k V_k^T)(\gamma_k,\alpha_k) G_{k+1}(\alpha_k,i_{k+1},\alpha_{k+1})
즉, truncation 이후 남은 오른쪽 factor를 다음 core에 곱해서 넘긴다. 이 과정에서 shared rank index의 크기가 줄어들기 때문에 TT-rank가 감소한다.
Output
- TT tensor B with reduced TT-ranks
논문에서 중요한 점은 rounding을 full tensor로 되돌아가지 않고 TT-format 안에서 수행한다는 것이다. 이 덕분에 이미 압축된 tensor를 효율적으로 recompress할 수 있다. 모든 mode size가 n이고 rank가 r 정도라고 하면, TT-rounding의 복잡도는 대략 다음과 같이 설명된다.
O(dnr^3)
즉, 차원 수 d에 대해 선형적으로 증가한다. 이 점이 고차원 문제에서 중요하다.
Canonical format에서 TT-format으로 변환
논문은 canonical decomposition에서 TT-format으로 변환하는 방법도 다룬다. canonical decomposition은 다음과 같은 형태이다.
A(i_1,\ldots,i_d) = \sum_{\alpha=1}^{R} U_1(i_1,\alpha)\cdots U_d(i_d,\alpha)
이 표현은 각 rank-one term을 TT 구조로 바꾸면 TT-format으로 변환할 수 있다. 단순 변환 후에는 TT-rank가 클 수 있지만, TT-rounding을 적용하면 실제로 필요한 rank를 줄일 수 있다. 논문에서 말하는 변환의 핵심은 canonical decomposition의 summation index \alpha를 TT의 내부 rank index로 그대로 사용하는 것이다. 즉, R개의 canonical term이 있으면 중간 TT-rank를 일단 R로 둔다.
r_1 = r_2 = \cdots = r_{d-1} = R
그리고 각 core를 다음처럼 만든다. 첫 번째 core는 row vector처럼 둔다.
G_1(i_1,\alpha_1) = U_1(i_1,\alpha_1)
마지막 core는 column vector처럼 둔다.
G_d(\alpha_{d-1},i_d) = U_d(i_d,\alpha_{d-1})
중간 core들은 diagonal matrix처럼 만든다.
G_k(\alpha_{k-1},i_k,\alpha_k) = \delta_{\alpha_{k-1},\alpha_k} U_k(i_k,\alpha_k), \quad k=2,\ldots,d-1
여기서 \delta_{\alpha_{k-1},\alpha_k}는 Kronecker delta이다.
\delta_{\alpha_{k-1},\alpha_k} = \begin{cases} 1, & \alpha_{k-1}=\alpha_k \\ 0, & \alpha_{k-1}\ne \alpha_k \end{cases}
이 delta 때문에 TT core들을 곱할 때 모든 내부 index가 같은 경우만 살아남는다.
\alpha_1=\alpha_2=\cdots=\alpha_{d-1}
따라서 TT-format의 내부 summation은 원래 canonical decomposition의 summation과 같아진다.
G_1(i_1)G_2(i_2)\cdots G_d(i_d) = \sum_{\alpha=1}^{R} U_1(i_1,\alpha)\cdots U_d(i_d,\alpha)
즉, canonical format은 중간 core를 diagonal 형태로 만들면 TT-format으로 바로 쓸 수 있다. 다만 이렇게 만든 TT-rank는 일단 R이므로, 실제로는 이 변환 뒤에 TT-rounding을 적용해 불필요한 rank를 줄인다. 이 부분은 논문 전체 흐름에서 중요하다. TT-format은 완전히 새로운 방식으로 tensor를 처음부터 만드는 것뿐 아니라, 기존 low-rank tensor representation을 더 안정적인 구조로 옮기는 도구로도 사용될 수 있다.
TT-format에서의 기본 연산
논문 4절은 TT-format에서 기본 선형대수 연산을 어떻게 수행하는지 다룬다. 어떤 format이 실용적이려면 저장만 잘하는 것으로는 부족하다. 더하기, 곱하기, norm 계산, matrix-vector product 같은 연산이 효율적으로 가능해야 한다. 논문에서 다루는 대표적인 연산은 다음과 같다.
- addition
- scalar multiplication
- multidimensional contraction
- Hadamard product
- scalar product
- norm computation
- matrix-by-vector product
Addition과 scalar multiplication
두 TT tensor가 있다고 하자.
A(i_1,\ldots,i_d) = A_1(i_1)\cdots A_d(i_d)
B(i_1,\ldots,i_d) = B_1(i_1)\cdots B_d(i_d)
목적은 두 TT tensor의 합 C=A+B를 full tensor로 펼치지 않고 다시 TT-format으로 표현하는 것이다. 논문은 이를 core를 block matrix 형태로 합치는 방식으로 설명한다. 중간 core는 다음처럼 만든다.
C_k(i_k) = \begin{bmatrix} A_k(i_k) & 0 \\ 0 & B_k(i_k) \end{bmatrix}, \quad k=2,\ldots,d-1
양 끝 core는 block row, block column으로 만든다.
C_1(i_1) = \begin{bmatrix} A_1(i_1) & B_1(i_1) \end{bmatrix}
C_d(i_d) = \begin{bmatrix} A_d(i_d) \\ B_d(i_d) \end{bmatrix}
이 정의를 사용해 core들을 곱하면, 중간 core의 block diagonal 구조 때문에 위쪽 block은 계속 위쪽 block과만 곱해진다. 예를 들어 첫 번째 중간 core를 곱하면 다음과 같다.
\begin{bmatrix} A_1(i_1) & B_1(i_1) \end{bmatrix} \begin{bmatrix} A_2(i_2) & 0 \\ 0 & B_2(i_2) \end{bmatrix} = \begin{bmatrix} A_1(i_1)A_2(i_2) & B_1(i_1)B_2(i_2) \end{bmatrix}
한 번 더 곱해도 같은 구조가 유지된다.
\begin{bmatrix} \cdots A_{k-1}(i_{k-1}) & \cdots B_{k-1}(i_{k-1}) \end{bmatrix} \begin{bmatrix} A_k(i_k) & 0 \\ 0 & B_k(i_k) \end{bmatrix} = \begin{bmatrix} \cdots A_{k-1}(i_{k-1})A_k(i_k) & \cdots B_{k-1}(i_{k-1})B_k(i_k) \end{bmatrix}
따라서 마지막 core를 곱하기 전에는 다음 형태가 된다.
\begin{bmatrix} A_1(i_1)\cdots A_{d-1}(i_{d-1}) & B_1(i_1)\cdots B_{d-1}(i_{d-1}) \end{bmatrix}
여기에 마지막 core를 곱하면,
\begin{bmatrix} A_1(i_1)\cdots A_{d-1}(i_{d-1}) & B_1(i_1)\cdots B_{d-1}(i_{d-1}) \end{bmatrix} \begin{bmatrix} A_d(i_d) \\ B_d(i_d) \end{bmatrix} = A_1(i_1)\cdots A_d(i_d) + B_1(i_1)\cdots B_d(i_d)
즉, 중간 core의 오른쪽 위 block과 왼쪽 아래 block이 0이기 때문에 A core들과 B core들이 서로 섞이지 않는다. 결과적으로 두 TT tensor의 합 C=A+B가 된다. 이 construction의 rank 효과는 명확하다. 새 TT-rank는 두 tensor의 rank를 더한 만큼 커진다. 그래서 addition 자체는 쉽지만, 여러 번 반복하면 rank growth가 생기고, 실제 계산에서는 보통 addition 뒤에 TT-rounding을 적용해 불필요하게 커진 rank를 다시 줄인다. Scalar multiplication의 목적은 TT 구조를 유지한 채 전체 tensor에 scalar \gamma를 곱하는 것이다. 이 경우 formula는 더 단순하다. core 하나만 scale하면 된다.
\gamma A(i_1,\ldots,i_d) = (\gamma G_1(i_1))G_2(i_2)\cdots G_d(i_d)
이 연산은 core의 rank dimension을 바꾸지 않으므로 TT-rank는 그대로다. 따라서 scalar multiplication만으로는 rounding이 필요하지 않지만, addition이나 product와 함께 반복되는 계산 흐름에서는 뒤따르는 rank 증가를 TT-rounding으로 정리한다.
Multidimensional contraction
Contraction은 특정 index에 대해 합을 취해서 그 index를 없애는 연산이다. 가장 익숙한 예시는 행렬 곱이다.
C(i,k) = \sum_j A(i,j)B(j,k)
여기서 j는 합을 취한 뒤 결과에서 사라진다. 즉, A와 B가 공유하는 index j를 기준으로 contraction한 것이다. Tensor에서도 같은 아이디어가 적용된다. 예를 들어 3-dimensional tensor A(i_1,i_2,i_3)에 vector u_3(i_3)를 곱하고 i_3에 대해 합을 취하면,
B(i_1,i_2) = \sum_{i_3} A(i_1,i_2,i_3)u_3(i_3)
결과는 i_3 index가 사라진 2-dimensional tensor가 된다. 즉, contraction은 index summation을 통해 tensor의 차원을 줄이는 연산이라고 볼 수 있다. 논문에서 말하는 multidimensional contraction의 목적은 여러 index에 대한 큰 summation을 TT core 단위의 작은 계산으로 바꾸는 것이다. 특히 다음 식은 tensor A와 rank-1 canonical tensor의 inner product를 계산하는 형태로 볼 수 있다.
W = \sum_{i_1,\ldots,i_d} A(i_1,\ldots,i_d) u_1(i_1)\cdots u_d(i_d)
여기서 A가 TT-format으로 주어졌다고 하자.
A(i_1,\ldots,i_d) = G_1(i_1)\cdots G_d(i_d)
그러면 각 mode마다 다음 matrix를 만들 수 있다. 이 \Gamma_k formula는 “한 mode씩” contraction한다는 뜻이다. 즉, k번째 physical index i_k에 대해서만 먼저 u_k(i_k)G_k(i_k)를 합쳐서 작은 rank-space matrix로 바꾼다.
\Gamma_k = \sum_{i_k} u_k(i_k)G_k(i_k)
이때 \Gamma_k는 r_{k-1}\times r_k matrix이다. 그러면 전체 contraction은 다음처럼 계산된다.
W = \Gamma_1\Gamma_2\cdots\Gamma_d
즉, 고차원 summation을 직접 수행하지 않고, 각 core에서 작은 matrix를 만든 뒤 그것들을 순서대로 곱한다. 이 연산의 rank 효과는 product처럼 rank를 곱해서 키우는 것이 아니라, contracted mode를 제거하면서 남은 rank-space matrix들을 순차적으로 소거하는 쪽에 가깝다. 따라서 이 canonical-vector contraction 자체에는 보통 별도의 rounding이 필요하지 않다. 다만 더 일반적인 부분 contraction이 새 TT tensor를 남기거나 다른 연산과 결합되면, 이후 rank를 줄이기 위해 TT-rounding을 붙인다. 논문은 이 계산량을 대략 다음과 같이 설명한다.
O(dnr^2)
여기서 핵심은 계산량이 차원 수 d에 대해 선형적으로 증가한다는 점이다.
Hadamard product와 scalar product
Hadamard product의 목적은 두 TT tensor의 같은 entry끼리 곱한 tensor를 만드는 것이다. Hadamard product는 elementwise product이다.
C = A \circ B
즉,
C(i_1,\ldots,i_d) = A(i_1,\ldots,i_d)B(i_1,\ldots,i_d)
TT-format에서는 Hadamard product도 core 단위로 표현할 수 있다. 두 tensor의 core가 각각 A_k(i_k), B_k(i_k)라면,
C_k(i_k) = A_k(i_k)\otimes B_k(i_k)
여기서 \otimes는 Kronecker product이다. 이 문맥에서는 두 core matrix의 rank dimension을 서로 조합해 더 큰 block-like matrix를 만드는 연산이라고 보면 된다. 그래서 core별 Kronecker product를 쓰면 Hadamard product 결과도 TT-format으로 남지만, rank dimension도 함께 조합되므로 rank가 곱처럼 커질 수 있다. 만약 A와 B의 TT-rank가 각각 r_A, r_B 정도라면, C=A\circ B의 rank는 대략 r_A r_B 정도가 된다. 따라서 Hadamard product 뒤에는 결과를 그대로 두기보다 TT-rounding으로 rank를 낮추는 흐름이 자연스럽다. Scalar product의 목적은 두 TT tensor의 inner product를 full tensor summation 없이 계산하는 것이다. Formula상으로는 Hadamard product와 contraction을 이용해 계산할 수 있다.
\langle A,B\rangle = \sum_{i_1,\ldots,i_d} A(i_1,\ldots,i_d)B(i_1,\ldots,i_d)
즉,
\langle A,B\rangle = \sum_{i_1,\ldots,i_d} (A\circ B)(i_1,\ldots,i_d)
따라서 먼저 A\circ B를 생각하고, 모든 u_k(i_k)=1인 contraction을 수행하면 scalar product를 얻을 수 있다. Norm도 scalar product로부터 계산한다.
\|A\|_F = \sqrt{\langle A,A\rangle}
논문은 scalar product를 실제로 구현할 때 Hadamard tensor를 명시적으로 만들지 않고, 작은 matrix들을 순차적으로 곱하는 방식으로 계산할 수 있음을 설명한다. 결과가 scalar이므로 최종 TT-rank를 관리할 필요는 없다. 다만 Hadamard tensor를 중간에 실제로 구성하는 방식으로 구현하면 rank가 곱해질 수 있으므로, 효율적인 구현은 contraction 순서를 잡아 중간 rank growth를 피하거나 필요한 경우 rounding을 사용한다.
Matrix-by-vector product
논문에서 가장 중요한 연산 중 하나는 matrix-by-vector product이다. 목적은 큰 matrix M과 vector x의 곱 y=Mx를 tensorized index와 TT core 계산으로 수행하는 것이다. 고차원 vector를 다음처럼 tensorized vector로 본다.
x(j_1,\ldots,j_d)
그리고 matrix도 각 row/column index를 mode별로 나누어 다음처럼 표현한다.
M(i_1,\ldots,i_d,j_1,\ldots,j_d)
Matrix TT-format에서는 각 core가 (i_k,j_k)를 함께 가진다. 여기서 (i_k,j_k)는 matrix core의 두 physical indices이다. i_k는 output 또는 row 쪽 mode이고, j_k는 input 또는 column 쪽 mode이므로, matrix TT core는 vector TT core처럼 하나의 physical index만 보는 것이 아니라 mode별 row/column index 쌍에 의존한다.
M(i_1,\ldots,i_d,j_1,\ldots,j_d) = M_1(i_1,j_1)\cdots M_d(i_d,j_d)
Vector x도 TT-format이라고 하자.
x(j_1,\ldots,j_d) = X_1(j_1)\cdots X_d(j_d)
그러면 y=Mx는 다음과 같다.
y(i_1,\ldots,i_d) = \sum_{j_1,\ldots,j_d} M(i_1,\ldots,i_d,j_1,\ldots,j_d) x(j_1,\ldots,j_d)
TT-format에서는 이 summation을 core별로 처리할 수 있다. y의 k번째 core는 대략 다음 형태로 만들어진다.
Y_k(i_k) = \sum_{j_k} M_k(i_k,j_k)\otimes X_k(j_k)
이 결과도 TT-format이지만, rank 효과는 Hadamard product와 비슷하다. 새 vector의 TT-rank는 matrix TT-rank와 vector TT-rank의 곱으로 증가한다. 따라서 matrix-vector product 뒤에도 rounding이 필요하다.
따라서 실제 계산 흐름은 다음처럼 된다.
\text{operation} \quad \rightarrow \quad \text{rank growth} \quad \rightarrow \quad \text{TT-rounding}
즉, TT-format의 실용성은 TT-SVD만으로 완성되지 않는다. 연산 후 rank 증가를 제어하는 TT-rounding이 함께 있어야 한다.
Numerical example
논문 5절에서는 19-dimensional operator의 smallest eigenvalue를 계산하는 예시를 보여준다. 이 예시는 TT-format이 단순한 저장 format이 아니라, 실제 고차원 선형대수 계산에 사용할 수 있음을 보이기 위한 것이다. 논문에서 사용하는 operator는 다음 형태이다.
H = \Delta_d + c_v \sum_i \cos(x - x_i) + c_w \sum_{i<j}\cos(x_i-x_j)
여기서 \Delta_d는 d-dimensional Laplace operator이고, 논문은 이를 discretization한 뒤 최소 eigenvalue 문제를 푼다.
Hx = \lambda x, \quad \|x\|_2 = 1, \quad \lambda \rightarrow \min
Discretization 후 matrix H는 크기가 n^d \times n^d가 된다. d=19이면 full matrix를 직접 저장하거나 연산하는 것은 불가능하다. 그래서 논문은 H를 matrix TT-format으로 표현한다.
H(i_1,\ldots,i_d,j_1,\ldots,j_d) = H_1(i_1,j_1)\cdots H_d(i_d,j_d)
논문은 이 operator를 canonical representation에서 TT-format으로 변환한다. 각 항의 구조 때문에 TT-rank가 작게 유지된다. 예를 들어 \Delta_d는 canonical rank d 형태로 표현할 수 있고, TT-rank는 2로 유지된다. Two-particle interaction term도 trigonometric identity를 이용해 낮은 rank 구조로 표현할 수 있다.
\cos(x_i-x_j) = \cos(x_i)\cos(x_j) + \sin(x_i)\sin(x_j)
결과적으로 논문은 H를 TT-rank가 10 이하인 matrix TT-format으로 구성한다. 그 다음 최소 eigenvalue를 직접 구하는 대신 shifted matrix를 사용한다.
\widehat{H} = cI - H
이렇게 하면 H의 smallest eigenvalue를 찾는 문제가 \widehat{H}의 dominant eigenvalue를 찾는 문제로 바뀐다. 논문은 단순한 power iteration을 사용한다. 여기서 c는 H의 eigenvalue들보다 충분히 큰 상수로 잡는다. 그러면 H의 eigenvalue가 \lambda일 때 \widehat{H}의 eigenvalue는 c-\lambda가 되므로, H에서 가장 작은 \lambda가 \widehat{H}에서는 가장 큰 eigenvalue가 된다. 즉 shifted operator는 최소 eigenvalue 문제를 power iteration이 자연스럽게 찾는 dominant eigenvalue 문제로 바꾸는 장치이다. 초기 vector는 H 전체에서 바로 고르는 대신 Laplace operator 부분의 eigenvector에서 가져온다. Discretized Laplace operator는 각 coordinate 방향의 1-dimensional operator가 더해진 separable 구조를 갖기 때문에, 그 기본 eigenvector는 coordinate별 1-dimensional eigenvector들의 outer product로 볼 수 있다. TT 관점에서 이런 완전 분리형 tensor는 core들이 서로 섞일 필요가 없으므로 rank-1 TT vector가 된다.
Power iteration in TT-format
Input
- matrix TT \widehat{H}
- initial TT vector v
- rounding tolerance \varepsilon
Repeat
Apply matrix-by-vector product.
w = \widehat{H}v
Round the result to control TT-rank.
v = T_{\varepsilon}(w)
Normalize.
v = \frac{v}{\|v\|}
Output
- approximate eigenvector v
논문에서는 이 과정을 짧게 다음처럼 쓴다.
v := T_{\varepsilon}(Hv), \quad v = \frac{v}{\|v\|}
이 예시에서 중요한 점은 다음과 같다.
- high-dimensional operator를 TT-format으로 표현한다.
- iterative method에서 matrix-vector product를 수행한다.
- product 후 rank가 증가하므로 TT-rounding으로 rank를 줄인다.
- 작은 TT-rank가 유지되면 고차원 문제도 계산 가능해진다.
논문은 d=19와 n=8,16,32,64에 대해 실험한다. 이때 matrix의 mode size는 최대 64^2=4096까지 커진다. 그럼에도 power iteration 한 step의 시간은 비교적 완만하게 증가하고, solution의 TT-rank는 모든 경우에서 4 이하로 유지됐다고 보고한다.
solution TT-rank가 4 이하라는 점은 이 고차원 eigenvector가 실제로 낮은 TT-rank 구조로 잘 근사됐다는 뜻이다. Matrix-vector product 자체는 rank를 키우지만, rounding 후에도 작은 rank로 정확도를 유지할 수 있었기 때문에 저장량과 연산량이 full tensor 크기 n^d로 폭발하지 않는다.
다만 이 결과가 power iteration이 가장 좋은 eigenvalue solver라는 뜻은 아니다. 논문은 simple power iteration을 주로 matrix-vector product와 TT-rounding이 반복 계산 안에서 동작하는지 확인하는 testbed로 사용한다. 따라서 이 numerical example은 TT-format 연산 pipeline의 가능성을 보여주는 예시이지, best eigenvalue solver를 주장하는 비교 실험은 아니다.
즉, numerical example은 논문 앞부분에서 제시한 개념들이 실제 계산 pipeline으로 이어진다는 것을 보여준다. 특히 중요한 패턴은 다음과 같다.
\text{matrix-vector product} \quad \rightarrow \quad \text{rank growth} \quad \rightarrow \quad \text{TT-rounding}
이 예시는 TT-format의 핵심이 단순한 압축이 아니라, 압축된 상태에서 선형대수 연산을 반복할 수 있게 만드는 데 있다는 점을 보여준다.