Q-less QR decomposition in inner product spaces

详细信息    查看全文

• 作者：H.-Y. Fan^a ; ^{hyfan@ntnu.edu.tw" class="auth_mail" title="E-mail the corresponding author} ; L. Zhang^b ; ^{zhanglp@zjut.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; E.K.-w. Chu^c ; ^{eric.chu@monash.edu" class="auth_mail" title="E-mail the corresponding author} ; Y. Wei^d ; ^{ymwei@fudan.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：15A06 ; 15A24 ; 15A30 ; 15A69 ; 15A72 ; 65F10 ; 65N22
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：15 February 2016
• 年：2016
• 卷：491
• 期：Complete
• 页码：292-316
• 全文大小：827 K

文摘

Tensor computation is intensive and difficult. Invariably, a vital component is the truncation of tensors, so as to control the memory and associated computational requirements. Various tensor toolboxes have been designed for such a purpose, in addition to transforming tensors between different formats. In this paper, we propose a simple Q-less QR truncation technique for tensors {x_(i)}$\{x_{(i)}\}$ with x_(i)∈R^{n₁×⋯×n_d} in the simple and natural Kronecker product form. It generalizes the QR decomposition with column pivoting, adapting the well-known Gram–Schmidt orthogonalization process. The main difficulty lies in the fact that linear combinations of tensors cannot be computed or stored explicitly. All computations have to be performed on the coefficients α_i${\alpha }_i$ in an arbitrary tensor v=∑_iα_ix_(i)$v={\sum }_i{\alpha }_i{x}_{(i)}$. The orthonormal Q   factor in the QR decomposition X≡[x₍₁₎,⋯,x_(p)]=QR$X\equiv [x_{(1)},\cdots ,x_{(p)}]=QR$ cannot be computed but expressed as XR⁻¹$X{R}^{-1}$ when required. The resulting algorithm has an O(p²dn)$O(p^{2}dn)$ computational complexity, with n=max⁡n_i$n=\max n_i$. Some illustrative examples in the numerical solution of tensor linear equations are presented.