Q-less QR decomposition in inner product spaces

H. Y. Fan, L. Zhang, E. K.W. Chu*, Y. Wei

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

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)} with x(i)∈Rn1×⋯×nd 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 in an arbitrary tensor v=∑iαix(i). The orthonormal Q factor in the QR decomposition X≡[x(1),⋯,x(p)]=QR cannot be computed but expressed as XR-1 when required. The resulting algorithm has an O(p2dn) computational complexity, with n=maxni. Some illustrative examples in the numerical solution of tensor linear equations are presented.

Original languageEnglish
Pages (from-to)292-316
Number of pages25
JournalLinear Algebra and Its Applications
Volume491
DOIs
Publication statusPublished - 2016 Feb 15

Keywords

  • Column pivoting
  • Gram-Schmidt orthogonalization
  • Kronecker product
  • Large-scale problem
  • Linear equation
  • Low-rank representation
  • Multilinear algebra
  • QR decomposition

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Q-less QR decomposition in inner product spaces'. Together they form a unique fingerprint.

Cite this