Convergence Analysis of Two Alternating Iterative Schemes for Tucker Decomposition

Technical Summary: Convergence Analysis of Two Alternating Iterative Schemes for Tucker Decomposition

Problem Statement
The paper addresses the computation of the Tucker decomposition (TD) for an $m$-mode tensor $\mathcal{B} \in \mathbb{C}^{n_1 \times n_2 \times \dots \times n_m}$. The objective is to find orthonormal factor matrices $P_\ell \in \text{St}(k_\ell, n_\ell)$ (where $\text{St}$ denotes the complex Stiefel manifold) and a core tensor $\mathcal{T}$ such that the approximation error $\|\mathcal{B} - \mathcal{T} \times_1 P_1 \times_2 P_2 \dots \times_m P_m\|_F$ is minimized. This is equivalent to maximizing the objective function $f(P_1, \dots, P_m) = \|\mathcal{B} \times_1 P_1^H \times_2 P_2^H \dots \times_m P_m^H\|_F^2$.

While two popular alternating iterative schemes exist for this problem—the Higher-Order Orthogonal Iteration (HOOI) and the Alternating Subspace Iteration (ASI)—their theoretical convergence properties have been previously incomplete. Specifically, the analysis of ASI by Kroonenberg and De Leeuw (1980) contained technical gaps, and the analysis of a "greedy" HOOI variant by Xu (2018) was restricted to real tensors and relied on advanced semi-algebraic function theory (Kurdyka–Lojasiewicz) less familiar to the numerical linear algebra community.

Methodology
The authors reformulate the minimization of the approximation error as a maximization problem involving $m$ coupled nonlinear matrix equations. These equations are interpreted in two ways:

1. As a system of coupled Nonlinear Eigenvalue Problems with eigenvector dependency (NEPv).
2. As a system of coupled Nonlinear Polar Decompositions with orthonormal polar factor dependency (NPDo).

The paper analyzes two algorithms based on these formulations:

• HOOI (Algorithm 4.1): A Gauss-Seidel type scheme where, at each step, $P_\ell$ is updated to be the matrix of the top $k_\ell$ left singular vectors of a specific unfolded tensor (or equivalently, the top $k_\ell$ eigenvectors of a Hermitian matrix $H_\ell$).
• ASI (Algorithm 5.1): A Gauss-Seidel type scheme where $P_\ell$ is updated via a one-step subspace iteration (specifically, the orthonormal polar factor of $H_\ell P_\ell$), rather than solving the full eigenvalue problem.

The convergence analysis relies on tools from numerical linear algebra, including canonical angles between subspaces, error bounds for extreme eigenvalue/singular value approximations via matrix traces, and properties of the Grassmann manifold. The analysis is conducted for complex tensors, with real tensors treated as a special case.

Key Contributions

1. Rigorous Convergence Proofs: The paper provides detailed convergence analyses for both HOOI and ASI. It proves that under mild conditions, both methods generate sequences where the objective function increases monotonically and converges.
2. Global Convergence to Stationary Points: The authors demonstrate that both algorithms converge globally to stationary points satisfying the Karush-Kuhn-Tucker (KKT) conditions.
   • For HOOI, the limit points satisfy a system of coupled NEPv equations where the eigenvalues correspond to the largest eigenvalues of the associated Hermitian matrices.
   • For ASI, the limit points satisfy a system of coupled NPDo equations.
3. Handling of Non-Uniqueness: The analysis addresses the inherent non-uniqueness of the Tucker decomposition (due to unitary invariance). The authors show that while the sequence of matrices may not converge entry-wise without alignment, the sequence of subspaces converges, and the objective function converges.
4. Complex Tensor Generalization: Unlike previous works restricted to real tensors, this analysis applies to complex tensors, broadening the applicability of the convergence guarantees.
5. Clarification of "Greedy" Alignment: The paper argues that the "alignment" step (adjusting the phase/orientation of $P_\ell$ at each iteration to match the previous step), proposed by Xu for greedy HOOI, is numerically unnecessary for the quality of the final approximation, though it may be useful for theoretical convergence proofs.

Results

• Theoretical Results:
  • Monotonicity: Both algorithms produce a monotonically increasing sequence of objective values.
  • Stationarity: Accumulation points of the generated sequences satisfy the KKT conditions.
  • Convergence Rates: The paper establishes that the sum of squared distances between consecutive iterates (weighted by eigenvalue gaps or singular values) is finite, implying the iterates approach a stationary point.
  • Global Convergence: If the stationary point is isolated and certain spectral gap conditions (for HOOI) or full-rank conditions (for ASI) are met, the entire sequence converges to that point.
• Numerical Experiments:
  • Experiments were conducted on a "Miranda Scientific Simulation Tensor" and randomly generated tensors (both real and complex).
  • HOOI vs. ASI: HOOI consistently required fewer iterations to converge than ASI because it computes the optimal subspace at each step, whereas ASI performs only a single power iteration step.
  • Initialization: Using a truncated HOSVD as an initial guess generally reduced the number of iterations, though not universally (in some cases, random initialization converged faster).
  • Complexity: While HOOI converges in fewer iterations, the computational cost per iteration is higher than ASI. However, the authors observed that the total CPU time for both methods was competitive, as the savings in iteration count for HOOI balanced the higher per-step cost.
  • Stopping Criteria: The experiments highlighted the risk of "false convergence" where the objective function plateaus temporarily before rising again, suggesting that residual-based stopping criteria are more robust than objective-value-based ones.

Significance and Claims
The paper claims to provide a more accessible and self-contained convergence analysis for Tucker decomposition algorithms compared to prior work. By relying entirely on numerical linear algebra concepts rather than semi-algebraic geometry, the results are intended to be more approachable for the numerical linear algebra community. The authors emphasize that their analysis covers both real and complex tensors and corrects gaps in the historical analysis of ASI. They conclude that while HOOI is theoretically superior in terms of iteration count, both methods are globally convergent and effective for computing Tucker decompositions, with the choice between them potentially depending on the specific trade-off between iteration count and per-iteration computational cost.