Algebraic Operations on Tensor Trains

기술 요약: 텐서 트레인(Tensor Trains)의 대수적 연산

문제 정의
고차원 텐서는 양자 화학, 시스템 식별, 동적 계획법과 같은 응용 분야에서 빈번하게 발생합니다. 차원에 따른 텐서 요소의 지수적 증가("차원의 저주")는 전체 텐서를 저장하고 조작하는 것을 비실용적으로 만듭니다. 텐서 트레인(TT) 형식(또는 Matrix Product State, MPS로도 알려짐)은 텐서를 관리 가능한 결합 차원(bond dimensions)을 가진 일련의 저계수 코어(wagon)로 표현함으로써 이 문제를 해결합니다.

그러나 이미 TT 형식으로 존재하는 텐서에 대해 대수적 연산을 수행하는 것은 상당한 어려움을 수반합니다. 구체적으로 다음과 같습니다:

1. 합산(Summation): 여러 개의 TT를 더하는 것(예: Sum of Tensor Trains 또는 SOTT)은 나이브하게 변환할 경우 결합 차원이 지나치게 큰 단일 TT를 생성할 수 있습니다.
2. 아다마르 곱(Hadamard Product): 두 TT의 요소별 곱은 이론적으로 개별 결합 차원의 곱($B_{prod} = B_1 B_2$)과 같은 결합 차원을 가집니다. 결합 차원이 큰 경우(예: $B=1000$), 중간 단계의 wagon들이 너무 커져서 저장할 수 없게 됩니다(코어당 $10^6$개의 요소, 총 $10^{12}$개의 요소 발생).
3. 행렬-벡터 곱(Matrix-Vector Product): 연산자 $H$(Matrix Product Operator, MPO)와 벡터 $x$(MPS)가 모두 TT 형식인 경우 $y = Hx$를 계산하는 작업 역시 거대한 결합 차원의 확장을 초래합니다.

기존의 "텐서 라운딩(tensor rounding)"(결합 차원 축소) 방법들은 종종 트레이드오프 문제에 직면합니다. 전통적인 알고리즘(예: TT-SVD)은 높은 정확도를 제공하지만 계산 비용이 많이 들며, 더 빠른 무작위 방식이나 Khatri-Rao 곱(KRP) 기반 방식은 손실이 발생하는 시나리오에서 정확도가 떨어지는 경향이 있습니다.

방법론
본 논문은 개선된 일반화된 TTSVDTT(TT에 적용된 Tensor Train SVD) 알고리즘 변형을 제안합니다. 핵심 방법론은 거대한 중간 텐서를 명시적으로 구축하는 것을 피하는 데 있습니다. 대신, 행렬 분해를 사용하여 이러한 텐서들의 곱에 직접 작용합니다.

1. 스트랭귤레이션(Strangulation) 및 SVD: 이 접근 방식은 텐서를 행렬로 재구성하고 SVD를 통해 결합 차원을 절단하는 "스트랭귤레이션"을 활용합니다.
2. 암시적 행렬 연산(Implicit Matrix Operations): TTSVDTT 알고리즘의 경우, 거대한 행렬 $X_n$(전체 곱 텐서 wagon을 포함하는)을 직접 형성하는 대신, 알고리즘은 $X_n X_n^T$를 암시적으로 계산합니다. $X_n$의 좌측 특이 벡터를 $X_n X_n^T$의 고유 벡터로부터 도출합니다.
3. 촐레스키 분해(Cholesky Decomposition) 및 절단된 SVD: 핵심 혁신은 행렬 $M_n = X_n X_n^T$를 $S_n S_n^T$(예: 촐레스키 분해를 통해)로 분해하는 것입니다. 알고리즘은 전체 $X_n$에 대해 절단된 SVD를 수행하는 대신, $z_n$과 $S_n$으로부터 유도된 더 작은 보조 텐서 $Y_n$에 대해 절단된 SVD를 수행하여 원하는 wagon $y_n$을 계산합니다.
4. 특화된 변형들: 본 논문은 전체 곱 텐서를 명시적으로 형성하지 않고 세 가지 특정 입력 형식을 처리하도록 이 프레임워크를 확장합니다:
   • SOTT (Sum of TTs): $M$개의 트레인의 합에 대해, 알고리즘은 결합된 wagon의 블록 대각 구조를 활용하여 $O(M^2)$ 메모리 복잡도를 피하기 위해 대각 블록만을 저장합니다.
   • 아다마르 곱 (TTSVDHP): 두 TT의 요소별 곱에 대해, 알고리즘은 두 TT의 전체 크로네커 곱을 피합니다. 알고리즘은 작은 구성 행렬($f_n$ 및 $g_n$)을 각각 곱함으로써 거대한 크로네커 구조를 가진 곱을 계산하는 항등식 $\text{vec}(ABC) = (C^T \otimes A)\text{vec}(B)$를 활용합니다.
   • MPO-MPS 곱 (TTSVDHX): $y=Hx$의 곱을 계산할 때, 알고리즘은 전체 곱 wagon보다 훨씬 작은 보조 텐서($z_n, V_n, Y_n$)를 계산하여 효율적인 절단을 가능하게 합니다.

