GitHub

UniqueKronecker.jl

UniqueKronecker.jl is a Julia package for computing non-redundant (unique) Kronecker products of vectors, generalizing to n dimensions and k-repeated products. It also provides efficient implementations of the Khatri-Rao (column-wise Kronecker) and face-splitting (row-wise Kronecker) products, along with their unique counterparts. The package includes utility functions to work with the associated coefficient matrices, enabling conversions between unique and standard products.

What is the Unique Kronecker Product?

The standard Kronecker product of a vector $\mathbf{x} \in \mathbb{R}^n$ with itself, $\text{kron}(\mathbf{x}, \mathbf{x}) = \mathbf{x} \otimes \mathbf{x}$, produces all possible pairwise products of its elements, resulting in redundant terms when $x_i x_j = x_j x_i$.

The unique Kronecker product, denoted here as $\text{uniquekron}(\mathbf{x},\mathbf{x}) = \mathbf{x} \oslash \mathbf{x}$, eliminates these redundancies by considering only unique combinations of indices. For example:

For $\mathbf{x} \in \mathbb{R}^2$:

  • Standard Kronecker product:

\[ \mathbf{x} \otimes \mathbf{x} = \begin{bmatrix} x_1^2 \\ x_1 x_2 \\ x_2 x_1 \\ x_2^2 \end{bmatrix}\]

  • Unique Kronecker product:

\[ \mathbf{x} \oslash \mathbf{x} = \begin{bmatrix} x_1^2 \\ x_1 x_2 \\ x_2^2 \end{bmatrix}\]

Here, $x_1 x_2$ and $x_2 x_1$ are considered the same and included only once.

Coefficient Matrices

The package provides functions to compute the associated coefficient matrices:

  • Unique Kronecker Coefficient Matrix $\mathbf{A}_{2u} \in \mathbb{R}^{n \times \frac{n(n+1)}{2}}$: Represents the mapping of the unique Kronecker product back to the original vector $\mathbf{x}\in\mathbb{R}^2$.
  • Kronecker Coefficient Matrix $\mathbf{A}_2 \in \mathbb{R}^{n \times n^2}$: Represents the mapping of the Kronecker product back to the original vector.

These matrices are useful for applications in polynomial regression, symmetric tensor computations, and vectorization of symmetric matrices.

Features

  • Compute the unique Kronecker product for vectors of any dimension $n$ and any repeated (Kronecker) order $k$.
  • Generate the associated polynomial and Kronecker coefficient matrices $\mathbf{A}_{2u}$ and $\mathbf{A}_2$.
  • Convert between unique and standard Kronecker products.
  • Khatri-Rao Product: Compute column-wise Kronecker products of matrices and their unique variants.
  • Face-Splitting Product: Compute row-wise Kronecker products of matrices and their unique variants.
  • Utility functions for polynomial modeling and symmetric tensor operations.

Installation

You can install it using the command

using Pkg
Pkg.add("UniqueKronecker")
using UniqueKronecker

or install it directly from GitHub:

using Pkg
Pkg.add(url="https://github.com/YourUsername/UniqueKronecker.jl")

Replace YourUsername with the actual GitHub username or organization where the package is hosted.

Usage

Importing the Package

using UniqueKronecker

Computing the Unique Kronecker Product

Compute the $k$-th order unique Kronecker product of vector x:

x = [2.0, 3.0, 4.0]  # Example vector in ℝ³

x_unique_kron =  x ⊘ x 
println(x_unique_kron)
# Output: [4.0, 6.0, 8.0, 9.0, 12.0, 16.0]
# Corresponding to [x₁², x₁x₂, x₁x₃, x₂², x₂x₃, x₃²]

Computing Coefficient Matrices

Polynomial Matrix $\mathbf{A}_2$

Compute the polynomial coefficient matrix $\mathbf{A}_2$:

n = 3
H = zeros(n,n^2)
for i in 1:n
    x = rand(n)
    H[i,:] = kron(x,x)
end

println(H)
# Output: A matrix of size (3, 9) for this example

Unique/Nonredundant Polynomial Coefficient Matrix $\mathbf{A}_{2u}$

Convert the polynomial matrix $\mathbf{A}_2$ into the unique polynomial coefficient matrix $\mathbf{A}_{2u}$:

