Verifying a fixed-rank T3-SVD: error and rank checks#

A short note on how the test suite checks a Tucker-tensor-train SVD (T3-SVD: truncate a tensor X to a fixed-rank T3 X̃, with the ranks chosen from rtol/atol and/or hard caps). The method combines a generalized Oseledets error bound with a rank upper bound proved by a projection argument. The combination — in particular which ranks each check uses — is the subtle part, and getting it wrong produces a rare, input-dependent test failure.

Why two checks#

A correct truncation must be both accurate and parsimonious:

  1. Accuracy — X̃ approximates X to within the requested tolerance.

  2. Parsimony — X̃ uses ranks no larger than necessary for that tolerance.

Neither alone suffices: a routine that returns X unchanged (maximal ranks) passes any accuracy check; a routine that returns 0 (rank 1) passes any rank check. So we check both. The trap is that the two checks are linked through the ranks, and if the accuracy bound is evaluated at the wrong ranks a faulty routine can borrow slack from one check to pass the other (see the last section).

Notation#

Work per stacked slice (batch axes drop out). X ∈ ℝ^{N₁×···×N_d}; ‖·‖ is the Frobenius norm.

  • TT unfoldings X⁽ᵏ⁾, k = 1..d−1: reshape X to (N₁···N_k) × (N_{k+1}···N_d); its singular values σ⁽ᵏ⁾ govern the TT rank r_k.

  • Tucker matricizations X_[i], i = 1..d: mode-i matricization N_i × ∏_{j≠i} N_j; its singular values σ_[i] govern the Tucker rank n_i.

  • X̃: the routine’s output, with chosen ranks r̂_k (TT) and n̂_i (Tucker).

  • Threshold τ = max(rtol·‖·‖, atol).

1. Accuracy check (Oseledets bound, generalized to T3)#

Oseledets (2011), Tensor-Train Decomposition, SIAM J. Sci. Comput. 33(5):2295–2317, Theorem 2.2: the TT-SVD approximation satisfies ‖X − X̃‖² ≤ Σ_{k=1}^{d−1} εₖ², where εₖ is the Frobenius norm of the singular values discarded when truncating the k-th unfolding. A T3 truncates the Tucker factors and the TT core; both are orthogonal projections (in complementary directions), so by Pythagoras the errors add in quadrature, giving the generalized bound

            ┌  d−1                          d                          ┐
‖X − X̃‖² ≤ │  Σ   ‖ σ⁽ᵏ⁾_{> r̂_k} ‖²   +    Σ   ‖ σ_[i]_{> n̂_i} ‖²   │
            └ k=1   (TT unfoldings)        i=1   (Tucker matricizations)┘

The discarded tails are taken beyond the ranks the routine actually returned (r̂_k, n̂_i), evaluated on the original X’s singular values. This is a valid upper bound on the true error: each sequential truncation discards a tail of a projected unfolding, whose singular values are ≤ those of X (Lemma below), so the discarded mass is ≤ ‖σ⁽ᵏ⁾_{> r̂_k}‖.

Algorithm 1 — accuracy check.

input: X (reference), X̃ (result), tol_num (numerical slack)
E² ← 0
for k in 1..d−1:                       # TT unfoldings
    σ ← svals(unfold_k(X));  E² += Σ_{j > r̂_k} σ_j²
for i in 1..d:                         # Tucker matricizations
    σ ← svals(matricize_i(X));  E² += Σ_{j > n̂_i} σ_j²
assert ‖X − X̃‖ ≤ sqrt(E²) + tol_num · ‖X‖

2. Rank check (the projection argument)#

Because Algorithm 1 evaluates the bound at the chosen ranks, a routine that returns huge ranks has vanishing tails and passes accuracy trivially. Parsimony is enforced by bounding the chosen ranks above by the optimal ranks of the original tensor:

Claim. r̂_k ≤ ρ_k := #{ j : σ⁽ᵏ⁾_j ≥ τ } with τ = max(rtol·‖X̃‖, atol), and likewise n̂_i ≤ #{ j : σ_[i]_j ≥ τ }. The routine uses no more rank than truncating the original unfolding at threshold τ would.

Lemma (singular values contract under projection). For orthogonal projections P, Q (so ‖P‖₂, ‖Q‖₂ ≤ 1) and any matrix A, σ_j(P A Q) ≤ ‖P‖₂ · σ_j(A) · ‖Q‖₂ ≤ σ_j(A) for every j.

Proof of the claim. The sequential T3-SVD processes the modes in turn. Just before truncating mode k it holds a reduced tensor C_k obtained from X by the earlier truncations, each of which is an orthogonal projection onto retained dominant singular subspaces. Hence the k-th unfolding is unfold_k(C_k) = P · unfold_k(X) · Q for orthogonal projections P, Q, and by the Lemma

        σ_j( unfold_k(C_k) )  ≤  σ⁽ᵏ⁾_j        for all j.            (∗)

The routine chooses r̂_k = #{ j : σ_j(unfold_k(C_k)) ≥ τ_k }, where τ_k is its per-step threshold. Orthogonal projection does not increase the Frobenius norm, so the running norm is monotone non-increasing, ‖X̃‖ ≤ ‖C_k‖; hence for relative truncation τ_k ≥ rtol·‖C_k‖ ≥ rtol·‖X̃‖, and τ_k ≥ atol for the absolute part — so τ_k ≥ τ := max(rtol·‖X̃‖, atol). Combining with (∗),

r̂_k = #{ σ_j(unfold_k(C_k)) ≥ τ_k }  ≤  #{ σ_j(unfold_k(C_k)) ≥ τ }  ≤  #{ σ⁽ᵏ⁾_j ≥ τ } = ρ_k.   ∎

The Tucker matricization truncations are likewise orthogonal projections onto dominant mode subspaces, so the same bound holds for n̂_i. (Floor ρ at 1, the minimal core rank, and intersect with any user max-rank cap; both preserve the inequality.)

Algorithm 2 — rank check.

input: X, X̃, rtol, atol  (and optional max-rank caps)
τ ← max(rtol · ‖X̃‖, atol)
for k in 1..d−1:
    ρ ← max(1, #{ j : svals(unfold_k(X))_j ≥ τ });   ρ ← min(ρ, cap_k)   # if a cap was given
    assert r̂_k ≤ ρ
for i in 1..d:
    ρ ← max(1, #{ j : svals(matricize_i(X))_j ≥ τ }); ρ ← min(ρ, cap_i)
    assert n̂_i ≤ ρ

The consistency pitfall (the bug this prevents)#

The two checks must use ranks consistently:

  • The accuracy bound (Alg. 1) uses the chosen ranks r̂ — this is the only choice that yields a true upper bound on ‖X − X̃‖.

  • The rank bound (Alg. 2) uses the optimal ranks ρ — the projection argument certifies r̂ ≤ ρ.

It is tempting to compute the accuracy bound at the optimal ranks ρ instead (doing both in one pass). That is wrong: when the sequential truncation’s chosen r̂_k differs from ρ_k — which happens at a singular value sitting near τ — the bound evaluated at ρ_k can be smaller than the true error, so accuracy fails spuriously on a small fraction of inputs. Keeping the two checks decoupled (error at r̂, rank at ρ) is what makes the test both correct and a genuine guard against inflated ranks.

See tests/test_tucker_tensor_train.py::test_t3svd and ::test_t3svd_dense for the implementation.