Sparse Tensors

MATLAB has no native ability to store sparse multidimensional arrays, only sparse matrices. Moreover, the compressed sparse column storage format for MATLAB sparse matrices is not readily adaptable to sparse tensors. Instead, the sptensor class stores the data in coordinate format. The sptensor class is best described in the following reference:

Contents

Creating a sptensor

A sparse tensor can be created by passing in a list of subscripts and values. For example, here we pass in three subscripts and a scalar value. The resuling sparse tensor has three nonzero entries, and the size is the size of the largest subscript in each dimension.

rand('state',0); %<-- Setup for the script
subs = [1,1,1;1,2,1;3,4,2]; %<-- Subscripts of the nonzeros.
vals = [1; 2; 3]; %<-- The values of the nonzeros.
X = sptensor(subs,vals) %<-- Create a sparse tensor with 3 nonzeros.
X is a sparse tensor of size 3 x 4 x 2 with 3 nonzeros
	(1,1,1)     1
	(1,2,1)     2
	(3,4,2)     3
X = sptensor(subs,vals,[3 5 2]) %<-- Or, specify the size explicitly.
X is a sparse tensor of size 3 x 5 x 2 with 3 nonzeros
	(1,1,1)     1
	(1,2,1)     2
	(3,4,2)     3

Values corresponding to repeated subscripts are summed. Also note that we can use a scalar as the second argument.

subs = [1 1 1; 1 1 3; 2 2 2; 4 4 4; 1 1 1; 1 1 1]; %<-- (1,1,1) is repeated.
X = sptensor(subs,2) %<-- Equivalent to X = sptensor(subs,2*ones(6,1)).
X is a sparse tensor of size 4 x 4 x 4 with 4 nonzeros
	(1,1,1)     6
	(1,1,3)     2
	(2,2,2)     2
	(4,4,4)     2

Specifying the accumulation method for the constructor

By default, values corresponding to repeated elements are summed. However, it is possible to specify other actions to be taken.

X = sptensor(subs,2*ones(6,1),[4 4 4],@max) %<-- Maximum element.
X is a sparse tensor of size 4 x 4 x 4 with 4 nonzeros
	(1,1,1)     2
	(1,1,3)     2
	(2,2,2)     2
	(4,4,4)     2
myfun = @(x) sum(x) / 3; %<-- Total sum divided by three.
X = sptensor(subs,2*ones(6,1),[4 4 4],myfun) %<-- Custom accumulation function.
X is a sparse tensor of size 4 x 4 x 4 with 4 nonzeros
	(1,1,1)    2.0000
	(1,1,3)    0.6667
	(2,2,2)    0.6667
	(4,4,4)    0.6667

Creating a one-dimensional sptensor.

X = sptensor([1;3;5],1,10) %<-- Same as X = sptensor([1;3;5],[1;1;1],1,10).
X is a sparse tensor of size 10 with 3 nonzeros
	(1)     1
	(3)     1
	(5)     1
X = sptenrand(50,5) %<-- A random, sparse, order-1 tensor with 5 nonzeros.
X is a sparse tensor of size 50 with 5 nonzeros
	(12)    0.7621
	(25)    0.4565
	(31)    0.0185
	(45)    0.8214
	(48)    0.4447

Creating an all-zero sptensor

X = sptensor([],[],[10 10 10]) %<-- Creates an all-zero tensor.
X is an all-zero sparse tensor of size 10 x 10 x 10
X = sptensor([10 10 10]) %<-- Same as above.
X is an all-zero sparse tensor of size 10 x 10 x 10

Constituent parts of a sptensor

X = sptenrand([40 30 20],5); %<-- Create data.
X.subs %<-- Subscripts of nonzeros.
ans =

     8    27     3
    25    13     2
    30    13     1
    32    29     8
    37    28    17

X.vals %<-- Corresponding nonzero values.
ans =

    0.2028
    0.1987
    0.6038
    0.2722
    0.1988

X.size %<-- The size.
ans =

    40    30    20

Creating a sparse tensor from its constituent parts

Y = sptensor(X.subs,X.vals,X.size) %<-- Copies X.
Y is a sparse tensor of size 40 x 30 x 20 with 5 nonzeros
	( 8,27, 3)    0.2028
	(25,13, 2)    0.1987
	(30,13, 1)    0.6038
	(32,29, 8)    0.2722
	(37,28,17)    0.1988

Creating an empty sptensor

An empty constructor exists, primarily to support loads of previously saved data.

