Numerical stability and tensor nuclear norm
From MaRDI portal
Publication:6153359
Abstract: We present a notion of bilinear stability, which is to numerical stability what bilinear complexity is to time complexity. In bilinear complexity, an algorithm for evaluating a bilinear operator is a decomposition ; the number of terms captures the speed of the algorithm; and its smallest possible value, i.e., the tensor rank of , quantifies the speed of a fastest algorithm. Bilinear stability introduces norms to the mix: The growth factor of the algorithm captures the accuracy of the algorithm; and its smallest possible value, i.e., the tensor nuclear norm of , quantifies the accuracy of a stablest algorithm. To substantiate this notion, we establish a bound for the forward error in terms of the growth factor and present numerical evidence comparing various fast algorithms for matrix and complex multiplications, showing that larger growth factors correlate with less accurate results. Compared to similar studies of numerical stability, bilinear stability is more general, applying to any bilinear operators and not just matrix or complex multiplications; is more simplistic, bounding forward error in terms of a single (growth) factor; and is truly tensorial like bilinear complexity, invariant under any orthogonal change of coordinates. As an aside, we study a new algorithm for computing complex multiplication in terms of real, much like Gauss's, but is optimally fast and stable in that it attains both tensor rank and nuclear norm.
Recommendations
Cites work
- scientific article; zbMATH DE number 1716480 (Why is no real title available?)
- scientific article; zbMATH DE number 108480 (Why is no real title available?)
- scientific article; zbMATH DE number 3461412 (Why is no real title available?)
- scientific article; zbMATH DE number 3628385 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- scientific article; zbMATH DE number 1142301 (Why is no real title available?)
- scientific article; zbMATH DE number 2134900 (Why is no real title available?)
- Accuracy and Stability of Numerical Algorithms
- Approximate Solutions for the Bilinear Form Computational Problem
- Complex-valued neural networks with multi-valued neurons.
- Computing the Polar Decomposition—with Applications
- Discovering faster matrix multiplication algorithms with reinforcement learning
- Efficient complex matrix multiplication
- Fast structured matrix computations: tensor rank and Cohn-Umans method
- Functions of Matrices
- Gaussian elimination is not optimal
- Geometry and complexity theory
- Improving the numerical stability of fast matrix multiplication
- Nuclear norm of higher-order tensors
- On Scaling Newton’s Method for Polar Decomposition and the Matrix Sign Function
- On multiplication of 2 \(\times\) 2 matrices
- On the nuclear norm and the singular value decomposition of tensors
- Relative bilinear complexity and matrix multiplication.
- Stability of a Method for Multiplying Complex Matrices with Three Real Matrix Multiplications
- Stability of fast algorithms for matrix multiplication
- Tensors in computations
- The border rank of the multiplication of $2\times 2$ matrices is seven
- The matrix sign decomposition and its relation to the polar decomposition
- The metric theory of tensor products. Grothendieck's résumé revisited
- The nature of computation
This page was built for publication: Numerical stability and tensor nuclear norm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6153359)