A2u = eliminate(A2, 2)

println(A2u)
# Output: A matrix of size (3, 6) for this example

This can be converted back

A2 = duplicate(A2u, 2)
println(A2)
# Output: the H matrix

To make the coefficients symmetric for redundant terms use duplicate_symmetric

A2s = duplicate_symmetric(A2u, 2)
println(A2s)
# Output: the H matrix with symmetric coefficients

Relationship Between Matrices

The following relationship holds:

\[\mathbf{A}_{2u} \cdot (\mathbf{x} \oslash \mathbf{x}) = \mathbf{A}_2 \cdot (\mathbf{x} \otimes \mathbf{x})\]

This allows mapping between the unique Kronecker product space and the standard Kronecker product space.

Generalizing to Higher-Order Products

Compute higher-order unique Kronecker products by specifying a higher value of $k$:

k = 3  # Third-order product

x_unique_kron_k3 = unique_kronecker(x, k)  # or ⊘(x,k)

println(x_unique_kron_k3)
# Output: Corresponding unique products of order 3

Khatri-Rao Product

The Khatri-Rao product (also known as the column-wise Kronecker product) takes two matrices and performs the Kronecker product on corresponding columns:

A = [1 2; 3 4]
B = [5 6; 7 8]

# Standard Khatri-Rao product
kr = khatri_rao(A, B)  # or A ⊙ B
# Column 1: kron([1,3], [5,7]) = [5,7,15,21]
# Column 2: kron([2,4], [6,8]) = [12,16,24,32]

# Unique Khatri-Rao product (eliminates redundancies in each column)
ukr = unique_khatri_rao(A, B)  # or A ⨸ B

# Self-product with power
kr_power = khatri_rao(A, 3)  # or A ⊙ 3
ukr_power = unique_khatri_rao(A, 3)  # or A ⨸ 3

The Khatri-Rao product is particularly useful in:

  • Multilinear algebra
  • Tensor decompositions
  • Signal processing and array processing
  • Machine learning feature engineering

Face-Splitting Product

The face-splitting product (also known as the row-wise Kronecker product) takes two matrices and performs the Kronecker product on corresponding rows:

A = [1 2; 3 4]
B = [5 6; 7 8]

# Standard face-splitting product
fs = face_split(A, B)  # or A ⊖ B
# Row 1: kron([1,2], [5,6]) = [5,6,10,12]
# Row 2: kron([3,4], [7,8]) = [21,24,28,32]

# Unique face-splitting product (eliminates redundancies in each row)
ufs = unique_face_split(A, B)  # or A ⧁ B

# Self-product with power
fs_power = face_split(A, 2)  # or A ⊖ 2
ufs_power = unique_face_split(A, 2)  # or A ⧁ 2

The face-splitting product is useful in:

  • Matrix polynomial operations
  • Row-wise tensor computations
  • Structured matrix operations

Circulant Kronecker Product

The circulant Kronecker product sums over all cyclic permutations of the Kronecker products. It's particularly useful for computing derivatives of Kronecker products:

x = [1, 2]
y = [3, 4]

# Circulant Kronecker product
ck = circulant_kronecker(x, y)  # or x ⊛ y
# Result: (x ⊗ y) + (y ⊗ x)

# Three vectors
z = [5, 6]
ck3 = x ⊛ y ⊛ z
# Result: (x ⊗ y ⊗ z) + (y ⊗ z ⊗ x) + (z ⊗ x ⊗ y)

The circulant Kronecker product is useful in:

  • Computing derivatives of Kronecker products (e.g., $\frac{\partial (\mathbf{x}\otimes\mathbf{x})}{\partial \mathbf{x}} = \mathbf{I} \circledast \mathbf{x}$)
  • Tensor calculus and differential operations
  • Symmetric polynomial structures
  • Applications requiring all cyclic permutations

Applications

  • Polynomial Regression: Efficient computation of polynomial features without redundant terms.
  • Symmetric Tensor Computations: Simplifies operations involving symmetric tensors.
  • Model Reduction: Construction of reduced-order models with polynomial structures.
  • Machine Learning: Feature engineering for higher-order interactions.

Contributing

Contributions are welcome! If you find a bug or have a feature request, please open an issue. If you'd like to contribute code, feel free to submit a pull request.

License

This project is licensed under the MIT License.