On polynomial time methods for exact low-rank tensor completion
From MaRDI portal
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 tensor of multilinear ranks with high probability from as few as entries. In the case when the ranks , 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.
Recommendations
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 2 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)
