# Introduction to tensorr In tensorr: Sparse Tensors in R

## Introduction

tensorr provides methods to manipulate and store sparse tensors. Tensors are multidimensional generalizations of matrices (two dimensional) and vectors (one dimensional).

It has three main goals:

• Provide an efficient format to store sparse tensors in R.
• Provide standard tensor operations such as multiplication and unfolding.
• Provide standard tensor decomposition techniques such as CP and Tucker.

The aim of this vignette is not to provide a mathematical overview of Tensors, please see Kolda and Bader (2009) instead. It assumes that you have some working knowledge of tensors and want to know how to use them in R.

Let's start with a simple motivating example for sparse tensor usage. Say we have a three-dimensional 2x2x2 tensor with non-zero values in the first and fifth positions (remember R arrays/matrices are column oriented). We could represent this object with a standard R array:

dims <- c(2,2,2)
z <- array(c(10,0,0,0,20,0,0,0), dims)
z


But since many of the values are zero, it makes more sense to only store this as a sparse tensor. Let's create this object by providing the indices (subscripts) of the non-zero values.

library(tensorr)

subs <- list(c(1,1,1), c(1,1,2))
vals <- c(10, 20)
dims <- c(2,2,2)
x <- sptensor(subs, vals, dims)
x


For this small example, the benefit from using a sparse tensor is not apparent (and in fact the sparse object is larger than the dense one if you check object.size), but for larger tensors this advantage will prove useful.

We'll go over the different kinds of operations you can perform below, but for now feel free to try a few out:

# element-wise math operations
x + x
2 * x
x * x
max(x)

# extracting
x[1,1,1]
x[1:4]
x[list(c(1,1,1), c(1,1,2), c(2,2,2))]

# replacing
x[1,1,2] <- 30

# converting
as_dtensor(x)

# tensor multiplication
m <- matrix(1:6, nrow = 3, ncol = 2)
ttm(x, m, 2)

# unfolding
unfold(x, 1)


## Tensor Classes

The tensorr package provides S4 classes for sparse and dense tensor representations. The sptensor class is a new sparse tensor class, with non-zero values and subscripts stored in coordinate list format (coo) to reduce storage requirements (Note the Matrix package refers to this as triplet format, and its corresponding class is TsparseMatrix). The dtensor class is a wrapper around R's existing dense multidimensional array, but adds functionality for tensor operations such as multiplication and unfolding.

### Sparse Tensors

A sparse tensor can be created with a list or matrix of subscripts, a numeric vector of non-zero values, and an integer vector of dimensions. Here's a summary of the basic commands needed to create sparse tensors.

Let's create a 2x2x2 sptensor with non-zero values in the first and fifth positions. You can create one with a list of subscripts.

subs <- list(c(1,1,1), c(1,1,2))
vals <- c(10, 20)
dims <- c(2,2,2)
x <- sptensor(subs, vals, dims)


Or, alternatively, you can provide a matrix of subscripts. Note that the subscripts are represented as a matrix where the ith row corresponds to the ith dimension and the jth column is the subscript to the jth non-zero value.

subs <- matrix(c(1,1,1, 1,1,2), nrow = length(dims))
x <- sptensor(subs, vals, dims)


The constructor components are stored as slots in the object and can be accessed via slots (x@subs, x@vals, x@dims) or the preferred accessor functions.

# subscripts for non-zero values
nzsubs(x)

# non-zero values
nzvals(x)

# dimensions
dim(x)


See methods(class = "sptensor") for a full list of operations associated with this class.

### Dense Tensors

Dense tensors can be created by simply providing an existing multidimensional array to the constructor. You can access the non-zero subscripts, non-zero values, and dimensions the same way you would for a sparse tensor.

dims <- c(2,2,2)
arr <- array(c(10,0,0,0,20,0,0,0), dims)
z <- dtensor(arr)

nzsubs(z)
nzvals(z)
dim(z)


See methods(class = "dtensor") for a full list of operations associated with this class.

### Unfolded Tensors

