Spectral algorithms for tensor completion

DOI10.1002/CPA.21748MaRDI QIDQ4962471zbMATH OpenOpenAlexFDO

Authors Nike Sun, Andrea Montanari

Publication date 2 November 2018

Published in Communications on Pure and Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

tensor completionunfolding

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Matrix completion problems (15A83)

Abstract: In the tensor completion problem, one seeks to estimate a low-rank tensor based on a random sample of revealed entries. In terms of the required sample size, earlier work revealed a large gap between estimation with unbounded computational resources (using, for instance, tensor nuclear norm minimization) and polynomial-time algorithms. Among the latter, the best statistical guarantees have been proved, for third-order tensors, using the sixth level of the sum-of-squares (SOS) semidefinite programming hierarchy (Barak and Moitra, 2014). However, the SOS approach does not scale well to large problem instances. By contrast, spectral methods --- based on unfolding or matricizing the tensor --- are attractive for their low complexity, but have been believed to require a much larger sample size. This paper presents two main contributions. First, we propose a new unfolding-based method, which outperforms naive ones for symmetric $k$-th order tensors of rank $r$. For this result we make a study of singular space estimation for partially revealed matrices of large aspect ratio, which may be of independent interest. For third-order tensors, our algorithm matches the SOS method in terms of sample size (requiring about $r{d}^{3/2}$ revealed entries), subject to a worse rank condition ($rll{d}^{3/4}$ rather than $rll{d}^{3/2}$). We complement this result with a different spectral algorithm for third-order tensors in the overcomplete ($rged$) regime. Under a random model, this second approach succeeds in estimating tensors of rank $dlerll{d}^{3/2}$ from about $r{d}^{3/2}$ revealed entries.

Recommendations

• On polynomial time methods for exact low-rank tensor completion
• On tensor completion via nuclear norm minimization
• Iterative algorithm for the symmetric and nonnegative tensor completion problem
• Statistically optimal and computationally efficient low rank tensor completion from noisy entries
• Low-rank approximation and completion of positive tensors

Cited in

(37)

• On polynomial time methods for exact low-rank tensor completion
• Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
• Sparse random tensors: concentration, regularization and applications
• An \({\ell_p}\) theory of PCA and spectral clustering
• 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
• Adaptive higher-order spectral estimators
• Statistically optimal and computationally efficient low rank tensor completion from noisy entries
• Matrix completion and tensor rank
• Dictionary learning and tensor decomposition via the sum-of-squares method
• Quantized compressed sensing: a survey
• On tensor completion via nuclear norm minimization
• Rank-deficient spectral factorization and wavelets completion problem
• Iterative algorithm for the symmetric and nonnegative tensor completion problem
• Statistical query lower bounds for tensor PCA
• ISLET: fast and optimal low-rank tensor regression via importance sketching
• Nonconvex Low-Rank Tensor Completion from Noisy Data
• Deterministic tensor completion with hypergraph expanders
• Spectral methods from tensor networks
• Endpoint results for Fourier integral operators on noncompact symmetric spaces
• Fiber sampling approach to canonical polyadic decomposition and application to tensor completion
• The geometry of rank-one tensor completion
• Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Statistical mechanics of low-rank tensor decomposition
• Spectral partitioning of large and sparse 3‐tensors using low‐rank tensor approximation
• Tensor completion by multi-rank via unitary transformation
• Marchenko–Pastur law with relaxed independence conditions
• Recovering orthogonal tensors under arbitrarily strong, but locally correlated, noise
• Covariate-Assisted Sparse Tensor Completion
• Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
• Long random matrices and tensor unfolding
• Inference for heteroskedastic PCA with missing data
• Sparse random hypergraphs: non-backtracking spectra and community detection
• Multi-Dimensional Domain Generalization with Low-Rank Structures
• Deflated HeteroPCA: overcoming the curse of ill-conditioning in heteroskedastic PCA

This page was built for publication: Spectral algorithms for tensor completion

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