Nearly Low Rank Tensors and Their Approximations
For researchers working on tensor approximation and decomposition, this provides a new algorithmic approach that is theoretically grounded and potentially scalable, though the results are theoretical without concrete numerical benchmarks.
The paper proposes a new three-stage method for low-rank tensor approximation that works well when the input tensor is nearly low-rank, and shows that if the tensor is sufficiently close to low-rank, the computed approximation is accurate. The method also enables efficient computation of low-rank decompositions for large-scale tensors.
The low rank tensor approximation problem (LRTAP) is to find a tensor whose rank is small and that is close to a given one. This paper studies the LRTAP when the tensor to be approximated is close to a low rank one. Both symmetric and nonsymmetric tensors are discussed. We propose a new approach for solving the LRTAP. It consists of three major stages: i) Find a set of linear relations that are approximately satisfied by the tensor; such linear relations can be expressed by polynomials and can be found by solving linear least squares. ii) Compute a set of points that are approximately common zeros of the obtained polynomials; they can be found by computing Schur decompositions. iii) Construct a low rank approximating tensor from the obtained points; this can be done by solving linear least squares. Our main conclusion is that if the given tensor is sufficiently close to a low rank one, then the computed tensor is a good enough low rank approximation. This approach can also be applied to efficiently compute low rank tensor decompositions, especially for large scale tensors.