Tucker manifold

Tucker{T, D, 𝔽} <: AbstractManifold{𝔽}

The manifold of $N_1×\dots×N_D$ real-valued or complex-valued tensors of fixed multilinear rank $(R_1, \dots, R_D)$ . If $R_1 = \dots = R_D = 1$, this is the Segre manifold, i.e., the set of rank-1 tensors.

Representation in HOSVD format

Let $𝔽$ be the real or complex numbers. Any tensor $p$ on the Tucker manifold can be represented as a multilinear product in HOSVD [LMV00] form

\[p = (U_1,\dots,U_D) ⋅ \mathcal{C}\]

where $\mathcal C \in 𝔽^{R_1×\dots×R_D}$ and, for $d=1,\dots,D$, the matrix $U_d \in 𝔽^{N_d×R_d}$ contains the singular vectors of the $d$th unfolding of $\mathcal{A}$

Tangent space

The tangent space to the Tucker manifold at $p = (U_1,\dots,U_D) ⋅ \mathcal{C}$ is [KL10]

\[T_p \mathcal{M} = \bigl\{ (U_1,\dots,U_D) ⋅ \mathcal{C}^\prime + \sum_{d=1}^D \bigl( (U_1, \dots, U_{d-1}, U_d^\prime, U_{d+1}, \dots, U_D) ⋅ \mathcal{C} \bigr) \bigr\}\]

where $\mathcal{C}^\prime$ is arbitrary, $U_d^{\mathrm{H}}$ is the Hermitian adjoint of $U_d$, and $U_d^{\mathrm{H}} U_d^\prime = 0$ for all $d$.

Constructor

Tucker(N::NTuple{D, Int}, R::NTuple{D, Int}[, field=ℝ]; parameter::Symbol=:type)

Generate the manifold of field-valued tensors of dimensions N[1] × … × N[D] and multilinear rank R = (R[1], …, R[D]).

TuckerPoint{T,D}

An order D tensor of fixed multilinear rank and entries of type T, which makes it a point on the Tucker manifold. The tensor is represented in HOSVD form.

Constructors:

TuckerPoint(core::AbstractArray{T,D}, factors::Vararg{<:AbstractMatrix{T},D}) where {T,D}

Construct an order D tensor of element type T that can be represented as the multilinear product (factors[1], …, factors[D]) ⋅ core. It is assumed that the dimensions of the core are the multilinear rank of the tensor and that the matrices factors each have full rank. No further assumptions are made.

TuckerPoint(p::AbstractArray{T,D}, mlrank::NTuple{D,Int}) where {T,D}

The low-multilinear rank tensor arising from the sequentially truncated the higher-order singular value decomposition of the D-dimensional array p of type T. The singular values are truncated to get a multilinear rank mlrank [VVM12].

TuckerTangentVector{T, D} <: AbstractTangentVector

Tangent vector to the D-th order Tucker manifold at $p = (U_1,\dots,U_D) ⋅ \mathcal{C}$. The numbers are of type T and the vector is represented as

\[X = (U_1,\dots,U_D) ⋅ \mathcal{C}^\prime + \sum_{d=1}^D (U_1,\dots,U_{d-1},U_d^\prime,U_{d+1},\dots,U_D) ⋅ \mathcal{C}\]

where $U_d^\mathrm{H} U_d^\prime = 0$.

Constructor

TuckerTangentVector(C′::Array{T,D}, U′::NTuple{D,Matrix{T}}) where {T,D}

Constructs a Dth order TuckerTangentVector of number type T with $C^\prime$ and $U^\prime$, so that, together with a TuckerPoint $p$ as above, the tangent vector can be represented as $X$ in the above expression.

Base.convert(::Type{Matrix{T}}, basis::CachedBasis{𝔽,DefaultOrthonormalBasis{𝔽, TangentSpaceType},HOSVDBasis{T, D}}) where {𝔽, T, D}
Base.convert(::Type{Matrix}, basis::CachedBasis{𝔽,DefaultOrthonormalBasis{𝔽, TangentSpaceType},HOSVDBasis{T, D}}) where {𝔽, T, D}

Convert a HOSVD-derived cached basis from [DBV21] of the Dth order Tucker manifold with number type T to a matrix. The columns of this matrix are the vectorisations of the embeddings of the basis vectors.

check_point(M::Tucker, p; kwargs...)

Check whether the multidimensional array or TuckerPoint p is a point on the Tucker manifold, i.e. it is a Dth order N[1] × … × N[D] tensor of multilinear rank (R[1], …, R[D]). The keyword arguments are passed to the matrix rank function applied to the unfoldings. For a TuckerPoint it is checked that the point is in correct HOSVD form.

check_vector(M::Tucker{<:Any,D}, p::TuckerPoint{T,D}, X::TuckerTangentVector) where {T,D}

