Multiscale Factorization

Quick Start

In some applications, the input tensor $Y$ to be factorized is a discretization of continuous functions. For example,

\[Y[i,j,k] = f_i(x_j, y_k)\]

for continuous functions $f_i$ and $(i,j,k)\in[I]\times[J]\times[K]$. Instead of calling factorize

factorize(Y; kwargs..)

we can use multiscale_factorize, and pass along information about which dimension come from continuously varying values.

multiscale_factorize(Y; continuous_dims=(2,3), kwargs...)

For fine discretizations, this is often faster and less memory intensive.

Motivating example

Say we have an order $3$-tensor $Y$ with entries

\[Y[i, j, k] = x[i] y[j] z[k]\]

for $(i,j,k) \in [65]\times[129]\times[257]$ representing a discretization of the box $[-1, 1]\times [0, 10]\times [0,1]$.

We might construct this in Julia with the following code.

f(x, y, z) = x*y*z
x = reshape(range(-1, 1, length=65), 65, 1, 1)
y = reshape(range(0, 10, length=129), 1, 129, 1)
z = reshape(range(0, 1, length=257), 1, 1, 257)
Y = f.(x, y, z)

It is true that Y is a CP-rank-$1$ tensor. So we could recover the factors x, y, and z with

decomposition, stats, kwargs = multiscale_factorize(Y;
    model=CPDecomposition, rank=1, continuous_dims=(1,2,3))
x, y, z = factors(decomposition)

The grid $(i,j,k) \in [65]\times[129]\times[257]$ we chose to discretize the function $f(x,y,z)=xyz$ was arbitrary and we could just as easily discretized $f$ on a smaller grid $(i,j,k)\in[10]^3$ or larger one $(i,j,k)\in[257]^3$.

In this setting, we can first decompose a coarse version of Y, for example only using every second grid-points in each dimension

Y_coarse = Y[begin:2:end, begin:2:end, begin:2:end]

and compute a coarse decomposition

model = CPDecomposition
rank = 1
decomposition_coarse, _, _ = factorize(Y_coarse; model, rank)
x_coarse, y_coarse, z_coarse = factors(decomposition_coarse)

We could then initialize the fine scale factorization using an interpolation of the coarse factors found.

init = interpolate.(factors(decomposition))
factorize(Y; model, rank, init)

We can actually do this starting from the most coarse scale with only $3$ points, and gradually refine the decomposition over multiple scale. This is what multiscale_factorize does.

multiscale_factorize(Y; continuous_dims=1:ndims(Y), rank=1, model=Tucker1, kwargs...)

Related exported functions

coarsen(Y::AbstractArray, scale::Integer; dims=1:ndims(Y))

Y = randn(12, 12, 12)

coarsen(Y, 2) == Y[begin:2:end, begin:2:end, begin:2:end]

coarsen(Y, 4; dims=(1, 3)) == Y[begin:4:end, :, begin:4:end]

coarsen(Y, 3; dims=2) == Y[:, begin:3:end, :]

interpolate(Y, scale; dims=1:ndims(Y), degree=0, kwargs...)

julia> Y = collect(reshape(1:6, 2, 3))
2×3 Matrix{Int64}:
 1  3  5
 2  4  6

julia> interpolate(Y, 2)
3×5 Matrix{Int64}:
 1  1  3  3  5
 1  1  3  3  5
 2  2  4  4  6

julia> interpolate(Y, 3; dims=2)
2×7 Matrix{Int64}:
 1  1  1  3  3  3  5
 2  2  2  4  4  4  6

julia> interpolate(Y, 1) == Y
true

scale_constraint(constraint::AbstractConstraint, scale, n_continuous_dims)