Y = sptensor %<-- Create an empty sptensor.
Y is an all-zero sparse tensor of size [empty tensor]

Use sptenrand to create a random sptensor

X = sptenrand([10 10 10],0.01) %<-- Create a tensor with 1% nonzeroes.
X is a sparse tensor of size 10 x 10 x 10 with 10 nonzeros
	( 1,9,2)    0.4966
	( 3,4,9)    0.8998
	( 5,6,7)    0.8216
	( 5,7,4)    0.6449
	( 5,9,2)    0.8180
	( 6,5,9)    0.6602
	( 7,2,6)    0.3420
	( 8,1,7)    0.2897
	( 9,8,4)    0.3412
	(10,4,6)    0.5341

It is also posible to specify the precise number of nonzeros rather than a percentage.

X = sptenrand([10 10 10],10) %<-- Create a tensor with 10 nonzeros.
X is a sparse tensor of size 10 x 10 x 10 with 10 nonzeros
	(4, 2, 3)    0.5828
	(4,10, 1)    0.4235
	(5, 3, 5)    0.5155
	(6, 3, 3)    0.3340
	(6, 9, 2)    0.4329
	(7, 8,10)    0.2259
	(7, 9, 1)    0.5798
	(8, 8, 2)    0.7604
	(8,10, 7)    0.5298
	(9, 6, 9)    0.6405

Use squeeze to remove singleton dimensions from a sptensor

Y = sptensor([1 1 1; 2 1 1], 1, [2 1 1]) %<-- Create a sparse tensor.
squeeze(Y) %<-- Remove singleton dimensions.
Y is a sparse tensor of size 2 x 1 x 1 with 2 nonzeros
	(1,1,1)     1
	(2,1,1)     1
ans is a sparse tensor of size 2 with 2 nonzeros
	(1)     1
	(2)     1

Use squash to remove empty slices from a sptensor

Y = sptensor([1 1 1; 3 3 3], [1; 3], [3 3 3]) %<-- Create a sparse tensor.
squash(Y) %<-- Remove empty slices.
Y is a sparse tensor of size 3 x 3 x 3 with 2 nonzeros
	(1,1,1)     1
	(3,3,3)     3
ans is a sparse tensor of size 2 x 2 x 2 with 2 nonzeros
	(1,1,1)     1
	(2,2,2)     3

Use full or tensor to convert a sptensor to a (dense) tensor

X = sptensor([1 1 1; 2 2 2], [1; 1]); %<-- Create a sparse tensor.
Y = full(X) %<-- Convert it to a (dense) tensor.
Y is a tensor of size 2 x 2 x 2
	Y(:,:,1) = 
	     1     0
	     0     0
	Y(:,:,2) = 
	     0     0
	     0     1
Y = tensor(X) %<-- Same as above.
Y is a tensor of size 2 x 2 x 2
	Y(:,:,1) = 
	     1     0
	     0     0
	Y(:,:,2) = 
	     0     0
	     0     1

Use sptensor to convert a (dense) tensor to a sptensor

Z = sptensor(Y) %<-- Convert a tensor to a sptensor.
Z is a sparse tensor of size 2 x 2 x 2 with 2 nonzeros
	(1,1,1)     1
	(2,2,2)     1

Use double to convert a sptensor to a (dense) multidimensional array

Y = double(X) %<-- Creates a MATLAB array.
Y(:,:,1) =

     1     0
     0     0


Y(:,:,2) =

     0     0
     0     1

Use find to extract nonzeros from a tensor and then create a sptensor

The find command can be used to extract specific elements and then convert those into a sptensor.

X = tensor(rand(5,4,2),[5 4 2]) %<-- Create a tensor.
S = find(X > 0.9) %<-- Extract subscipts of values greater than 0.9.
V = X(S) %<-- Extract the corresponding values.
Y = sptensor(S,V,[5 4 2]) %<-- Create a new tensor.
X is a tensor of size 5 x 4 x 2
	X(:,:,1) = 
	    0.2091    0.5678    0.4154    0.9708
	    0.3798    0.7942    0.3050    0.9901
	    0.7833    0.0592    0.8744    0.7889
	    0.6808    0.6029    0.0150    0.4387
	    0.4611    0.0503    0.7680    0.4983
	X(:,:,2) = 
	    0.2140    0.4120    0.6833    0.2071
	    0.6435    0.7446    0.2126    0.6072
	    0.3200    0.2679    0.8392    0.6299
	    0.9601    0.4399    0.6288    0.3705
	    0.7266    0.9334    0.1338    0.5751

