Tensor Spaces and Numerical Tensor Calculus

Preface......Page 7
Contents......Page 9
About the Author......Page 19
 Symbols......Page 20
 Greek Letters......Page 22
 Latin Letters......Page 23
 Abbreviations and Algorithms......Page 27
Part I: Algebraic Tensors......Page 28
   1.1.1 Tensor Product of Vectors......Page 30
   1.1.2 Tensor Product of Matrices, Kronecker Product......Page 32
   1.1.3 Tensor Product of Functions......Page 34
   1.2.1 Tensors as Coefficients......Page 35
   1.2.2 Tensor Decomposition for Inverse Problems......Page 36
   1.2.4 Large-Sized Tensors in Analysis Applications......Page 37
  1.3 Tensor Calculus......Page 40
   1.4.1 Part I: Algebraic Properties......Page 41
   1.4.2 Part II: Functional Analysis of Tensors......Page 42
   1.4.3 Part III: Numerical Treatment......Page 43
   1.4.4 Topics Outside the Scope of the Monograph......Page 44
  1.6 Comments about the Early History of Tensors......Page 45
  1.7 Notations......Page 46
  2.1 Matrix Notations......Page 49
  2.2 Matrix Rank......Page 51
  2.3 Matrix Norms......Page 53
  2.4 Semidefinite Matrices......Page 55
   2.5.1 Cholesky Decomposition......Page 56
   2.5.2 QR Decomposition......Page 57
   2.5.3 Singular-Value Decomposition......Page 59
  2.6 Low-Rank Approximation......Page 65
  2.7 Linear Algebra Procedures......Page 67
  2.8 Dominant Columns......Page 70
   3.1.1 Basic Facts......Page 74
   3.1.2 Free Vector Space over a Set......Page 75
   3.1.3 Quotient Vector Space......Page 77
   3.1.4 (Multi-)Linear Maps, Algebraic Dual, Basis Transformation......Page 78
   3.2.1 Constructive Definition......Page 79
   3.2.2 Characteristic Properties......Page 81
   3.2.3 Isomorphism to Matrices for d = 2......Page 83
   3.2.4 Tensors of Order d > 3......Page 85
   3.2.5 Different Types of Isomorphisms......Page 88
   3.2.6 Rr and Tensor Rank......Page 90
   3.3.1 Definition on the Set of Elementary Tensors......Page 101
   3.3.2 Embeddings......Page 102
  3.4 Tensor Spaces with Algebra Structure......Page 110
   3.5.1 Basic Definitions......Page 113
   3.5.2 Quantics......Page 116
   3.5.3 Determinants......Page 117
   3.5.4 Application of Functionals......Page 118