Check whether a TuckerTangentVector X is is in the tangent space to the Dth order Tucker manifold M at the Dth order TuckerPoint p. This is the case when the dimensions of the factors in X agree with those of p and the factor matrices of X are in the orthogonal complement of the HOSVD factors of p.

default_inverse_retraction_method(M::Tucker)

Return PolarInverseRetraction as the default inverse retraction for the Tucker manifold.

default_retraction_method(M::Tucker)

Return PolarRetraction as the default retraction for the Tucker manifold.

default_vector_transport_method(M::Tucker)

Return the ProjectionTransport as the default vector transport method for the Tucker manifold.

embed(::Tucker, p::TuckerPoint, X::TuckerTangentVector)

Convert a tangent vector X with base point p on the rank R Tucker manifold to a full tensor, represented as an N[1] × … × N[D]-array.

embed(::Tucker, p::TuckerPoint)

Convert a TuckerPoint p on the rank R Tucker manifold to a full N[1] × … × N[D]-array by evaluating the Tucker decomposition.

get_basis(:: Tucker, p::TuckerPoint, basisType::DefaultOrthonormalBasis{𝔽, TangentSpaceType}) where 𝔽

An implicitly stored basis of the tangent space to the Tucker manifold. Assume $p = (U_1,\dots,U_D) ⋅ \mathcal{C}$ is in HOSVD format and that, for $d=1,\dots,D$, the singular values of the $d$'th unfolding are $\sigma_{dj}$, with $j = 1,\dots,R_d$. The basis of the tangent space is as follows: [DBV21]

\[\bigl\{ (U_1,\dots,U_D) e_i \bigr\} \cup \bigl\{ (U_1,\dots, \sigma_{dj}^{-1} U_d^{\perp} e_i e_j^T,\dots,U_D) ⋅ \mathcal{C} \bigr\}\]

for all $d = 1,\dots,D$ and all canonical basis vectors $e_i$ and $e_j$. Every $U_d^\perp$ is such that $[U_d \quad U_d^{\perp}]$ forms an orthonormal basis of $ℝ^{N_d}$.

inner(M::Tucker, p::TuckerPoint, X::TuckerTangentVector, Y::TuckerTangentVector)

The Euclidean inner product between tangent vectors X and X at the point p on the Tucker manifold. This is equal to embed(M, p, X) ⋅ embed(M, p, Y).

inner(::Tucker, A::TuckerPoint, X::TuckerTangentVector, Y)
inner(::Tucker, A::TuckerPoint, X, Y::TuckerTangentVector)

The Euclidean inner product between X and Y where X is a vector tangent to the Tucker manifold at p and Y is a vector in the ambient space or vice versa. The vector in the ambient space is represented as a full tensor, i.e., a multidimensional array.

inverse_retract(M::Tucker, p::TuckerPoint, q::TuckerPoint, ::ProjectionInverseRetraction)

The projection inverse retraction on the Tucker manifold interprets q as a point in the ambient Euclidean space (see embed) and projects it onto the tangent space at to M at p.

is_flat(::Tucker)

Return false. Tucker is not a flat manifold.

manifold_dimension(::Tucker)

The dimension of the manifold of $N_1×\dots×N_D$ tensors of multilinear rank $(R_1, \dots, R_D)$, i.e.

\[\mathrm{dim}(\mathcal{M}) = \prod_{d=1}^D R_d + \sum_{d=1}^D R_d (N_d - R_d).\]

project(M::Tucker, p::TuckerPoint, X)

The least-squares projection of a dense tensor X onto the tangent space to M at p.

retract(::Tucker, p::TuckerPoint, X::TuckerTangentVector, ::PolarRetraction)

The truncated HOSVD-based retraction [KSV13] to the Tucker manifold, i.e. the result is the sequentially truncated HOSVD approximation of $p + X$.

In the exceptional case that the multilinear rank of $p + X$ is lower than that of $p$, this retraction produces a boundary point, which is outside the manifold.

vector_transport_to(M::Tucker, Y, p, X, q, ::ProjectionTransport)

Compute the projection vector transport on the Tucker manifold by projecting the tangent vector X onto the tangent space of M at q.

Let

\[p = (C_p, U_p^1, …, U_p^D), \qquad X = (C_X, U_X^1, …, U_X^D) ∈ T_p M, \qquad q = (C_q, U_q^1, …, U_q^1).\]

This means that

\[ X = C_X ×_{j = 1, …, D} U_p^j + \sum_{k = 1}^D C_p ×_{j ≠ k} U_p^j ×_k U_X^k\]

as an embedded vector. Let

\[C_Y = X ×_{j} (U_q^j)^T = C_X ×_{j = 1, …, D} U_p^j (U_q^j)^T + \sum_{k = 1}^D C_p ×_{j ≠ k} U_p^j (U_q^j)^T ×_k U_X^k(U_q^k)^T\]

and

