论文标题
数值稳定性和张量核标准
Numerical stability and tensor nuclear norm
论文作者
论文摘要
我们提出了双线性稳定性的概念，即数值稳定性是双线性复杂性对时间复杂性的复杂性。在双线性的复杂性中，用于评估双线性操作员$β的算法：\ mathbb {u} \ times \ times \ mathbb {v} \ to \ mathbb {w} $是分解$β=φ_1\ outimimes \ otimes w_r $; $ r $的条款数量捕获了算法的速度；及其最小的可能值，即张量级$β$，量化了最快算法的速度。双线性稳定性将规范引入混合：算法的生长因子$ \lvertφ_1\ rvert_* \lvertψ_1\ rvert_* \ lvert w_1 \ rvert w_1 \ rvert + \ dots + \ dots + \ lvert + lvertφ_R\ rvertφ* \ lvert_* \ lvert y $ ceptry of ceptraster of ceptrast y o \ rverty 算法;及其最小的可能值，即$β$的张量核定标准，可以量化最稳定算法的准确性。为了证实这一概念，我们在生长因子方面建立了针对正向误差的约束，并提供了比较矩阵和复杂乘法的各种快速算法的数值证据，表明较大的生长因子与较少准确的结果相关。与类似的数值稳定性研究相比，双线性稳定性更为笼统，适用于任何双线性算子，而不仅仅是矩阵或复杂乘法。更简单，就单个（增长）因子而言，前向误差有限；并且在坐标的任何正交变化下，都像双线性复杂性一样真正的紧张关系。顺便说一句，我们研究了一种新算法，用于以真实的方式计算复杂的乘法，就像高斯一样，但在最佳快速和稳定上，它既达到张量等级又达到核定标准。
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 $β: \mathbb{U} \times \mathbb{V} \to \mathbb{W}$ is a decomposition $β= φ_1 \otimes ψ_1 \otimes w_1 + \dots + φ_r \otimes ψ_r \otimes w_r $; the number of terms $r$ 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 $\lVert φ_1 \rVert_* \lVert ψ_1 \rVert_* \lVert w_1 \rVert + \dots + \lVert φ_r \rVert_* \lVert ψ_r \rVert_* \lVert w_r \rVert$ 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.
