On polynomial time methods for exact low-rank tensor completion

DOI10.1007/S10208-018-09408-6MaRDI QIDQ2007852zbMATH OpenOpenAlexFDO

Authors Dong Xia, Ming Yuan

Publication date 22 November 2019

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.06980

zbMATH Keywords

concentration inequalityconvex optimizationgradient descent algorithmGrassmannianmatrix completionpolynomial time complexityspectral algorithmtensor completion

Mathematics Subject Classification ID

Matrix completion problems (15A83) Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: In this paper, we investigate the sample size requirement for exact recovery of a high order tensor of low rank from a subset of its entries. We show that a gradient descent algorithm with initial value obtained from a spectral method can, in particular, reconstruct a $dimesdimesd$ tensor of multilinear ranks $(r,r,r)$ with high probability from as few as $O(r^{7/2}{d}^{3/2}lo{g}^{7/2}d+r^{7}dlo{g}^{6}d)$ entries. In the case when the ranks $r=O(1)$, our sample size requirement matches those for nuclear norm minimization (Yuan and Zhang, 2016a), or alternating least squares assuming orthogonal decomposability (Jain and Oh, 2014). Unlike these earlier approaches, however, our method is efficient to compute, easy to implement, and does not impose extra structures on the tensor. Numerical results are presented to further demonstrate the merits of the proposed approach.

Review text

The goal of tensor completion is to recover a tensor from partial observations of its entries. Although the second-order (matrix) case is in general NP-hard, it is possible to develop tractable algorithms to achieve exact recovery with high probability. The question is, if the same can be said for higher-order tensors. The goal of this paper is to develop a computationally efficient approach with a tight sample size requirement for completing a third-order tensors that are of low multilinear ranks. The authors show that a gradient descent algorithm with initial value obtained from a new spectral method can reconstruct a \(d_1 \times d_2 \times d_3\) tensor with multilinear ranks \((r_1,r_2,r_3)\) with high probability from as few as \(O\left(r_1r_2r_3(rd_1d_2d_3)^{1/2}\log^{7/2}d + (r_1r_2r_3)^2rd\log^6d\right)\) entries, where \(r=\max\{r_1,r_2,r_3\}\) and \(d=\max\{d_1,d_2,d_3\}\). The authors are primarily interested in high-dimensional (large \(d\)) and low-rank (small \(r\)) instances. The new second-order spectral method guarantees to produce an initial value sufficiently close to the optimal value. Both algorithms, the gradient descent algorithm and the second-order spectral algorithm, are of polynomial time complexity. The total computational cost of the method depends on the convergence rate of the gradient descent algorithm. Numerical experiments suggest a linear convergence rate. The framework is established for third-order tensors but it can be naturally extended to higher order tensors.

Recommendations

• Spectral algorithms for tensor completion
• Nonconvex Low-Rank Tensor Completion from Noisy Data
• Statistically optimal and computationally efficient low rank tensor completion from noisy entries
• Low-rank approximation and completion of positive tensors
• Cross: efficient low-rank tensor completion

Cites work

• A Bennett concentration inequality and its application to suprema of empirical processes
• A Newton-Grassmann method for computing the best multilinear rank-(r₁,r₂,r₃) approximation of a tensor
• A simpler approach to matrix completion
• A useful variant of the Davis-Kahan theorem for statisticians
• Decoupling inequalities for the tail probabilities of multivariate \(U\)- statistics
• Exact matrix completion via convex optimization
• scientific article; zbMATH DE number 1254560 (Why is no real title available?)
• scientific article; zbMATH DE number 5223994 (Why is no real title available?)
• Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion
• Linear and nonlinear programming.
• Low rank tensor recovery via iterative hard thresholding
• Low-rank tensor completion by Riemannian optimization
• Matrix Completion From a Few Entries
• Most tensor problems are NP-hard
• Noisy tensor completion via the sum-of-squares hierarchy
• On tensor completion via nuclear norm minimization
• Quasi-Newton methods on Grassmannians and multilinear approximations of tensors
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Spectral algorithms for tensor completion
• Tensor Algebra and Multidimensional Harmonic Retrieval in Signal Processing for MIMO Radar
• Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
• Tensor decompositions for learning latent variable models
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• Tensor theta norms and low rank recovery
• Tensor-Based Formulation and Nuclear Norm Regularization for Multienergy Computed Tomography
• The Geometry of Algorithms with Orthogonality Constraints
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• User-friendly tail bounds for sums of random matrices

Cited in

(32)

• Cross: efficient low-rank tensor completion
• Statistical inference for structured high-dimensional models. Abstracts from the workshop held March 11--17, 2018
• Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
• Community detection on mixture multilayer networks via regularized tensor decomposition
• Riemannian conjugate gradient descent method for fixed multi rank third-order tensor completion
• An optimal statistical and computational framework for generalized tensor estimation
• Inference for low-rank tensors -- no need to debias
• Noisy tensor completion via the sum-of-squares hierarchy
• Statistically optimal and computationally efficient low rank tensor completion from noisy entries
• An approximation method of CP rank for third-order tensor completion
• Low-rank approximation and completion of positive tensors
• On tensor completion via nuclear norm minimization
• Variants of alternating least squares tensor completion in the tensor train format
• Spectral algorithms for tensor completion
• Near-optimal sample complexity for convex tensor completion
• ISLET: fast and optimal low-rank tensor regression via importance sketching
• Deterministic tensor completion with hypergraph expanders
• Deterministic and Probabilistic Conditions for Finite Completability of Low-Tucker-Rank Tensor
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
• Factor Models for High-Dimensional Tensor Time Series
• Tensor completion by multi-rank via unitary transformation
• Recovering orthogonal tensors under arbitrarily strong, but locally correlated, noise
• Generalized Low-Rank Plus Sparse Tensor Estimation by Fast Riemannian Optimization
• Covariate-Assisted Sparse Tensor Completion
• Latent Space Model for Higher-Order Networks and Generalized Tensor Decomposition
• Constructing low-rank Tucker tensor approximations using generalized completion
• Robust Low-Rank Tensor Decomposition with the L ₂ Criterion
• Tucker tensor factor models: matricization and mode-wise PCA estimation
• A single-mode quasi Riemannian gradient descent algorithm for low-multilinear-rank tensor recovery
• Tensor-on-tensor regression: Riemannian optimization, over-parameterization, statistical-computational gap and their interplay
• Online tensor learning: computational and statistical trade-offs, adaptivity and optimal regret

This page was built for publication: On polynomial time methods for exact low-rank tensor completion

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