Optimal low rank tensor recovery
We investigate the sample size requirement for exact recovery of a high order tensor of low rank from a subset of its entries. In the Tucker decomposition framework, we show that the Riemannian optimization algorithm with initial value obtained from a spectral method can reconstruct a tensor of size $n\times n \times\cdots \times n$ tensor of ranks $(r,\cdots,r)$ with high probability from as few as $O((r^d+dnr)\log(d))$ entries. In the case of order 3 tensor, the entries can be asymptotically as few as $O(nr)$ for a low rank large tensor. We show the theoretical guarantee condition for the recovery. The analysis relies on the tensor restricted isometry property (tensor RIP) and the curvature of the low rank tensor manifold. Our algorithm is computationally efficient and easy to implement. Numerical results verify that the algorithms are able to recover a low rank tensor from minimum number of measurements. The experiments on hyperspectral images recovery also show that our algorithm is capable of real world signal processing problems.
Code (0)
등록된 구현이 없습니다.
Tasks
Riemannian optimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Generalized Nonconvex Approach for Low-Tubal-Rank Tensor Recovery
The tensor-tensor product-induced tensor nuclear norm (t-TNN) (Lu et al., 2020) minimization for low-tubal-rank tensor recovery attracts broad attention recently. However, minimizing the t-TNN faces some drawbacks. For e…
Image InpaintingLow-Rank Matrix CompletionOptimal Low-Rank Tensor Recovery from Separable Measurements: Four Contractions Suffice
Tensors play a central role in many modern machine learning and signal processing applications. In such applications, the target tensor is usually of low rank, i.e., can be expressed as a sum of a small number of rank on…
Matrix CompletionTensor DecompositionLow-Rank Tensor Completion With a New Tensor Nuclear Norm Induced by Invertible Linear Transforms
This work studies the low-rank tensor completion problem, which aims to exactly recover a low-rank tensor from partially observed entries. Our model is inspired by the recently proposed tensor-tensor product (t-product) …
Exact Low Tubal Rank Tensor Recovery from Gaussian Measurements
The recent proposed Tensor Nuclear Norm (TNN) [Lu et al., 2016; 2018a] is an interesting convex penalty induced by the tensor SVD [Kilmer and Martin, 2011]. It plays a similar role as the matrix nuclear norm which is the…
Cross: Efficient Low-rank Tensor Completion
The completion of tensors, or high-order arrays, attracts significant attention in recent research. Current literature on tensor completion primarily focuses on recovery from a set of uniformly randomly measured entries,…