Theory and Computation of Tensors: Multi-Dimensional Arrays

By Yimin Wei and Weiyang Ding

Theory and Computation of Tensors: Multi-Dimensional Arrays investigates theories and computations of tensors to broaden perspectives on matrices. Data in the Big Data Era is not only growing larger but also becoming much more complicated. Tensors (multi-dimensional arrays) arise naturally from many engineering or scientific disciplines because they can represent multi-relational data or nonlinear relationships.

• Provides an introduction of recent results about tensors
• Investigates theories and computations of tensors to broaden perspectives on matrices
• Discusses how to extend numerical linear algebra to numerical multi-linear algebra
• Offers examples of how researchers and students can engage in research and the applications of tensors and multi-dimensional arrays

• Language: English
• Publisher: Academic Press
• Release date: Aug 28, 2016
• ISBN: 9780128039809

Yimin Wei

Yimin Wei is a Professor at the School of Mathematical Sciences, Fudan University, Shanghai, P.R. of China. He has has published three English books and over 100 research papers in international journals. His studies on tensors are supported by the National Natural Science Foundation of China.

Book preview

Theory and Computation of Tensors

Multi-Dimensional Arrays

Weiyang Ding

Yimin Wei

Table of Contents

Cover image

Title page

Copyright

Preface

I: General Theory

Chapter 1: Introduction and Preliminaries

Abstract

1.1 What Are Tensors?

1.2 Basic Operations

1.3 Tensor Decompositions

1.4 Tensor Eigenvalue Problems

Chapter 2: Generalized Tensor Eigenvalue Problems

Abstract

2.1 A Unified Framework

2.2 Basic Definitions

2.3 Several Basic Properties

2.4 Real Tensor Pairs

2.5 Sign-Complex Spectral Radius

2.6 An Illustrative Example

II: Hankel Tensors

Chapter 3: Fast Tensor-Vector Products

Abstract

3.1 Hankel Tensors

3.2 Exponential Data Fitting

3.3 Anti-Circulant Tensors

3.4 Fast Hankel Tensor-Vector Product

3.5 Numerical Examples

Chapter 4: Inheritance Properties

Abstract

4.1 Inheritance Properties

4.2 The First Inheritance Property of Hankel Tensors

4.3 The Second Inheritance Property of Hankel Tensors

4.4 The Third Inheritance Property of Hankel Tensors

III: M-Tensors

Chapter 5: Definitions and Basic Properties

Abstract

5.1 Preliminaries

5.2 Spectral Properties of M-Tensors

5.3 Semi-Positivity

5.4 Monotonicity

5.5 An Extension of M-Tensors

5.6 Summation

Chapter 6: Multilinear Systems with M-Tensors

Abstract

6.1 Motivations

6.2 Triangular Equations

6.3 M-Equations and Beyond

6.4 Iterative Methods for M-Equations

6.5 Perturbation Analysis of M-Equations

6.6 Inverse Iteration

Appendix

Bibliography

Subject Index

Copyright

Academic Press is an imprint of Elsevier

125 London Wall, London EC2Y 5AS, UK

525 B Street, Suite 1800, San Diego, CA 92101-4495, USA

50 Hampshire Street, 5th Floor, Cambridge, MA 02139, USA

The Boulevard, Langford Lane, Kidlington, Oxford OX5 1GB, UK

Copyright © 2016 Elsevier Ltd. All rights reserved.

No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or any information storage and retrieval system, without permission in writing from the publisher. Details on how to seek permission, further information about the Publisher’s permissions policies and our arrangements with organizations such as the Copyright Clearance Center and the Copyright Licensing Agency, can be found at our website: www.elsevier.com/permissions.

This book and the individual contributions contained in it are protected under copyright by the Publisher (other than as may be noted herein).

Notices

Knowledge and best practice in this field are constantly changing. As new research and experience broaden our understanding, changes in research methods, professional practices, or medical treatment may become necessary.

Practitioners and researchers must always rely on their own experience and knowledge in evaluating and using any information, methods, compounds, or experiments described herein. In using such information or methods they should be mindful of their own safety and the safety of others, including parties for whom they have a professional responsibility.

To the fullest extent of the law, neither the Publisher nor the authors, contributors, or editors, assume any liability for any injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods, products, instructions, or ideas contained in the material herein.

Library of Congress Cataloging-in-Publication Data

A catalog record for this book is available from the Library of Congress

British Library Cataloguing-in-Publication Data

A catalogue record for this book is available from the British Library

ISBN 978-0-12-803953-3 (print)

ISBN 978-0-12-803980-9 (online)

For information on all Academic Press publications visit our website at https://www.elsevier.com/

Publisher: Glyn Jones

Acquisition Editor: Glyn Jones