주요 기여

1. 일반화된 TTSVDTT: 본 논문은 단일 TT가 아닌 합산된 TT, 아다마르 곱, 또는 MPO-MPS 곱을 다룰 수 있는 일반화된 TTSVDTT 알고리즘을 제시합니다.
2. 메모리 효율성: 제안된 알고리즘(TTSVDHP 및 TTSVDHX)은 전체 곱 텐서를 평가하거나 그로 인해 발생하는 거대한 중간 배열을 저장하지 않고도 텐서 곱을 라운딩할 수 있게 합니다.
3. 정확도-속도 트레이드오프: 본 논문은 "연속적 무작위 압축(Successive Randomized Compression, SRC)" 및 KRP 기반 라운딩 방식에 대한 대안을 도입합니다. 무작위 방식이 더 빠를 수는 있지만, 제안된 TTSVDTT 변형들은 정밀도가 중요한 손실 시나리오에서 더 나은 계산 효율성과 정확도의 균형을 제공합니다.
4. CPD to TT 변환: 본 방법론은 텐서를 Canonical Polyadic Decomposition(CPD) 형식에서 TT 형식으로(그리고 그 반대로) 변환할 때, 모든 텐서 요소를 평가하지 않고도 이를 가능하게 합니다. 이는 CPD를 결합 차원이 1인 SOTT의 특수한 경우로 취급함으로써 이루어집니다.

결과
합성 데이터와 실제 양자 화학 문제를 대상으로 수치 실험이 수행되었습니다:

• SOTT/CPD: CP 모델(rank 1000)을 TT로 변환하는 과정에서, 특화된 TTSVDCP 알고리즘은 전통적인 TT 라운딩의 높은 정확도를 유지하면서도 가장 빠른 방법들과 경쟁할 만한 속도를 보여주었습니다.
• 아다마르 곱: 결합 차원 20인 두 TT의 요소별 곱을 포함하는 실험에서, 제안된 TTSVDHP 알고리즘은 TTSVDTT 및 전통적인 라운딩과 유사한 피팅 오차를 달면서도 훨씬 빠른 속도를 기록했습니다. 또한 메모리 제약으로 인해 다른 방법들이 실패했던 높은 차원에서도 성공적으로 작동했습니다.
• MPO-MPS 곱: $y=Hx$를 계산하는 과정에서, TTSVDHX 알고리즘은 전통적인 TT 라운딩 및 TTSVDTT와 거의 동일한 정확도를 입증했으며, SRC 및 KRP 방법보다 정확도 면에서 우수했습니다. 결합 차수가 증가함에 따라 계산 복잡도가 전통적인 방식보다 낮은 비율로 증가했습니다.
• 양자 화학 응용: 알고리즘은 순환 방향족 분자(벤젠, [10]annulene, [18]annulene)의 해밀토니안(Hamiltonian)의 이차 형식(quadratic form)을 최소화(바닥 상태 에너지 찾기)하는 데 적용되었습니다. TTSVDHX 알고리즘은 DMRG 알고리즘에 의해 확인된 최소 에너지를 성공적으로 계산하였으며, 이는 실질적인 실행 가능성을 입증합니다.

의의 및 주장
본 논문은 제안된 알고리즘이 최신 기술(state-of-the-art) 방법들과 비교하여 계산 효율성과 정확도 사이에서 개선된 트레이드오프를 달 Achieve 한다고 주장합니다. 구체적으로:

• 무작위 또는 KRP 기반 알고리즘이 최대 50배 더 빠를 수는 있지만 손실 시나리오에서 정확도가 떨어지는 것과 달리, 제안된 TTSVDTT 변형들은 전통적인 TT-SVD 방식의 높은 정확도를 유지하면서도 속도 향상을 제공합니다.
• 이 알고리즘들은 명시적 확장을 수행하지 않고 압축된 표현 위에서 동작함으로써 텐서 대수(합, 아다마르 곱, 행렬-벡터 곱)에 내재된 "메모리 병목" 문제를 해결합니다.
• 본 연구는 고차원 응용 분야, 특히 양자 화학 분야를 위한 강력한 도구를 제공하며, 메모리 제한으로 인해 다루기 힘든 거대 해밀토니안에 대한 제약된 이차 최적화 문제(고유값 문제)를 해결할 수 있게 합니다.