Tensor Rank Visualization¶

Martin J. Mohlenkamp

Introduction¶

Since the notation and terminology are inconsistent in the literature, we first have to define what we are talking about. A tensor is an object with some number of indices that yields a real or complex number. We denote it

The dimension of the tensor is the number of indices. Thus an ordinary vector is a tensor in dimension one, and an ordinary matrix is a tensor in dimension two. Each index has some range of allowed values. The resolution in an index is the number of allowed values, so

For simplicity we will often assume the resolution is the same in all indices and denote it .

A tensor in dimension with resolution contains numbers. For even moderate and this is an astronomical number, and there is no way to directly store, compute, or manipulate such a tensor. This effect is known as the Curse of Dimensionality [BELLMA1961].

A separable tensor is one that can be written as a product

To write without explicitly listing its indices, we use the tensor product

A tensor can be expressed with separation rank if it can be written

or equivalently

where the superscript in is an index rather than a power. Such a tensor can be stored using only numbers instead of . Any tensor can be written in this form with , but only when is small is this representation useful.

Given a tensor with separation rank , it may or may not be possible to express it with smaller . There are several examples where tensors have been written or approximated with much smaller than expected (see e.g. [BEY-MOH2005] [MOH-MON2005] ). In each of these examples a proof can be given, but there is no apparent connection between the proofs. Overall, there is very little understanding of why approximations with small seem to be effective. Our understanding is hampered by the following:

• The set of tensors with separation rank at most is not a subspace, since in general the sum of two such tensors has separation rank . Thus this set is not flat, but instead has nontrivial geometry and topology.
• The smallest interesting example is , which has 8 entries and so would need to be plotted in .

The goal of this work is to provide a way to visually explore the set of tensors with a given . We hope that this exploration will yield unexpected structure and inspire better understanding of such tensors. This understanding may then lead to proofs on why approximations with small are unexpectedly effective.

See [KOL-BAD2009] for a general review of tensor decompositions.

Visualization Theory¶

In these sections we describe how one can visualize a set of tensors in a canonical fashion, and some practical issues that arise.

Examples¶

In these sections we explore some particular examples and show the visualizations produced.

The case gives interesting holes that the and cases lack. Based on table 1 in [C-B-L-C2009], this was to be expected since the case has two typical ranks and the others do not. Other known cases with more than one typical rank are

• with ranks 3 and 4
• with ranks 4 and 5
• with ranks 5 and 6
• with ranks 5 and 6
• with ranks 8 and 9
• with ranks 12 and 13

In some other cases, the smallest typical rank is known, but it is unknown if it is the only typical rank. For example, for tensors the typical rank is either just 6 or is 6 and 7.

In this section we explain what the software does to produce the visualizations and how to use it.

Acknowledgments¶

This material is based upon work supported by the National Science Foundation under Grant DMS-0545895.

I would like to thank Sruthi Devarachetty, Nam Nguyen, Krishna Chaitanya Palavarpu, and Robert Vanyo, who were research assistants on this project while students at Ohio University.

I would also like to thank Shmuel Friedland, Lek-Heng Lim, Fernando Perez, Alwin Stegeman, and Jos ten Berge for their comments, corrections, and suggestions.

Bibliography¶

 [BELLMA1961] Richard Bellman, Adaptive Control Processes: a Guided Tour Princeton Univ. Press, Princeton, New Jersey, 1961.
 [BEY-MOH2005] G. Beylkin and M.J. Mohlenkamp, Algorithms for numerical analysis in high dimensions, SIAM J. Sci. Comput., 26 (2005), pp.2133-2159.
 [BRE-HU2013] Bremner, Murray R. and Hu, Jiaxiong, On Kruskal’s theorem that every 3x3x3 array has rank at most 5 Linear Algebra Appl. 439(2)401-421, 2013. doi:10.1016/j.laa.2013.03.021
 [C-B-L-C2009] Comon, P.; ten Berge, J. M. F.; De Lathauwer, L.; and Castaing, J., Generic and typical ranks of multi-way arrays, Linear Algebra Appl., 430: pp.2997-3007, 2009. doi:10.1016/j.laa.2009.01.014
 [DES-LIM2008] Vin De Silva and Lek-Heng Lim, Tensor Rank and The Ill-posedness of The Best Low-Rank Approximation Problem, SIAM Journal on Matrix Analysis and Applications, Volume 30, Issue 3, September 2008.
 [FRI-MEH] S. Friedland and V. Mehrmann, Best Subspace Tensor Approximations, http://arxiv.org/abs/0805.4220
 [KOL-BAD2009] Tamara G. Kolda and Brett W. Bader Tensor Decompositions and Applications SIAM Review 51(3)455-500, 2009
 [KRUSKA1989] J. B. Kruskal, Rank, decomposition, and uniqueness for 3-way and N -way arrays, in Multiway Data Analysis, R. Coppi and S. Bolasco, eds., North-Holland, Amsterdam, 1989, pp. 7-18.
 [MOH-MON2005] M.J. Mohlenkamp and L. Monzon, Trigonometric identities and sums of separable functions, The Mathematical Intelligencer, 27 (2005), pp.65–69. http://www.ohio.edu/people/mohlenka/research/sine.pdf