Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery

MaRDI QIDQ6345292zbMATH OpenFDO

Authors Jian-Feng Cai, Lizhang Miao, Yang Wang, Yin Xian

Publication date 17 July 2020

Mathematics Subject Classification ID

Secant varieties, tensor rank, varieties of sums of powers (14N07) Inverse problems in linear algebra (15A29) Multilinear algebra, tensor calculus (15A69) Iterative numerical methods for linear systems (65F10) Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26)

Abstract: We consider the problem of recovering a low-multilinear-rank tensor from a small amount of linear measurements. We show that the Riemannian gradient algorithm initialized by one step of iterative hard thresholding can reconstruct an order-$d$ tensor of size $nimesldotsimesn$ and multilinear rank $(r,ldots,r)$ with high probability from only $O(n{r}^2+r^{d+1})$ measurements, assuming $d$ is a constant. This sampling complexity is optimal in $n$, compared to existing results whose sampling complexities are all unnecessarily large in $n$. The analysis relies on the tensor restricted isometry property (TRIP) and the geometry of the manifold of all tensors with a fixed multilinear rank. High computational efficiency of our algorithm is also achieved by doing higher order singular value decomposition on intermediate small tensors of size only $2rimesldotsimes2r$ rather than on tensors of size $nimesldotsimesn$ as usual.

This page was built for publication: Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345292)