Black Box Low Tensor-Rank Approximation Using Fiber-Crosses

By M. Espig, Lars Grasedyck, Wolfgang Hackbusch. 2009

46 citations recorded by the source corpus.

AbstractIn this article we introduce a black box type algorithm for the approximation of tensors A in high dimension d. The algorithm adaptively determines 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 ℓ2-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 fiber-crosses of the tensor so that the Hessian can be assembled and evaluated in a data-sparse form requiring a complexity of $\mathcal{O}(Pd)$ , where P is the number of fiber-crosses and d the order of the tensor.

Subfields: Computational Mathematics, Computational Mechanics, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Mechanics

In Computational Theory and Mathematics

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “Based on fiber crosses, a quite different extension for tensors of arbitrary order can be found in [74].”
Variational calculus with sums of elementary tensors of fixed rank (2012, unknown): “In [5, 8, 6] a modified Newton method is used to solve minimization problems with sums of elementary tensors.”
Black box approximation of tensors in hierarchical Tucker format (2013, methodology): “This is done by a simple greedy search in the entries of the remainder (similar to Algorithm 2 in [3]) starting at random entries and then looking for entries by varying only one component at a time.”
Fast truncation of mode ranks for bilinear tensor operations (2010, unknown): “This explains why among many algorithms of canonical approximation (cf. [4, 7, 11, 25]) none is known as absolutely reliable, and no robust tools for linear algebra operations maintaining the canonical format (linear combinations, etc.) are proposed.”
F ¨ Ur Mathematik in Den Naturwissenschaften Leipzig Generalized Cross Approximation for 3d-tensors Generalized Cross Approximation for 3d-tensors (background): “This was done in different ways, see for instance [3] [10].”
Efficient low-rank approximation of the stochastic Galerkin matrix in tensor formats (2014, background): “For recent algorithms in the canonical tensor format we refer to [4, 5, 6, 9, 10].”