\[U_Y^i = P_{U_q^i}^⊥ \left[X ×_{j ≠ i} (U_q^j)^T\right]_{(i)} (C_q)_{(i)}^+ \\ = \left[C_X ×_{j ≠ i} U_p^j (U_q^j)^T ×_i U_p^i (I - U_q^i (U_q^i)^T)\right]_{(i)} (C_q)_{(i)}^+ + \sum_{k ≠ i} \left[ C_p ×_{j ≠ k ≠ i} U_p^j (U_q^j)^T ×_k U_X^k(U_q^k)^T ×_i U_p^i (I - U_q^i (U_q^i)^T)\right]_{(i)} (C_q)_{(i)}^+ + \left[ C_p ×_{j ≠ i} U_p^j (U_q^j)^T ×_i U_X^i (I - U_q^i (U_q^i)^T)\right]_{(i)} (C_q)_{(i)}^+ \]

Note that $(C_q)_{(i)}^+ = ((C_q)_{(i)}^∗ (C_q)_{(i)})^{-1} (C_q)_{(i)}^∗ = Σ_{(i)}^{-2} (C_q)_{(i)}^∗$, where $Σ_{(i)}$ is the diagonal Matrix containing the singular values of the mode-$i$ unfolding of $C_q$.

Then the transported tangent vector is represented by

\[Y = (C_Y, U_Y^1, …, U_Y^D).\]

For details, see [KSV13].

zero_vector(::Tucker, p::TuckerPoint)

The zero element in the tangent space to p on the Tucker manifold, represented as a TuckerTangentVector.

Base.foreach(f, M::Tucker, p::TuckerPoint, basis::AbstractBasis, indices=1:manifold_dimension(M))

Let basis be and AbstractBasis at a point p on M. Suppose f is a function that takes an index and a vector as an argument. This function applies f to i and the ith basis vector sequentially for each i in indices. Using a CachedBasis may speed up the computation.

NOTE: The i'th basis vector is overwritten in each iteration. If any information about the vector is to be stored, f must make a copy.

Base.ndims(p::TuckerPoint{T,D}) where {T,D}

The order of the tensor corresponding to the TuckerPoint p, i.e., D.

Base.size(p::TuckerPoint)

The dimensions of a TuckerPoint p, when regarded as a full tensor (see embed).

compute_projection_summand!(result::Matrix{T}, buffer::NTuple{5, Array{T}}, core::Array{T, D}, Uᵢ::Matrix{T}, q::TuckerPoint{T, D}, Σ⁻¹::Vector{T}, factors::Vector{Matrix{T}}, i::Int64, add_to_result::Bool) where {T, D}

Helper function for the computation of summands in vector_transport_to_project! Let $q = (C_q, U_q^1, …, U_q^D)$ and $\mathrm{factors} = (F_1, F_2, \ldots, F_D)\, .$ This function computes

\[[\mathrm{core} ×_{j ≠ i} F_j ×_i U_i (I - U_q^i (U_q^i)^T)]_{(i)} \cdot (C_q)_{(i)}^T \cdot Σ^{-1}\, .\]

If add_to_result == true, the result is added to the matrix result, otherwise, result is overwritten. Note that buffer is a 5-tuple of arrays that are used only to store intermediate results of the computation. Let dims be the dimensions of q and ranks its ranks. Then the contents of buffer must be arrays with sizes:

(dims[i], ranks[i]), (dims[i], ranks[i]), (ranks[i], ranks[i]), (ranks...), (ranks...).

contract_with_factors!(result::Array{T, D}, B1::Array{T, D}, B2::Array{T, D}, core::Array{T, D}, factors::Vector{Matrix{T}}, add_to_result::Bool) where {T, D}

This function compute the contraction of the order-D tensor core with the quadratic factor matrices factors. That is, if $\mathrm{factors} = (F_1, F_2, \ldots, F_D)\, ,$ this function computes

\[\mathrm{result}= \mathrm{core} \times_{j = 1, \ldots, D} F_j\]

For D = 3, e.g.

result[n1, n2, n3] = core[r1, r2, r3] * factors[1][r1, n1] * factors[2][r2, n2] * factors[3][r3, n3].

If add_to_result == true, adds to the result array, otherwise overwrites the result array. The arrays B1 and B2 are buffer arrays used to store intermediate results and must have the same size as core.

contract_with_partial_factors!(result::Array{T, D}, B::Array{T, D}, core::Array{T, D}, factors::Vector{Matrix{T}}, k::Int64) where {T, D}

Computes the contraction of the order-$D$ tensor core with the quadratic factor matrices factors in all except the k-th mode. That is, if $\mathrm{factors} = (F_1, F_2, \ldots, F_D)\, ,$ this computes

\[\mathrm{result} = \mathrm{core} \times_{j ≠ k} F_j \, .\]

For D = 3, k = 1, e.g.

result[r1, n1, n2] = core[r1, r2, r3] * factors[2][r2, n2] * factors[3][r3, n3]. The array B is a buffer array used to store intermediate results and must have the same size as core.