Unique Kronecker Product

Introduction

The unique Kronecker product is a math operation which is similar to the Kronecker product but eliminates all the redundant terms appearing due to terms invariant under index permutations. This is easiest to understand through an example.

The example above shows the unique Kronecker product for a vector of $\mathbf{x}\in\mathbb{R}^3$. For a standard Kronecker product the resulting vector becomes a 9-dimensional vector, and we have a 6-dimensional vector when using the unique Kronecker product. Which shows how the unique Kronecker product eliminates 3 of the redundant terms.

Definitions

We define the basic syntax for the general Kronecker product and unique Kronecker product of order $k$ as follows:

\[\begin{align*} \mathbf{x}^{[k]} &= \underbrace{\mathbf{x} \otimes \cdots \otimes \mathbf{x}}_{k-\text{times}} \in \mathbb{R}^{n^k}, \\ \mathbf{x}^{\langle k \rangle} &= \underbrace{\mathbf{x} \oslash \cdots \oslash \mathbf{x}}_{k-\text{times}} \in \mathbb{R}^{\binom{n+k-1}{k}} \end{align*}\]

where $\mathbf{x}\in\mathbb{R}^n$. From this definition, we observe that the dimensions of the Kronecker product grows in the order of $n^k$ but the unique Kronecker grows in the order of $\binom{n+k-1}{k}$. The reduction in computational cost from this order difference becomes significantly obvious in higher-dimensions.

For a second-order Kronecker product, the package supports the following syntax

julia> using UniqueKronecker
julia> n = 33
julia> x = rand(n)3-element Vector{Float64}:
 0.656953623903433
 0.4837388711590681
 0.8290724994482106
julia> x2u = x ⊘ x  # or unique_kronecker(x,x)6-element Vector{Float64}:
 0.43158806395985333
 0.31779400443090566
 0.544662182991179
 0.2340032954702495
 0.4010545949921045
 0.6873612093413032

for higher-order Kronecker products, you can do

julia> using UniqueKronecker
julia> n = 33
julia> k = 55
julia> x = rand(n)3-element Vector{Float64}:
 0.1975051432449747
 0.2999452781172056
 0.4652806055551152
julia> xku = ⊘(x, k)21-element Vector{Float64}:
 0.00030053291791846005
 0.0004564105428718825
 0.0007079923881521738
 0.0006931373278088788
 0.0010752073099472138
 0.0016678812595744246
 0.0010526473647583896
 0.0016328858596646964
 0.002532962433535284
 0.003929177689748906
 ⋮
 0.003846735882947726
 0.005967127111529749
 0.009256316796532518
 0.0024277845721101666
 0.00376602386595126
 0.0058419251534278585
 0.009062101227452709
 0.014057297294953102
 0.021805936865951538

Another concept we need to define is the vectorization and half-vectorization operators $\mathrm{vec}(\cdot)$ and $\mathrm{vech}(\cdot)$, respectively. The vectorization operator flattens a matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$ in the column direction creating a vector of size $mn$. On the other hand, the half-vectorization operator vectorizes the matrix but only half of it or discarding the supradiagonal entries. These operations are strongly related to the second-order Kronecker and unique Kronecker products, and those relationships are described in the picture below.

The vectorization operator is already defined in the LinearAlgebra package as the function vec, but we define the functions vech for the half-vectorization operator and invec function for the inverse-vectorization operator that reverses the vectorization.

We are aware that similar concepts exists in the tensor algebra literature, and the vectorization and half-vectorization operations can be generalized to higher-order Kronecker products. However, for ease of exposition, we only illustrate the second-order Kronecker product case.

Columnwise Operation on Snapshot Matrices

We also employ the functions

• kron_snapshot_matrix
• unique_kron_snapshot_matrix

which allows you to apply the Kronecker product and unique Kronecker product on each column of a matrix. For example

julia> using UniqueKronecker
julia> X = [1 2; 3 4]2×2 Matrix{Int64}:
 1  2
 3  4
julia> X2 = kron_snapshot_matrix(X, 2)4×2 Matrix{Int64}:
 1   4
 3   8
 3   8
 9  16

julia> using UniqueKronecker
julia> X = [1 2; 3 4]2×2 Matrix{Int64}:
 1  2
 3  4
julia> X2u = unique_kron_snapshot_matrix(X, 2)3×2 Matrix{Int64}:
 1   4
 3   8
 9  16

unique_kronecker(x::AbstractVector{T}, y::AbstractVector{T}) where T

unique_kronecker(x::AbstractVector{T}, y::AbstractVector{T}, z::AbstractVector{T}) where T

unique_kronecker(x::AbstractVector{T}, y::AbstractVector{T}, z::AbstractVector{T}, w::AbstractVector{T}) where T

⊘(x::AbstractVector{T}, y::AbstractVector{T}) where T

⊘(x::AbstractArray{T}...) where {T<:Number}

kron_snapshot_matrix(Xmat::AbstractArray{T}, p::Int) where {T<:Number}

unique_kron_snapshot_matrix(Xmat::AbstractArray{T}, p::Int) where {T<:Number}