Mathematical Culture and Thought

Mathematical Culture and Thought

Tensor Rank and the Best Low-rank Approximation Problem

Document Type : Review

Authors
Z. Ordolalo 1
E. Golpar Raboky 1
N. Mahdavi-Amiri 2
1 Department of Mathematics, University of Qom, Iran
2 Department of Mathematical Sciences, Sharif University of Technology, Iran
10.30504/mct.2022.323
Abstract
The rank of a matrix is indeed an important characteristic, and it can be calculated using methods such as Gaussian elimination or stepwise decomposition. The rank of a tensor  A, on the other hand, is more complex to calculate and is considered an NP-hard problem except in special cases. Various methods have been proposed for computing the rank of 2x2x2 tensors, including the calculation of hyperdeterminant, checking the internal structure of the tensor, and classifying the tensor into canonical forms. The Eckart-Young theorem provides a method for calculating the best low-rank approximation for matrices. However, many tensors may not have a specified low-rank approximation, which is a degenerate problem. These tensors can be approximated by a sequence of low-rank tensors.
Keywords
numerical multilinear algebra
tensor
tensor rank
tensor decomposition
low-rank approximation
Subjects

 

 

[1] Cichocki, A., Zdunek, R. L. , Phan, A. H., Amari, S., Nonnegative Matrix and Tensor Factorizations:
Applications to Exploratory Multi-way Data Analysis and Blind Source Separation,
John Wiley and Sons, London, 2009.
[2] Golub, G. H., Van Loan, C. F., Matrix Computations, Johns Hopkins University Press, Baltimore,
2013.
[3] Hitchock, F. l., The expression of tensor or a polyadic as a sum of products, J. Math. Phys., 6
(1927), 164-189.
[4] Kolda, T. G., Bader, B. W., Tensor decompositions and applications, SIAM Rev., 51 (2009),
455-500.
[5] Kruskal, J. B., Rank, decomposition and uniqueness for 3-way andN-way arrays, in Multiway
Data Analysis, North-Holland Publishing Co., Amsterdam, 1989, 7-18.
[6] Landsberg, J. M. , The border rank of the multiplication of 2  2 matrices is seven, J. Amer.
Math. Soc., 19 (2006), 447-459.
[7] Lim, L. H., Tensors and Hyprematrices, in Handbook of Linear Algebra, 2nd ed., L. Hogben,
ed., CRC Press, Boca Raton, FL, 2013.
[8] Rovi, A., Analysis of 2  2  2 Tensors, Master’s thesis, Linköping University, 2010.
[9] Silva, V. D., Lim, L. H., Tensor rank and the ill-posedness of the best low-rank approximation
problem, SIAM J. Matrix Anal., 30 (2008), 1084-1127.
[10] Ten Berge, J. M. F., Kruskal’s polynomial for 222 arrays and a generalization to 2nn
arrays, Psychometrika, 56 (1991), 631-636.

  • Receive Date 19 December 2017
  • Revise Date 21 April 2018
  • Accept Date 22 April 2018
  • Publish Date 20 February 2022