/TensorDecompositions.jl

A Julia implementation of tensor decomposition algorithms

Primary LanguageJuliaOtherNOASSERTION

TensorDecompositions.jl

A Julia implementation of tensor decomposition algorithms

Build Status Coverage Status

What's new

  • Compatible with Julia v0.7/v1.0

Available functions

  1. The following functions for Tucker decompositions, except for sshopm, return a Tucker, which contains factors::Vector{Matrix{Float64}}, core::Array{Float64} (1-dimensional array for Kruskal decompositions), and the relative reconstruction error error::Float64.

  • High-order SVD (HOSVD) [3] hosvd{T,N}(tnsr::StridedArray{T,N}, core_dims::NTuple{N, Int}; pad_zeros::Bool=false, compute_error::Bool=false)

  • Canonical polyadic decomposition (CANDECOMP/PARAFAC) candecomp{T,N}(tnsr::StridedArray{T,N}, r::Integer, initial_guess::NTuple{N, Matrix{T}}; method::Symbol=:ALS, tol::Float64=1e-5, maxiter::Integer=100, compute_error::Bool=false, verbose::Bool=true). This function provides two algorithms, set by method argument, for fitting the CANDECOMP model:

    • ALS (default): Alternating least square method [3]
    • SGSD: Simultaneous generalized Schur decomposition [1]

  • Non-negative CANDECOMP/PARAFAC by the block-coordinate update method [7] nncp(tnsr::StridedArray, r::Integer; tol::Float64=1e-4, maxiter::Integer=100, compute_error::Bool=false, verbose::Bool=true)

Remark. Choose a smaller r if the above functions throw ERROR: SingularException.

  • Symmetric rank-1 approximation for symmetric tensors by shifted symmetric higher-order power method (SS-HOPM) [4] sshopm{T,N}(tnsr::AbstractArray{T,N}, alpha::Real; tol::Float64=1e-5, maxiter::Int=100, verbose::Bool=false). This function requires a shifting parameter alpha and returns an eigenpair of tnsr, represented by a tuple (Float64, Vector{Float64}). Note that this functions does NOT check symmetry of input tensors. This implementation takes both dense representation StridedArray and sparse representation (Matrix{Int64}, StridedVector, Integer), which contains indexes, as column vectors of the matrix in the first component of the tuple, corresponding values, and dimension of a mode.

  • Sparse (semi-)nonnegative Tucker decomposition by the alternating proximal gradient method [6] spnntucker{T,N}(tnsr::StridedArray{T, N}, core_dims::NTuple{N, Int}; core_nonneg::Bool=true, tol::Float64=1e-4, hosvd_init::Bool=false, max_iter::Int=500, max_time::Float64=0.0, lambdas::Vector{Float64} = fill(0.0, N+1), Lmin::Float64 = 1.0, rw::Float64=0.9999, bounds::Vector{Float64} = fill(Inf, N+1), ini_decomp = nothing, verbose::Bool=false).

  1. Tensor-CUR for 3-mode tensors [5] is a randomized algorithm and returns a CUR, which includes indexes of c slabs (along axis slab_index) and r fibers, matrix U, and the relative reconstruction error of slabs. Note that this function samples with replacement, and the numbers of repeated samples are stored in Cweight and Rweight.
  • tensorcur3(tnsr::StridedArray, c::Integer, r::Integer, slab_axis::Integer=3; compute_u::Bool=true)
  1. PARAFAC2 for 3-mode tensors by the alternating least square method [2] takes an array of matrices, which may not be equally sized, and factorizes the matrices under a constraint on row space. The below function returns a PARAFAC2, which contains factors and diagonal effects D of each matrix, a common loading matrix A, and the relative error.
  • parafac2{S<:Matrix}(X::Vector{S}, r::Integer; tol::Float64=1e-5, maxiter::Integer=100, verbose::Bool=true)
  • Common parameters:
    • tnsr::StridedArray: Data tensor
    • r::Integer: Number of components/factors
    • tol::Float64: Tolerance to achieve
    • maxiter::Integer: Maximum number of iterations
    • verbose::Bool: Print status when iterative algorithms terminate

Quick example

Here is a quick example of code that fits the CANDECOMP model:

julia> using TensorDecompositions

julia> u = randn(10); v = randn(20); w = randn(30)

# Generate a noisy rank-1 tensor
julia> T = cat(map(x -> x * u * v', w)..., dims=3) + 0.2 * randn(10, 20, 30)

julia> size(T)
(10, 20, 30)

julia> F = candecomp(T, 1, (randn(10, 1), randn(20, 1), randn(30, 1)), compute_error=true, method=:ALS);
NFO: Initializing factor matrices...
INFO: Applying CANDECOMP ALS method...
INFO: Algorithm converged after 4 iterations.

julia> [size(F.factors[i]) for i = 1:3]
3-element Array{Any,1}:
 (10,1)
 (20,1)
 (30,1)

julia> F.props
Dict{Symbol,Any} with 1 entry:
  :rel_residue => 0.18735979193091348

julia> F.factors[1]
10x1 Array{Float64,2}:
  0.0676683 
 -0.0985366 
 -0.239748  
  0.0821674 
 -0.0547672 
 -0.00892641
  0.0220593 
 -0.058075  
 -0.135493  
  0.23256

Requirements

  • Julia 0.7/1.0
  • TensorOperations
  • Distributions
  • StatsBase
  • ProgressMeter
  • FactCheck

Performance issues

  • Inefficiency of unfolding (matricizing), which has a significant impact on the performance of candecomp (method:=ALS) and parafac2

Future plan

  • Improving performance
  • More algorithms for fitting CANDECOMP/PARAFAC and non-negative tensor decompositions
  • Probabilistic tensor decompositions
  • Algorithms for factorizing sparse tensors
  • Tensor completion algorithms

Reference

  • [1] De Lathauwer, L., De Moor, B., & Vandewalle, J. (2004). Computation of the canonical decomposition by means of a simultaneous generalized Schur decomposition. SIAM Journal on Matrix Analysis and Applications, 26(2), 295-327.

  • [2] Kiers, H. A., Ten Berge, J. M., & Bro, R. (1999). PARAFAC2-Part I. A direct fitting algorithm for the PARAFAC2 model. Journal of Chemometrics, 13(3-4), 275-294.

  • [3] Kolda, T. G., & Bader, B. W. (2009). Tensor decompositions and applications. SIAM Review, 51(3), 455-500.

  • [4] Kolda, T. G., & Mayo, J. R. (2011). Shifted power method for computing tensor eigenpairs. SIAM Journal on Matrix Analysis and Applications, 32(4), 1095-1124.

  • [5] Mahoney, M. W., Maggioni, M., & Drineas, P. (2008). Tensor-CUR decompositions for tensor-based data. SIAM Journal on Matrix Analysis and Applications, 30(3), 957-987.

  • [6] Xu, Y. (2015). Alternating proximal gradient method for sparse nonnegative Tucker decomposition. Mathematical Programming Computation, 7(1), 39-70.

  • [7] Xu, Y., & Yin, W. (2013). A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM Journal on Imaging Sciences, 6(3), 1758-1789.

Special thanks

  • Thank @alyst for making the package compatible with Julia 1.0.