Part II: Functional Analysis of Tensor Spaces......Page 120
   4.1.1 Norms......Page 122
   4.1.2 Basic Facts about Banach Spaces......Page 123
   4.1.3 Examples......Page 125
   4.1.4 Operators......Page 126
   4.1.5 Dual Spaces......Page 129
   4.1.7 Weak Convergence......Page 131
   4.2.1 Notations......Page 133
   4.2.2 Continuity of the Tensor Product, Crossnorms......Page 135
   4.2.3 Projective Norm ||.||^(V;W)......Page 141
   4.2.4 Duals and Injective Norm ||.|| (V;W)......Page 145
   4.2.5 Embedding of V* into L(V W;W)......Page 152
   4.2.6 Reasonable Crossnorms......Page 153
   4.2.7 Reflexivity......Page 157
   4.2.8 Uniform Crossnorms......Page 158
   4.2.9 Nuclear and Compact Operators......Page 161
   4.3.1 Continuity, Crossnorms......Page 162
   4.3.2 Recursive Definition of the Topological Tensor Space......Page 165
   4.3.3 Proofs......Page 168
   4.3.4 Embedding into Embedding into L(V; Vj) and L(V;V)......Page 172
   4.3.5 Intersections of Banach Tensor Spaces......Page 176
   4.3.6 Tensor Space of Operators......Page 179
   4.4.2 Basic Facts about Hilbert Spaces......Page 180
   4.4.3 Operators on Hilbert Spaces......Page 182
   4.4.4 Orthogonal Projections......Page 184
   4.5.1 Induced Scalar Product......Page 186
   4.5.2 Crossnorms......Page 188
   4.5.3 Tensor Products of L(Vj ; Vj)......Page 189
   4.5.4 Gagliardo–Nirenberg Inequality......Page 190
   4.5.5 Partial Scalar Products......Page 195
   4.6.1 Vector Operations......Page 196
   4.6.3 Matrix-Matrix Operations......Page 197
   4.6.5 Convolution......Page 199
   4.6.6 Function of a Matrix......Page 201
   4.7.1 Hilbert Structure......Page 204
   4.7.2 Banach Spaces and Dual Spaces......Page 205
   5.1.1 Tensors as Vectors......Page 207
   5.1.2 Kronecker Tensors......Page 209
   5.2.1 General Case......Page 211
   5.2.2 Finite-Dimensional Case......Page 213
   5.2.3 Hilbert Structure......Page 218
  5.3 Tensorisation......Page 222
  6.1 Statement of the Problem, Notations......Page 225
   6.2.1 Existence of Minimal Subspaces......Page 226
   6.2.2 Use of the Singular-Value Decomposition......Page 229
   6.2.3 Minimal Subspaces for a Family of Tensors......Page 230
  6.3 Minimal Subspaces of Tensors of Higher Order......Page 231
  6.4 Hierarchies of Minimal Subspaces and......Page 234
  6.5 Sequences of Minimal Subspaces......Page 237
   6.6.2 First Approach......Page 242
   6.6.3 Second Approach......Page 245
   6.7.1 Algebraic Tensor Space......Page 248
   6.7.2 Topological Tensor Space......Page 249
  6.8 Linear Constraints and Regularity Properties......Page 250
  6.9 Minimal Subspaces for (Anti-)Symmetric Tensors......Page 253