S =

     1     4     1
     2     4     1
     4     1     2
     5     2     2


V =

    0.9708
    0.9901
    0.9601
    0.9334

Y is a sparse tensor of size 5 x 4 x 2 with 4 nonzeros
	(1,4,1)    0.9708
	(2,4,1)    0.9901
	(4,1,2)    0.9601
	(5,2,2)    0.9334

Use ndims and size to get the size of a sptensor

ndims(Y) %<-- Number of dimensions or modes.
ans =

     3

size(Y) %<-- Size of Y.
ans =

     5     4     2

size(Y,3) %<-- Size of mode 3 of Y.
ans =

     2

Use nnz to get the number of nonzeros of a sptensor

nnz(Y) %<-- Number of nonzeros in Y.
ans =

     4

Subscripted reference for a sptensor

X = sptensor([4,4,4;2,2,1;2,3,2],[3;5;1],[4 4 4]) %<-- Create a sptensor.
X is a sparse tensor of size 4 x 4 x 4 with 3 nonzeros
	(2,2,1)     5
	(2,3,2)     1
	(4,4,4)     3
X(1,2,1) %<-- Extract the (1,2,1) element, which is zero.
ans =

     0

X(4,4,4) %<-- Extract the (4,4,4) element, which is nonzero.
ans =

     3

X(1:2,2:4,:) %<-- Extract a 2 x 3 x 4 subtensor.
ans is a sparse tensor of size 2 x 3 x 4 with 2 nonzeros
	(2,1,1)     5
	(2,2,2)     1
X([1 1 1; 2 2 1]) %<-- Extract elements by subscript.
ans =

     0
     5

X([1;6]) %<-- Same as above but with linear indices.
ans =

     0
     5

As with a tensor, subscriped reference may be ambiguous for one-dimensional tensors.

X = sptensor([1;3;5],1,7) %<-- Create a sparse tensor.
X is a sparse tensor of size 7 with 3 nonzeros
	(1)     1
	(3)     1
	(5)     1
X(3) %<-- Fully specified, single elements are always returned as scalars.
ans =

     1

X([3;6]) %<-- Returns a subtensor.
ans is a sparse tensor of size 2 with 1 nonzeros
	(1)     1
X([3;6],'extract') %<-- Same as above *but* returns an array.
ans =

     1
     0

Subscripted assignment for a sptensor

X = sptensor([30 40 20]) %<-- Create an emtpy 30 x 40 x 20 sptensor.
X is an all-zero sparse tensor of size 30 x 40 x 20
X(30,40,20) = 7 %<-- Assign a single element.
X is a sparse tensor of size 30 x 40 x 20 with 1 nonzeros
	(30,40,20)     7
X([1,1,1;2,2,2]) = [1;1] %<-- Assign a list of elements.
X is a sparse tensor of size 30 x 40 x 20 with 3 nonzeros
	(30,40,20)     7
	( 1, 1, 1)     1
	( 2, 2, 2)     1
X(11:20,11:20,11:20) = sptenrand([10,10,10],10) %<-- Assign a subtensor.
X is a sparse tensor of size 30 x 40 x 20 with 13 nonzeros
	(30,40,20)    7.0000
	( 1, 1, 1)    1.0000
	( 2, 2, 2)    1.0000
	(12,13,15)    0.9342
	(13,12,11)    0.2644
	(13,12,16)    0.1603
	(13,17,14)    0.8729
	(15,13,14)    0.2379
	(18,11,14)    0.6458
	(19,11,14)    0.9669
	(19,12,15)    0.6649
	(19,19,12)    0.8704
	(20,20,19)    0.0099
X(31,41,21) = 4 %<-- Grows the size of the sptensor.
X is a sparse tensor of size 31 x 41 x 21 with 14 nonzeros
	(30,40,20)    7.0000
	( 1, 1, 1)    1.0000
	( 2, 2, 2)    1.0000
	(12,13,15)    0.9342
	(13,12,11)    0.2644
	(13,12,16)    0.1603
	(13,17,14)    0.8729
	(15,13,14)    0.2379
	(18,11,14)    0.6458
	(19,11,14)    0.9669
	(19,12,15)    0.6649
	(19,19,12)    0.8704
	(20,20,19)    0.0099
	(31,41,21)    4.0000
