Function Repository Resource:

CPDecomposition

Source Notebook

Compute the canonical polyadic (CP) decomposition of a tensor

Contributed by: Nikolay Murzin

ResourceFunction["CPDecomposition"][tensor]

returns a list of matrix factors decomposing tensor.

ResourceFunction["CPDecomposition"][tensor,rank]

provides a positive integer rank for decomposing tensor.

ResourceFunction["CPDecomposition"][…,property]

returns a property or a list of properties of the decomposition.

ResourceFunction["CPDecomposition"][…,All]

returns an association with all the properties.

Details and Options

The CP (canonical polyadic) decomposition is also known as the CANDECOMP/PARAFAC decomposition.

The CP decomposition expresses a tensor as the sum of rank-1 tensors, which can be useful for dimensionality reduction, compression, and revealing latent structure in data.

Given an input tensor and a desired tensor rank, ResourceFunction["CPDecomposition"] returns a list of factor matrices representing the decomposed tensor.

In ResourceFunction["CPDecomposition"][tensor,rank], if rank, the second dimension of each factor, is set to Automatic, the default rank is heuristically determined as Min[16,Total[dims]-Max[dims]], where dims represents the dimensions of the input tensor.

ResourceFunction["CPDecomposition"] uses the alternating least squares (ALS) algorithm to compute the decomposition.

The ALS algorithm is a randomized algorithm. Due to this, ResourceFunction["CPDecomposition"] may return different results on different evaluations. Use SeedRandom or provide "InitialFactors" for reproducibility.

The argument property can be any of the following:

"Factors"

list of matrix factors decomposing an input tensor

"ReconstructedTensor"

reconstructed tensor

"Error"

total squared error between input and reconstructed tensors

"Iterations"

number of iterations performed

"Rank"

rank of the decompostion

ResourceFunction["CPDecomposition"] takes the following options:

MaxIterations

100

maximum number of iterations for the ALS algorithm

Tolerance

10^-6

tolerance threshold for convergence

"InitialFactors"

Automatic

initial list of factors for the ALS algorithm

In the setting of the "InitialFactors" option, the i^th factor should have dimensions equal to {d_i,rank} with d_i being the tensor’s i^th dimension.

Examples

Basic Examples (1)

Compute the CP decomposition of a random rank-3 tensor:

In[1]:=

Out[1]=

Scope (4)

Return all the properties of the CP decomposition:

In[2]:=

Out[3]=

Return a single property:

In[4]:=

Out[4]=

Specify a different decomposition rank:

In[5]:=

Out[6]=

Increasing the rank reduces the error:

In[7]:=

Out[7]=

Scalars (rank-0 tensors) and vectors (rank-1 tensors) are returned as their own decomposition:

In[8]:=

Out[8]=

In[9]:=

Out[9]=

CP decomposition of a sparse tensor:

In[10]:=

Out[10]=

In[11]:=

Out[11]=

Options (4)

InitialFactors (1)

Providing explicit initial factors for the ALS algorithm will make the decomposition deterministic:

In[12]:=

In[13]:=

In[14]:=

Out[14]=

MaxIterations (1)

Increasing MaxIterations can further reduce the error, at the cost of longer evaluation times:

In[15]:=

In[16]:=

Out[7]=

In[17]:=

Out[18]=

Tolerance (2)

Increasing the error tolerance will result in faster convergence:

In[19]:=

In[20]:=

$SeedRandom[1234]; ResourceFunction["CPDecomposition"][tensor, {"Error", "Iterations"}, Tolerance -> 10^(-3)]$

Out[7]=

Decreasing the error tolerance may reduce error:

In[21]:=

$SeedRandom[1234]; ResourceFunction["CPDecomposition"][tensor, {"Error", "Iterations"}, Tolerance -> 10^(-6)]$

Out[22]=

Applications (4)

A 3D test image:

In[23]:=

Out[23]=

Compute the CP decomposition of the image (this might take a long time to evaluate):

In[24]:=

Out[24]=

The CP decomposition is able to compress the data in the image:

In[25]:=

Out[25]=

In[26]:=

Out[26]=

Show the reconstructed tensor as an image:

In[27]:=

Out[27]=

Properties and Relations (2)

Given the CP decomposition factors:

In[28]:=

dimensions = {2, 3, 4};
tensor = RandomReal[{-1, 1}, dimensions];
{factors, rt, error} = ResourceFunction["CPDecomposition"][
tensor, {"Factors", "ReconstructedTensor", "Error"}]

Out[29]=

One can reconstruct a tensor using the ResourceFunction KhatriRaoProduct along with Total and ArrayReshape with initial tensor dimensions:

In[30]:=

Out[30]=

The error can be computed using SquaredEuclideanDistance with the flattened original and reconstructed tensors:

In[31]:=

Out[31]=

For a matrix, CPDecomposition returns two factor matrices a and b, with the original matrix reconstructed as a.Transpose[b]:

In[32]:=

In[33]:=

In[34]:=

Out[34]=

Version History

1.0.0 – 05 April 2023

Source Metadata

Citation:
- Carroll J.D., Chang J.J., "Analysis of individual differences in multidimensional scaling via an n-way generalization of 'Eckart-Young' decomposition." Psychometrika, vol. 35, no. 3, 283–319, 1970.
  DOI: 10.1007/BF02310791
- Harshman R.A., "Determination and proof of minimum uniqueness conditions for PARAFAC1." UCLA Working Papers in Phonetics, vol. 22, 111–117, 1972.
  Available from https://www.psychology.uwo.ca/faculty/harshman/wpppfac1.pdf
- Kolda T.G., Bader B.W., "Tensor Decompositions and Applications." SIAM Review, vol. 51, no. 3, 455–500, 2009.
  DOI: 10.1109/TCS.1977.1084319

Related Resources

License Information

This work is licensed under a Creative Commons Attribution 4.0 International License

Wolfram Function Repository

CPDecomposition

Details and Options