Tensor rank and the ill-posedness of the best low-rank approximation problem

Details Tensor rank and the ill-posedness of the best low-rank approximation problem Tensor rank and the ill-posedness of the best low-rank approximation problem

2006-07-26

arxiv.org/abs/math/0607647v2

Mathematics

Numerical Analysis

To appear in the SIAM Journal on Matrix Analysis and Applications. Includes another 7 pages of additional materials not in the

Scientific paper

There has been continued interest in seeking a theorem describing optimal low-rank approximations to tensors of order 3 or higher, that parallels the Eckart-Young theorem for matrices. In this paper, we argue that the naive approach to this problem is doomed to failure because, unlike matrices, tensors of order 3 or higher can fail to have best rank-r approximations. The phenomenon is much more widespread than one might suspect: examples of this failure can be constructed over a wide range of dimensions, orders and ranks, regardless of the choice of norm (or even Bregman divergence). Moreover, we show that in many instances these counterexamples have positive volume: they cannot be regarded as isolated phenomena. In one extreme case, we exhibit a tensor space in which no rank-3 tensor has an optimal rank-2 approximation. The notable exceptions to this misbehavior are rank-1 tensors and order-2 tensors. In a more positive spirit, we propose a natural way of overcoming the ill-posedness of the low-rank approximation problem, by using weak solutions when true solutions do not exist. In our work we emphasize the importance of closely studying concrete low-dimensional examples as a first step towards more general results. To this end, we present a detailed analysis of equivalence classes of 2-by-2-by-2 tensors, and we develop methods for extending results upwards to higher orders and dimensions. Finally, we link our work to existing studies of tensors from an algebraic geometric point of view. The rank of a tensor can in theory be given a semialgebraic description; i.e., can be determined by a system of polynomial inequalities. In particular we make extensive use of the 2-by-2-by-2 hyperdeterminant.

Affiliated with

Also associated with

No associations

Rating

Tensor rank and the ill-posedness of the best low-rank approximation problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tensor rank and the ill-posedness of the best low-rank approximation problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tensor rank and the ill-posedness of the best low-rank approximation problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-478514