X(111:120,111:120,111:120) = sptenrand([10,10,10],10) %<-- Grow more.
X is a sparse tensor of size 120 x 120 x 120 with 24 nonzeros
	( 30, 40, 20)    7.0000
	(  1,  1,  1)    1.0000
	(  2,  2,  2)    1.0000
	( 12, 13, 15)    0.9342
	( 13, 12, 11)    0.2644
	( 13, 12, 16)    0.1603
	( 13, 17, 14)    0.8729
	( 15, 13, 14)    0.2379
	( 18, 11, 14)    0.6458
	( 19, 11, 14)    0.9669
	( 19, 12, 15)    0.6649
	( 19, 19, 12)    0.8704
	( 20, 20, 19)    0.0099
	( 31, 41, 21)    4.0000
	(112,111,118)    0.3759
	(112,115,112)    0.0099
	(112,115,113)    0.4199
	(112,120,117)    0.7537
	(114,115,115)    0.7939
	(115,115,117)    0.9200
	(117,115,116)    0.8447
	(118,115,120)    0.3678
	(119,119,111)    0.6208
	(119,119,117)    0.7313

Use end as the last index.

X(end-10:end,end-10:end,end-5:end)  %<-- Same as X(108:118,110:120,115:120)
ans is a sparse tensor of size 11 x 11 x 6 with 7 nonzeros
	( 3, 2,4)    0.3759
	( 3,11,3)    0.7537
	( 5, 6,1)    0.7939
	( 6, 6,3)    0.9200
	( 8, 6,2)    0.8447
	( 9, 6,6)    0.3678
	(10,10,3)    0.7313

Use elemfun to manipulate the nonzeros of a sptensor

The function elemfun is similar to spfun for sparse matrices.

X = sptenrand([10,10,10],3) %<-- Create some data.
X is a sparse tensor of size 10 x 10 x 10 with 3 nonzeros
	( 2,7,10)    0.3919
	( 6,6, 7)    0.6273
	(10,3, 4)    0.6991
Z = elemfun(X, @sqrt) %<-- Square root of every nonzero.
Z is a sparse tensor of size 10 x 10 x 10 with 3 nonzeros
	( 2,7,10)    0.6260
	( 6,6, 7)    0.7920
	(10,3, 4)    0.8361
Z = elemfun(X, @(x) x+1) %<-- Use a custom function.
Z is a sparse tensor of size 10 x 10 x 10 with 3 nonzeros
	( 2,7,10)    1.3919
	( 6,6, 7)    1.6273
	(10,3, 4)    1.6991
Z = elemfun(X, @(x) x~=0) %<-- Set every nonzero to one.
Z is a sparse tensor of size 10 x 10 x 10 with 3 nonzeros
	( 2,7,10)   1
	( 6,6, 7)   1
	(10,3, 4)   1
Z = ones(X) %<-- An easier way to change every nonzero to one.
Z is a sparse tensor of size 10 x 10 x 10 with 3 nonzeros
	( 2,7,10)     1
	( 6,6, 7)     1
	(10,3, 4)     1

Basic operations (plus, minus, times, etc.) on a sptensor

A = sptensor(tensor(floor(5*rand(2,2,2)))) %<-- Create data.
B = sptensor(tensor(floor(5*rand(2,2,2)))) %<-- Create more data.
A is a sparse tensor of size 2 x 2 x 2 with 8 nonzeros
	(1,1,1)     1
	(2,1,1)     2
	(1,2,1)     3
	(2,2,1)     4
	(1,1,2)     1
	(2,1,2)     2
	(1,2,2)     2
	(2,2,2)     2
B is a sparse tensor of size 2 x 2 x 2 with 7 nonzeros
	(1,1,1)     3
	(2,1,1)     2
	(1,2,1)     3
	(2,2,1)     2
	(2,1,2)     3
	(1,2,2)     4
	(2,2,2)     4
+A %<-- Calls uplus.
ans is a sparse tensor of size 2 x 2 x 2 with 8 nonzeros
	(1,1,1)     1
	(2,1,1)     2
	(1,2,1)     3
	(2,2,1)     4
	(1,1,2)     1
	(2,1,2)     2
	(1,2,2)     2
	(2,2,2)     2
-A %<-- Calls uminus.
ans is a sparse tensor of size 2 x 2 x 2 with 8 nonzeros
	(1,1,1)    -1
	(2,1,1)    -2
	(1,2,1)    -3
	(2,2,1)    -4
	(1,1,2)    -1
	(2,1,2)    -2
	(1,2,2)    -2
	(2,2,2)    -2
