Copyright (c) 2009, 2013 Martin J. Mohlenkamp. This documentation is distributed under the GNU Free Documentation License.
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 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.
In these sections we describe how one can visualize a set of tensors in a canonical fashion, and some practical issues that arise.
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
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.
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.
[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.ohiouniversityfaculty.com/mohlenka/research/sine.pdf |