Black Box Low Tensor Rank Approximation using Fibre-Crosses

Mike Espig, Lars Grasedyck, and Wolfgang Hackbusch

Contact the author: Please use for correspondence this email.
Submission date: 24. Sep. 2008 (revised version: May 2009)
Pages: 38
published in: Constructive approximation, 30 (2009) 3, p. 557-597 
DOI number (of the published article): 10.1007/s00365-009-9076-9
Bibtex
with the following different title: Black box low tensor-rank approximation using fiber-crosses
MSC-Numbers: 15A69, 90C06, 65K10
Keywords and phrases: Low Rank, Tensor, Newton, Cross Approximation, Fibre-Crosses, Black Box
Download full preprint: PDF (395 kB)

Abstract:
In this article we introduce a black box type approximation algorithm for tensors A in high dimension d. The algorithm determines adaptively the positions of entries of the tensor that have to be computed or read, and using these (few) entries it constructs a low rank tensor approximation X that minimizes the -distance between A and X at the chosen positions. The full tensor A is not required, only the evaluation of A at a few positions. The minimization problem is solved by Newton's method which requires the computation and evaluation of the Hessian. For efficiency reasons the positions are located on fibre-crosses of the tensor so that the Hessian can be assembled and evaluated in a data-sparse form requiring a complexity of , where P is the number of fibre-crosses and d the order of the tensor.