truncations.md

CurrentModule = MatrixAlgebraKit
CollapsedDocStrings = true

Truncations

Truncation strategies allow you to control which eigenvalues or singular values to keep when computing partial or truncated decompositions. These strategies are used in the functions eigh_trunc, eig_trunc, and svd_trunc to reduce the size of the decomposition while retaining the most important information.

Using Truncations in Decompositions

Truncation strategies can be used with truncated decomposition functions in two ways, as illustrated below. For concreteness, we use the following matrix as an example:

using MatrixAlgebraKit
using MatrixAlgebraKit: diagview

A = [2 1 0; 1 3 1; 0 1 4];
D, V = eigh_full(A);
diagview(D) ≈ [3 - √3, 3, 3 + √3]

# output
true

1. Using the trunc keyword with a NamedTuple

The simplest approach is to pass a NamedTuple with the truncation parameters. For example, keeping only the largest 2 eigenvalues:

Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = (maxrank = 2,));
size(Dtrunc, 1) <= 2

# output
true

Note however that there are no guarantees on the order of the output values:

diagview(Dtrunc) ≈ diagview(D)[[3, 2]]

# output
true

You can also use tolerance-based truncation or combine multiple criteria:

Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = (atol = 2.9,));
all(>(2.9), diagview(Dtrunc))

# output
true

Use maxrank together with a tolerance to keep at most maxrank values above the tolerance (intersection):

Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = (maxrank = 2, atol = 2.9));
size(Dtrunc, 1) <= 2 && all(>(2.9), diagview(Dtrunc))

# output
true

Use minrank together with a tolerance to guarantee at least minrank values are kept (union):

Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = (atol = 3.5, minrank = 2));
size(Dtrunc, 1) >= 2

# output
true

In general, the keyword arguments that are supported can be found in the TruncationStrategy docstring:

TruncationStrategy()

2. Using explicit TruncationStrategy objects

For more control, you can construct TruncationStrategy objects directly. This is also what the previous syntax will end up calling.

Dtrunc, Vtrunc = eigh_trunc(A; trunc = truncrank(2))
size(Dtrunc, 1) <= 2

# output
true

Strategies can be combined with & (intersection: keep values satisfying all conditions):

Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = truncrank(2) & trunctol(; atol = 2.9))
size(Dtrunc, 1) <= 2 && all(>(2.9), diagview(Dtrunc))

# output
true

Strategies can also be combined with | (union: keep values satisfying any condition). This is useful to set a lower bound on the number of kept values with minrank:

Dtrunc, Vtrunc, ϵ = eigh_trunc(A; trunc = trunctol(; atol = 3.5) | truncrank(2))
size(Dtrunc, 1) >= 2

# output
true

Truncation Strategies

MatrixAlgebraKit provides several built-in truncation strategies:

notrunc
truncrank
trunctol
truncfilter
truncerror

Strategies can be composed using the & operator (TruncationIntersection) to keep only values satisfying all conditions, or the | operator (TruncationUnion) to keep values satisfying any condition.

TruncationIntersection
TruncationUnion

# Keep at most 10 values, all above tolerance (intersection)
combined_trunc = truncrank(10) & trunctol(; atol = 1e-6);

# Keep values above tolerance, but always at least 3 (union)
combined_trunc = trunctol(; atol = 1e-6) | truncrank(3);

Truncation Error

When using truncated decompositions such as svd_trunc, eig_trunc, or eigh_trunc, an additional truncation error value is returned. This error is defined as the 2-norm of the discarded singular values or eigenvalues, providing a measure of the approximation quality. For svd_trunc and eigh_trunc, this corresponds to the 2-norm difference between the original and the truncated matrix. For the case of eig_trunc, this interpretation does not hold because the norm of the non-unitary matrix of eigenvectors and its inverse also influence the approximation quality.

For example:

using LinearAlgebra: norm
U, S, Vᴴ, ϵ = svd_trunc(A; trunc=truncrank(2))
norm(A - U * S * Vᴴ) ≈ ϵ # ϵ is the 2-norm of the discarded singular values

# output
true

Truncation with SVD vs Eigenvalue Decompositions

When using truncations with different decomposition types, keep in mind:

• svd_trunc: Singular values are always real and non-negative, sorted in descending order. Truncation by value typically keeps the largest singular values. The truncation error gives the 2-norm difference between the original and the truncated matrix.

• eigh_trunc: Eigenvalues are real but can be negative for symmetric matrices. By default, eigenvalues are treated by absolute value, e.g. truncrank(k) keeps the k eigenvalues with largest magnitude (positive or negative). The truncation error gives the 2-norm difference between the original and the truncated matrix.

• eig_trunc: For general (non-symmetric) matrices, eigenvalues can be complex. By default, eigenvalues are treated by absolute value. The truncation error gives an indication of the magnitude of discarded values, but is not directly related to the 2-norm difference between the original and the truncated matrix.