A+B %<-- Calls plus.
ans is a sparse tensor of size 2 x 2 x 2 with 8 nonzeros
	(1,1,1)     4
	(1,1,2)     1
	(1,2,1)     6
	(1,2,2)     6
	(2,1,1)     4
	(2,1,2)     5
	(2,2,1)     6
	(2,2,2)     6
A-B %<-- Calls minus.
ans is a sparse tensor of size 2 x 2 x 2 with 6 nonzeros
	(1,1,1)    -2
	(1,1,2)     1
	(1,2,2)    -2
	(2,1,2)    -1
	(2,2,1)     2
	(2,2,2)    -2
A.*B %<-- Calls times.
ans is a sparse tensor of size 2 x 2 x 2 with 7 nonzeros
	(1,1,1)     3
	(1,2,1)     9
	(1,2,2)     8
	(2,1,1)     4
	(2,1,2)     6
	(2,2,1)     8
	(2,2,2)     8
5*A %<-- Calls mtimes.
ans is a sparse tensor of size 2 x 2 x 2 with 8 nonzeros
	(1,1,1)     5
	(1,1,2)     5
	(1,2,1)    15
	(1,2,2)    10
	(2,1,1)    10
	(2,1,2)    10
	(2,2,1)    20
	(2,2,2)    10
A./2 %<-- Calls rdivide.
ans is a sparse tensor of size 2 x 2 x 2 with 8 nonzeros
	(1,1,1)    0.5000
	(1,1,2)    0.5000
	(1,2,1)    1.5000
	(1,2,2)    1.0000
	(2,1,1)    1.0000
	(2,1,2)    1.0000
	(2,2,1)    2.0000
	(2,2,2)    1.0000

Elementwise divsion by another sptensor is allowed, but if the sparsity pattern of the denominator should be a superset of the numerator.

A./(A+B) %<-- Calls rdivide.
ans is a sparse tensor of size 2 x 2 x 2 with 8 nonzeros
	(1,1,1)    0.2500
	(1,1,2)    1.0000
	(1,2,1)    0.5000
	(1,2,2)    0.3333
	(2,1,1)    0.5000
	(2,1,2)    0.4000
	(2,2,1)    0.6667
	(2,2,2)    0.3333
A./B %<-- Uh-oh. Getting a divide by zero.
ans is a sparse tensor of size 2 x 2 x 2 with 8 nonzeros
	(1,1,1)    0.3333
	(1,1,2)       Inf
	(1,2,1)    1.0000
	(1,2,2)    0.5000
	(2,1,1)    1.0000
	(2,1,2)    0.6667
	(2,2,1)    2.0000
	(2,2,2)    0.5000

Use permute to reorder the modes of a sptensor

A = sptenrand([30 40 20 1], 5) %<-- Create data.
A is a sparse tensor of size 30 x 40 x 20 x 1 with 5 nonzeros
	( 4,33, 8,1)    0.7505
	(11,40, 6,1)    0.7400
	(15,23, 2,1)    0.4319
	(20,27,11,1)    0.6343
	(22, 6,20,1)    0.8030
permute(A,[4 3 2 1]) %<-- Reorder the modes.
ans is a sparse tensor of size 1 x 20 x 40 x 30 with 5 nonzeros
	(1, 8,33, 4)    0.7505
	(1, 6,40,11)    0.7400
	(1, 2,23,15)    0.4319
	(1,11,27,20)    0.6343
	(1,20, 6,22)    0.8030

Permute works correctly for a 1-dimensional sptensor.

X = sptenrand(40,4) %<-- Create data.
X is a sparse tensor of size 40 with 4 nonzeros
	( 4)    0.2536
	(25)    0.8735
	(37)    0.5134
	(38)    0.7327
permute(X,1) %<-- Permute.
ans is a sparse tensor of size 40 with 4 nonzeros
	( 4)    0.2536
	(25)    0.8735
	(37)    0.5134
	(38)    0.7327

Displaying a tensor

The function disp handles small and large elements appropriately, as well as aligning the indices.

X = sptensor([1 1 1]); %<-- Create an empty sptensor.
X(1,1,1) = rand(1)*1e15; %<-- Insert a very big element.
X(4,3,2) = rand(1)*1e-15; %<-- Insert a very small element.
X(2,2,2) = rand(1); %<-- Insert a 'normal' element.
disp(X)
ans is a sparse tensor of size 4 x 3 x 2 with 3 nonzeros
   1.0e+14 *
	(1,1,1)    4.2223
	(4,3,2)    0.0000
	(2,2,2)    0.0000