Editorial Project Manager: Anna Valutkevich

Production Project Manager: Debasish Ghosh

Designer: Nikki Levy

Typeset by SPi Global, India

Preface

-tensors. Both theoretical analyses and computational aspects are discussed.

We begin with the generalized tensor eigenvalue problems, which are regarded as a unified framework of different kinds of tensor eigenvalue problems arising from applications. We focus on the perturbation theory and the error analysis of regular tensor pairs. Employing various techniques, we extend several classical results from matrices or matrix pairs to tensor pairs, such as the Gershgorin circle theorem, the Collatz-Wielandt formula, the Bauer-Fike theorem, the Rayleigh-Ritz theorem, backward error analysis, the componentwise distance of a nonsingular tensor to singularity, etc.

. Next, we investigate the spectral inheritance properties of Hankel tensors by applying the convolution formula of the fast algorithm and an augmented Vandermonde decomposition of strong Hankel tensors. We prove that if a lower-order Hankel tensor is positive semidefinite, then a higher-order Hankel tensor with the same generating vector has no negative H-eigenvalues, when (i) the lower order is 2, or (ii) the lower order is even and the higher order is its multiple.

-tensors. We attempt to extend the equivalent definitions of nonsingular M-equations with positive right-hand sides, and also propose several iterative methods for computing the positive solutions.

We would like to thank our collaborator Prof. Liqun Qi of the Hong Kong Polytechnic University, who leaded us to the research of tensor spectral theory and always encourages us to explore the topic. We would also like to thank Prof. Eric King-wah Chu of Monash University and Prof. Sanzheng Qiao of McMaster University, who read this book carefully and provided feedback during the writing process.

This work was supported by the National Natural Science Foundation of China under Grant 11271084, School of Mathematical Sciences and Key Laboratory of Mathematics for Nonlinear Sciences, Fudan University.

I

General Theory

Chapter 1

Introduction and Preliminaries

Abstract

We first introduce the concepts and sources of tensors in this chapter. Several essential and frequently used operations involving tensors are also included. Furthermore, two basic topics, tensor decompositions and tensor eigenvalue problems, are briefly discussed at the end of this chapter.

Keywords

Decompositions; Eigenvalue Problems; Generalized tensor eigenvalue problem; Higher-order singular value decomposition (HOSVD); Modal tensor-matrix multiplication; Modal unfolding; Operations; Tensor Decompositions; Tensors

We first introduce the concepts and sources of tensors in this chapter. Several essential and frequently used operations involving tensors are also included. Furthermore, two basic topics, tensor decompositions and tensor eigenvalue problems, are briefly discussed at the end of this chapter.

1.1 What Are Tensors?

The term tensor or hypermatrix in this book refers to a multiway array. The number of the dimensions of a tensor is called its orderis an mth-order tensor. Particularly, a scalar is a 0th-order tensor, a vector is a 1st-order tensor, and a matrix is a 2nd-order tensor. As other mathematical concepts, tensor or hypermatrix is abstracted from real-world phenomena and other scientific theories. Where do the tensors arise? What kinds of properties do we care most? How many different types of tensors do we have? We will briefly answer these questions employing several illustrative examples in this section.

Example 1.1

of size 4 × 3 × 2 whose (i, j, k) entry sijk denotes the score of the i-th student on the j-th subjects in the k-th exam. This representation is natural and easily understood, thus it is a convenient data structure for construction and query. However, when we need to print the information on a piece of paper, the 3D structure is apparently not suitable for 2D visualization. Thus we need to unfold the cubic tensor into a matrix. The following two different unfoldings of the same tensor both include all the information in the original complex table. We can see from the two tables that their entries are the same up to a permutation. Actually, there are many different ways to unfold a higher-order tensor into a matrix, and the linkages between them are permutations of indices.

Example 1.2

to store an RGB image, whose (i, j, k) entry denotes the value of the k-th channel in the (i, j) position. (kstores the t-th frame of the video as a color image.

Table 1.1

The first way to print .

Table 1.2

The second way to print .

Example 1.3

can be rewritten into p1(x) = x c, where the vector c = (c1, c2, … , cn, that is, a quadratic form, can be simplified into p2(x) = x Cx, where the matrix C = (cij). By analogy, if we denote an mand apply a notation, which will be introduced in the next section, then the degree-m homogeneous polynomial

can be rewritten as

Moreover, x ccan stand for an degree-m . We shall see in Section 1.2 that the normal vector at a point x.

Example 1.4

The Taylor expansion is a well-known mathematical tool. The Taylor series of a real or complex-valued function f(x) that is infinitely differentiable at a real or complex number a is the power series

A multivariate function f(x1, x2, … , xn) that is infinitely differentiable at a point (a1, a2, … , an) also has its Taylor expansion

which is