You can also directly create unfolded-sptensor and unfolded-dtensor classes, though most likely you will only interact with these objects after unfold-ing an existing tensor. The unfolding operation is discussed more in depth in a later section. The complement to unfolding is refold-ing. Here's an example of unfolding our tensor along the first dimension and then refolding it back.

unfold(x, 1)
refold(unfold(x,1))


### Converting Between Classes

You can easily convert between sparse and dense tensor representations.

# convert dense tensor to sparse
as_sptensor(z)

# convert sparse tensor to dense
as_dtensor(x)


You can also turn a data frame of indices into a sparse tensor. Each column in the data frame corresponds to a specific dimension. The last column in the data frame is assumed to contain the value, unless otherwise specified.

df <- data.frame(i = c(1, 1), j = c(1, 1), k = c(1,2), val = c(10, 20))
df

as_sptensor(df, dims = dims)


## Extracting and Replacing

The extraction [ and replacement [<- functions work exactly as they would for multidimensional arrays, with one addition - they can also accept a list or matrix of subscripts. This feature was added to aid in programming workflows (as opposed to interactive usage).

If you have a high dimensional array it can be cumbersome to write all the subscript for each dimension, e.g. x[1,2,4,5,1,1,1,21,100], and it is more likely that you will make mistakes. But if you are able to programmatically generate these subscripts then you can simply pass a list/matrix instead.

### Standard Indexing

If the dimensions of your tensor aren't too high, you can take advantage of standard indexing the way you would with any matrix or array in R. This format takes a comma-separated list of arguments (since [ and [<- are actually functions)

x[1,1,1]
x[1,2,2]

x[1,1,1] <- 100
x[2,2,2] <- 200
x


You can also pass ranges or leave out arguments where you want to extract or replace all the values in that dimension.

x[1,,]
x[1,1:2,1:2]
x[1,,,drop=TRUE]


### Linear Indexing

You can also index the tensor by treating it as a single vector of values. Note that R indexes values in column-wise fashion, which means that the first index changes the fastest and the last index changes the slowest as you traverse the array. For example, these would be the indices of a 2x2x2 multidimensional array.

array(1:8, c(2,2,2))


Using this pattern, we can extract or replace tensor values by passing a single vector of numeric values with each value corresponding to a linear index.

# get the first three values
x[c(1,2,3)]

# alternatively
x[1:3]

# replace the first and fifth values
x[c(1,5)] <- c(-10, -20)
x


### List/Matrix Indexing

Another way to extract or replace values from a tensor is use a list/matrix of subscripts (similarly to how you would construct an sptensor). As stated above, this can be useful if you have a high dimensional tensor and have a way to programmatically produce indices. In the example below we'll create the list manually.

subs <- list(c(1,1,1), c(1,2,1), c(1,1,2))
x[subs]
x[subs] <- c(50, 60, 70)
x


### Dimnames Indexing

You can also add dimnames to your sparse tensor and extract by specifying the dimname.

dimnames(x) <- list(LETTERS[1:2], letters[1:2], month.abb[1:2])
dimnames(x)

x[,,"Feb"]
identical(x[,,"Feb"], x[,,2])


## Group Generics

A number of group generics are also defined for tensors (if you're unfamiliar with group generics, see ?S4GroupGeneric), including

• Arithmetic (+, - , *, ...)
• Comparisons (==, >, !=, ...)
• Logic (&, |)
• Math (abs, sqrt, ..)
• Summary (max, min, sum, ...)

We we'll go over a few examples for each group, but not every one. Feel free to experiment on your own! For these examples we'll use our sparse tensor x, which currently has values:

x


Note that these operations will throw a warning if the operation converts zero values to non-zero values since this will likely cause the sparse tensor to become extremely dense.

### Arithmetic

These are element-wise operations. To perform tensor operations see the section on Tensor Multiplication.

x + x


Note that if an operation results in all the values equal to zero, then the tensor will return empty subscripts and values.

x - x


### Comparisons and Logic

These operations are also element-wise, returning a tensor with logical values.

x > 100
x > 2*x


Note the warning when returning a tensor that is mostly TRUE values.

x == x


### Math

sqrt(x)
log1p(x)
abs(x)


Again, we'll get a warning if we apply a function that converts zero values to non-zero values.

log(x)


### Summary

Note that any time we apply min or range to a tensor we'll get 0 if there are any zero values in the tensor. If you just want the min or range of non-zero values call these functions on the result of nzvals

max(x)
range(x)
range(nzvals(x))


## Unfolding

Unfolding, or matricizing, re-orders the fibers of tensor to be columns in a matrix. A fiber is analogous to a row or column in a 2D matrix in that they are obtained by holding every dimension constant except for one. For example, the mode-1 fibers of our sparse tensor x are x[,1,1], x[,2,1], x[,1,2], and x[,2,2]. The unfold function takes a tensor, finds the fibers, and makes them the columns in a new matrix.

u <- unfold(x,1)
u


Unfolding is important because many tensor operations can be expressed as operations on unfolded tensors, so we can take advantage of existing tools and methods for working with matrices. For example, the n-mode product of a tensor and a matrix can be written as the matrix product of the unfolded tensor and the matrix. See [Tensor Multiplication] and Kolda and Bader (2009) for more info.

Of course, each unfolded tensor can be easily refolded to its original state.

refold(u)


## Tensor Multiplication

Tensor multiplication is analogous to matrix multiplication, but is a little more complex due to the number of dimensions.

### Tensor Times Matrix

Currently, this package only implements the n-mode product. This product keeps all tensor indices constant except for the nth, and sums the product of these values with a matrix of size $j \times i_n$. If we have a tensor $\mathbf{X}$ and a matrix $U$, then we can write this product down as (per Kolda (2009)):

$$(\mathbf{X} \times_n U){i_1i_2...i{n-1} j i_{n+1}...i_N} = \sum_{i_n = 1}^{I_n}{x_{i_1i_2...i_N}u_{ji_n}}$$ However, as stated previously, this operation can also be expressed by unfolding the sparse tensor:

$$\mathbf{Y} = \mathbf{X} \times_n U \Leftrightarrow Y_{(n)} = UX_{(n)}$$ where $Y_{(n)}$ and $X_{(n)}$ represent unfolded tensors along the nth dimension. This product can be executed using ttm. For example, we can multiply our sparse tensor along the 2nd mode. Notice how dimensions of the resulting tensor change in the 2nd dimension.

m <- matrix(1:6, nrow = 3, ncol = 2)
ttm(x, m, 2)


### Tensor Times Vector

Using ttv to multiply a tensor times a vector is equivalent to using ttm to multiply by a matrix with a single column except that the nth dimension of size one will be dropped automatically. So the result of ttv is a tensor with one less dimension.

v <- 1:3
ttv(x,c(3,4),2)


### Tensor Times Tensor (Outer Product)

The outer product of two tensors results in a tensor with dimension c(dim(x),dim(y)). This is essentially a sparse implementation of the outer function in the base package. The function ttt is an alias for outerprod.

outerprod(x,x)
identical(ttt(x,x), outerprod(x,x))


### Norm and Inner Product

You can also calculate the Frobenius norm of a tensor and the inner product between two tensors.

norm(x)
sqrt(innerprod(x,x))


## Future Work

I plan to add common tensor decompositions, such as CP and Tucker, to the tensorr package in the near future. Any other requests and suggestions are welcome.

## References

Many of the dense and sparse implementation ideas were adapted from:

• B. W. Bader and T. G. Kolda. Algorithm 862: MATLAB tensor classes for fast algorithm prototyping, ACM Transactions on Mathematical Software 32(4):635-653, December 2006.
• B. W. Bader and T. G. Kolda. Efficient MATLAB computations with sparse and factored tensors, SIAM Journal on Scientific Computing 30(1):205-231, December 2007.
• scikit-tensor

For a review on tensors, see:

• T. G. Kolda and B. W. Bader, Tensor Decompositions and Applications, SIAM Review 51(3):455-500, September 2009

## Try the tensorr package in your browser

Any scripts or data that you put into this service are public.

tensorr documentation built on May 2, 2019, 3:26 a.m.