Cross: efficient low-rank tensor completion

DOI10.1214/18-AOS1694MaRDI QIDQ1731066zbMATH OpenWikidataFDO

Authors Anru Zhang

Publication date 6 March 2019

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.01129, https://projecteuclid.org/euclid.aos/1547197244

zbMATH Keywords

cross tensor measurementdenoisingminimax rate-optimalneuroimagingtensor completion

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Matrix completion problems (15A83) Minimax procedures in statistical decision theory (62C20) Estimation in multivariate analysis (62H12) Image analysis in multivariate analysis (62H35) Applications of statistics to biology and medical sciences; meta analysis (62P10) Numerical solutions to overdetermined systems, pseudoinverses (65F20)

Abstract: 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, and the required number of measurements to achieve recovery is not guaranteed to be optimal. In addition, the implementation of some previous methods is NP-hard. In this article, we propose a framework for low-rank tensor completion via a novel tensor measurement scheme we name Cross. The proposed procedure is efficient and easy to implement. In particular, we show that a third order tensor of Tucker rank-$(r_1,r_2,r_3)$ in $p_1$-by-$p_2$-by-$p_3$ dimensional space can be recovered from as few as $r_1{r}_2{r}_3+r_1(p_1-r_1)+r_2(p_2-r_2)+r_3(p_3-r_3)$ noiseless measurements, which matches the sample complexity lower-bound. In the case of noisy measurements, we also develop a theoretical upper bound and the matching minimax lower bound for recovery error over certain classes of low-rank tensors for the proposed procedure. The results can be further extended to fourth or higher-order tensors. Simulation studies show that the method performs well under a variety of settings. Finally, the procedure is illustrated through a real dataset in neuroimaging.

Recommendations

• Statistically optimal and computationally efficient low rank tensor completion from noisy entries
• On polynomial time methods for exact low-rank tensor completion
• Low-rank tensor completion by Riemannian optimization
• Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
• Tucker factorization with missing data with application to low-n-rank tensor completion

Cites work

• A simpler approach to matrix completion
• A statistical multiscale framework for Poisson inverse problems
• Bayesian tensor regression
• Breaking the Curse of Dimensionality, Or How to Use SVD in Many Dimensions
• Cross: efficient low-rank tensor completion
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Estimation of high-dimensional low-rank matrices
• Generalizing the column-row matrix decomposition to multi-way arrays
• scientific article; zbMATH DE number 6982912 (Why is no real title available?)
• Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion
• Learning Theory
• Low rank tensor recovery via iterative hard thresholding
• Low-rank tensor completion by Riemannian optimization
• Matrix Completion From a Few Entries
• Matrix completion via max-norm constrained optimization
• Minimax Optimal Rates for Poisson Inverse Problems With Physical Constraints
• Most tensor problems are NP-hard
• Noisy low-rank matrix completion with general sampling distribution
• Noisy matrix decomposition via convex relaxation: optimal rates in high dimensions
• Noisy tensor completion via the sum-of-squares hierarchy
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• On tensor completion via nuclear norm minimization
• Poisson Matrix Recovery and Completion
• Provable sparse tensor decomposition
• Restricted strong convexity and weighted matrix completion: optimal bounds with noise
• Sampling from large matrices
• Stable, Robust, and Super Fast Reconstruction of Tensors Using Multi-Way Projections
• Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
• Tensor Decompositions and Applications
• Tensor decompositions and sparse log-linear models
• Tensor Regression with Applications in Neuroimaging Data Analysis
• Tensor SVD: Statistical and Computational Limits
• Tensor-Based Formulation and Nuclear Norm Regularization for Multienergy Computed Tomography
• Tensor-CUR Decompositions for Tensor-Based Data
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Tighter low-rank approximation via sampling the leveraged element
• Tucker Dimensionality Reduction of Three-Dimensional Arrays in Linear Time

Cited in

(40)

• Cross: efficient low-rank tensor completion
• On polynomial time methods for exact low-rank tensor completion
• Community detection on mixture multilayer networks via regularized tensor decomposition
• Smoothed tensor quantile regression estimation for longitudinal data
• An optimal statistical and computational framework for generalized tensor estimation
• Inference for low-rank tensors -- no need to debias
• Rank determination in tensor factor model
• Statistically optimal and computationally efficient low rank tensor completion from noisy entries
• An approximation method of CP rank for third-order tensor completion
• Cross
• Sparse tensor additive regression
• ISLET: fast and optimal low-rank tensor regression via importance sketching
• Nonconvex Low-Rank Tensor Completion from Noisy Data
• A sharp blockwise tensor perturbation bound for orthogonal iteration
• Deterministic tensor completion with hypergraph expanders
• Dynamic tensor clustering
• Factor Models for High-Dimensional Tensor Time Series
• High-Dimensional Vector Autoregressive Time Series Modeling via Tensor Decomposition
• Tensor completion by multi-rank via unitary transformation
• Tensor completion with noisy side information
• Statistical inference on the significance of rows and columns for matrix-valued data in an additive model
• Tensor envelope mixture model for simultaneous clustering and multiway dimension reduction
• Partially Observed Dynamic Tensor Response Regression
• Parsimonious Tensor Discriminant Analysis
• Covariate-Assisted Sparse Tensor Completion
• A Corrected Tensor Nuclear Norm Minimization Method for Noisy Low-Rank Tensor Completion
• Constructing low-rank Tucker tensor approximations using generalized completion
• Exponential family tensor completion with auxiliary information
• Model-Based Tensor Low-Rank Clustering
• Matrix completion from a computational statistics perspective
• Robust Low-Rank Tensor Decomposition with the L ₂ Criterion
• Tucker tensor factor models: matricization and mode-wise PCA estimation
• Multi-Dimensional Domain Generalization with Low-Rank Structures
• Bayesian inference approaches for tensor quantile regression and its application
• Fourth order random tensors and their applications in statistics
• Low-rank quaternion tensor completion for color video inpainting via a novel factorization strategy
• Stochastic Low-Rank Tensor Bandits for Multi-Dimensional Online Decision Making
• An omnibus embedding of multiple random graphs and implications for multiscale network inference
• High-order accurate inference on manifolds
• Worst-Case Completion of Tensors with Approximately Few ANOVA Terms

This page was built for publication: Cross: efficient low-rank tensor completion

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