Part III: Numerical Treatment......Page 254
 Chapter 7: r-Term Representation......Page 256
   7.1.1 Concept......Page 257
   7.1.2 Computational and Memory Cost......Page 258
   7.1.3 Tensor Representation versus Tensor Decomposition......Page 259
  7.2 Full and Sparse Representation......Page 260
  7.3 r-Term Representation......Page 261
   7.4.1 Tangent Space......Page 264
   7.4.2 Sensitivity......Page 265
  7.5 Representation of Vj......Page 267
   7.6.1 From Full Representation into r-Term Format......Page 270
   7.6.3 From r-Term into N-Term Format for r>N......Page 271
   7.6.4 Sparse-Grid Approach......Page 272
   7.6.5 From Sparse Format into......Page 274
  7.7 Representation of (Anti-)Symmetric Tensors......Page 276
   7.7.2 Indirect Representation......Page 277
  7.8 Modifications......Page 279
  8.1 The Set Tr......Page 280
   8.2.1 General Frame or Basis......Page 284
   8.2.2 Transformations......Page 287
   8.2.3 Tensors in KI......Page 288
   8.2.4 Orthonormal Basis......Page 289
   8.2.5 Summary of the Formats......Page 293
   8.2.6 Hybrid Format......Page 294
   8.3.1 Definitions......Page 296
   8.3.2 Examples......Page 298
   8.3.3 Computation and Computational Cost......Page 300
   8.4.1 Uniqueness......Page 306
   8.4.2 Tangent Space......Page 307
   8.4.3 Sensitivity......Page 308
   8.5.2 Conversion from Rr to Tr......Page 310
   8.5.3 Conversion from Tr to Rr......Page 314
   8.5.4 A Comparison of Both Representations......Page 315
   8.6.1 Trivial Joining of Frames......Page 316
   8.6.2 Common Bases......Page 317
  9.1 Approximation of a Tensor......Page 319
  9.2 Discussion for r = 1......Page 321
  9.3 Discussion in the Matrix Case d = 2......Page 323
   9.4.1 Nonclosedness of Rr......Page 325
   9.4.2 Border Rank......Page 326
   9.4.3 Stable and Unstable Sequences......Page 328
   9.4.4 A Greedy Algorithm......Page 330
   9.5.1 Definitions......Page 331
   9.5.2 Nonclosed Formats......Page 333
   9.5.4 General Case......Page 334
   9.5.5 On the Strength of Divergence......Page 335
   9.5.6 Uniform Strength of Divergence......Page 336
   9.5.7 Extension to Vector Spaces of Larger Dimension......Page 339
   9.6.1 Use of the Hybrid Format......Page 340
   9.6.2 Alternating Least-Squares Method......Page 342
   9.6.3 Stabilised Approximation Problem......Page 351
   9.6.4 Newton’s Approach......Page 352
  9.7 Generalisations......Page 354
  9.8 Analytical Approaches for the r-Term Approximation......Page 355
   9.8.1 Quadrature......Page 356
   9.8.2 Approximation by Exponential Sums......Page 357
   9.8.3 Sparse Grids......Page 368
  10.1 Truncation to Tr......Page 369
   10.1.1 HOSVD Projection......Page 370
   10.1.2 Successive HOSVD Projection......Page 372
   10.1.3 Examples......Page 374
   10.1.4 Other Truncations......Page 376
   10.1.5 L Estimate of the Truncation Error......Page 377
   10.2.1 General Setting......Page 380
   10.2.2 Approximation with Fixed Format......Page 381
   10.2.3 Properties......Page 383
   10.3.1 Algorithm......Page 384
   10.3.2 ALS for Different Formats......Page 386
   10.3.3 Approximation with Fixed Accuracy......Page 389
   10.4.1 Linear Interpolation Techniques......Page 391
   10.4.2 Polynomial Approximation......Page 394
   10.4.3 Polynomial Interpolation......Page 396
   10.4.4 Sinc Approximations......Page 398
  10.5 Simultaneous Approximation......Page 405
  10.6 Resume......Page 407
   11.1.1 Hierarchical Structure......Page 408
   11.1.2 Properties......Page 411
   11.1.3 Historical Comments......Page 412
   11.2.1 Dimension Partition Tree......Page 413
   11.2.2 Algebraic Characterisation, Hierarchical Subspace Family......Page 415
   11.2.3 Minimal Subspaces......Page 416
   11.2.4 Conversions......Page 419
   11.3.1 Hierarchical Basis Representation......Page 421
   11.3.2 Orthonormal Bases......Page 431
   11.3.3 HOSVD Bases......Page 436
   11.3.5 Sensitivity......Page 443
   11.3.6 Conversion from Rr to Hr Revisited......Page 450
   11.4.1 Best Approximation in Hr......Page 452
   11.4.2 HOSVD Truncation to Hr......Page 454
   11.5.1 Setting of the Problem......Page 467
   11.5.3 Common Bases......Page 468
  12.1 Basic TT Representation......Page 473
   12.3.1 Related Subspaces......Page 476
   12.3.2 From Subspaces to TT Coefficients......Page 477
   12.3.3 From Hierarchical Format to TT Format......Page 478
   12.3.5 Extended TT Representation......Page 480
   12.3.6 Properties......Page 481
   12.3.7 HOSVD Bases and Truncation......Page 482
   12.4.2 Conversion from Tp to Hr with a General Tree......Page 483
   12.4.3 Conversion from Hr to Tp......Page 485
   12.5.1 Cyclic Matrix Product Representation......Page 487
   12.5.2 Site-Independent Representation......Page 490
   12.5.3 Tensor Network......Page 491
  12.6 Representation of Symmetric and Antisymmetric Tensors......Page 492
 Chapter 13: Tensor Operations......Page 493
   13.1.1 Full Representation......Page 494
   13.1.3 Tensor Subspace Representation......Page 495
  13.2 Entry-wise Evaluation......Page 497
   13.2.2 Tensor Subspace Representation......Page 498
   13.2.3 Hierarchical Representation......Page 499
  13.3 Scalar Product......Page 500
   13.3.2 r-Term Representation......Page 501
   13.3.3 Tensor Subspace Representation......Page 502
   13.3.4 Hybrid Format......Page 504
   13.3.5 Hierarchical Representation......Page 505
   13.3.6 Orthonormalisation......Page 509
   13.4.2 Hybrid r-Term Representation......Page 510
   13.4.4 Hierarchical Representation......Page 511
  13.5 General Binary Operation......Page 512
   13.5.2 Tensor Subspace Representation......Page 513
   13.5.3 Hierarchical Representation......Page 514
  13.6 Hadamard Product of Tensors......Page 515
  13.8 Matrix-Matrix Multiplication......Page 516
  13.9 Matrix-Vector Multiplication......Page 517
   13.9.2 Separable Form (13.25a)......Page 518
   13.9.3 Elementary Kronecker Tensor (13.25b)......Page 519
   13.9.4 Matrix in p-Term Format (13.25c)......Page 520
  13.10 Functions of Tensors, Fixed-Point Iterations......Page 521
  13.11 Example: Operations in Quantum Chemistry Applications......Page 523
   14.1.1 Notations, Choice for TD......Page 526
   14.1.2 Format Htens......Page 528
   14.1.3 Operations with Tensorised Vectors......Page 529
   14.1.4 Application to Representations by Other Formats......Page 531
   14.1.5 Matricisation......Page 532
   14.1.6 Generalisation to Matrices......Page 533
   14.2.1 Grid Functions......Page 534
   14.2.3 Polynomials......Page 535
   14.2.5 Local Grid Refinement......Page 539
   14.3.1 Notation......Page 540
   14.3.2 Separable Operations......Page 542
   14.3.3 Tensor Algebra A(l0)......Page 543
   14.3.4 Algorithm......Page 550
   14.4.1 FFT for Cn Vectors......Page 553
   14.4.2 FFT for Tensorised Vectors......Page 554
   14.5.1 Isomorphism Fn......Page 556
   14.5.2 Scalar Products......Page 557
   14.5.4 Continuous Functions......Page 558
  15.1 Approximation of General Tensors......Page 560
   15.1.1 Approximation of Multivariate Functions......Page 561
   15.1.2 Multiparametric Boundary-Value Problem and PDE with Stochastic Coefficients......Page 562
   15.1.3 Function of a Tensor......Page 564
  15.2 Notations......Page 565
  15.3 Properties in the Matrix Case......Page 567
   15.4.1 Matricisation......Page 570
   15.4.2 Nestedness......Page 572
   15.4.3 Algorithm......Page 574
  16.1 General Discretisation Strategy......Page 578
  16.2 Solution of Elliptic Boundary-Value Problems......Page 579
   16.2.2 Discretisation......Page 580
   16.2.3 Solution of the Linear System......Page 582
   16.2.4 Accuracy Controlled Solution......Page 584
   16.3.1 Regularity of Eigensolutions......Page 585
   16.3.2 Iterative Computation......Page 587
  16.4 On Other Types of PDEs......Page 588
   17.1.1 Algorithm......Page 589
   17.1.2 Convergence......Page 590
  17.2 Solution of Optimisation Problems Involving Tensor Formats......Page 591
   17.2.1 Formulation of the Problem......Page 592
   17.2.2 Reformulation, Derivatives, and Iterative Treatment......Page 593
   17.3.2 Dirac–Frenkel Discretisation......Page 594
   17.3.3 Tensor Subspace Format Tr......Page 595
   17.3.4 Hierarchical Format Hr......Page 597
   17.4.1 Definitions......Page 599
   17.4.2 Properties......Page 600
   17.4.4 Symmetric Tensors......Page 602
References......Page 603
Index......Page 616