Tensor SVD: Statistical and Computational Limits
From MaRDI portal
Factorization of matrices (15A23) Multilinear algebra, tensor calculus (15A69) Factor analysis and principal components; correspondence analysis (62H25) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)
Abstract: In this paper, we propose a general framework for tensor singular value decomposition (tensor SVD), which focuses on the methodology and theory for extracting the hidden low-rank structure from high-dimensional tensor data. Comprehensive results are developed on both the statistical and computational limits for tensor SVD. This problem exhibits three different phases according to the signal-to-noise ratio (SNR). In particular, with strong SNR, we show that the classical higher-order orthogonal iteration achieves the minimax optimal rate of convergence in estimation; with weak SNR, the information-theoretical lower bound implies that it is impossible to have consistent estimation in general; with moderate SNR, we show that the non-convex maximum likelihood estimation provides optimal solution, but with NP-hard computational cost; moreover, under the hardness hypothesis of hypergraphic planted clique detection, there are no polynomial-time algorithms performing consistently in general.
Cited in
(85)- Covariate-adjusted tensor classification in high dimensions
- 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
- An optimal statistical and computational framework for generalized tensor estimation
- Heteroskedastic PCA: algorithm, optimality, and applications
- Isotonic regression with unknown permutations: statistics, computation and adaptation
- Tensor clustering with planted structures: statistical optimality and computational limits
- Inference for low-rank tensors -- no need to debias
- Computational barriers to estimation from low-degree polynomials
- Hyper-Laplacian regularized multi-view subspace clustering with low-rank tensor constraint
- Limiting behavior of largest entry of random tensor constructed by high-dimensional data
- Normal approximation and confidence region of singular subspaces
- Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
- Kronecker-structured covariance models for multiway data
- \(L^{\infty}\) estimation of tensor truncations
- Statistical query lower bounds for tensor PCA
- Adaptive singular value shrinkage estimate for low rank tensor denoising
- Tensor Canonical Correlation Analysis With Convergence and Statistical Guarantees
- Nonconvex Low-Rank Tensor Completion from Noisy Data
- Generalized Tensor Decomposition With Features on Multiple Modes
- Inference for multiple heterogeneous networks with a common invariant subspace
- A sharp blockwise tensor perturbation bound for orthogonal iteration
- The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
- Factor Models for High-Dimensional Tensor Time Series
- Matrix‐based introduction to multivariate data analysis, by KoheiAdachi2nd edition. Singapore: Springer Nature, 2020. pp. 457.
- Statistical inference on the significance of rows and columns for matrix-valued data in an additive model
- NT-DPTC: a non-negative temporal dimension preserved tensor completion model for missing traffic data imputation
- Generalized Liquid Association Analysis for Multimodal Data Integration
- High-Dimensional Gaussian Graphical Regression Models with Covariates
- Correlation Tensor Decomposition and Its Application in Spatial Imaging Data
- Parsimonious Tensor Discriminant Analysis
- Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
- Generalized Low-Rank Plus Sparse Tensor Estimation by Fast Riemannian Optimization
- Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
- Statistical Inference for High-Dimensional Matrix-Variate Factor Models
- Optimal estimation and computational limit of low-rank Gaussian mixtures
- Long random matrices and tensor unfolding
- Latent Space Model for Higher-Order Networks and Generalized Tensor Decomposition
- Learning polynomial transformations via generalized tensor decompositions
- Model-Based Tensor Low-Rank Clustering
- Subexponential-time algorithms for sparse PCA
- Guaranteed Functional Tensor Singular Value Decomposition
- Convex set-oriented singular value decomposition with bounded uncertainties
- Smoothing composite proximal gradient algorithm for sparse group Lasso problems with nonsmooth loss functions
- A stochastic perturbation analysis of the QR decomposition and its applications
- Robust Low-Rank Tensor Decomposition with the L 2 Criterion
- Joint Tensor Modeling of Single Cell 3D Genome and Epigenetic Data with Muscle
- Computational lower bounds for graphon estimation via low-degree polynomials
- Computational and statistical thresholds in multi-layer stochastic block models
- Multilayer random dot product graphs: estimation and online change point detection
- Optimal clustering by Lloyd's algorithm for low-rank mixture model
- Tucker tensor factor models: matricization and mode-wise PCA estimation
- Sharp concentration of simple random tensors
- Distributed Tensor Principal Component Analysis with Data Heterogeneity
- Multi-Dimensional Domain Generalization with Low-Rank Structures
- Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations
- Mode-wise principal subspace pursuit and matrix spiked covariance model
- CP factor model for dynamic tensors
- On the multiway principal component analysis
- The coefficient estimation of tensor autoregression based on TR decomposition
- Fourth order random tensors and their applications in statistics
- Estimating Higher-Order Mixed Memberships via the l2,∞ Tensor Perturbation Bound
- Euclidean Mirrors and Dynamics in Network Time Series
- Contextual tensor decomposition by projected alternating least squares
- Large-dimensional independent component analysis: statistical optimality and computational tractability
- A random matrix approach to low-multilinear-rank tensor approximation
- Stochastic Low-Rank Tensor Bandits for Multi-Dimensional Online Decision Making
- The Tucker low-rank classification model for tensor data
- Deflated HeteroPCA: overcoming the curse of ill-conditioning in heteroskedastic PCA
- A new feature extraction scheme based on support optimization in enhanced multivariance products representation for hyperspectral imagery
- Random line graphs and edge-attributed network inference
- Tensor factor model estimation by iterative projection
- Tensor-on-tensor regression: Riemannian optimization, over-parameterization, statistical-computational gap and their interplay
- Sparse higher-order partial least squares for simultaneous variable selection, dimension reduction and tensor denoising
- Quasi-SVD: Learning a Lie-constrained matrix factorisation for real-time imaging
- Online tensor learning: computational and statistical trade-offs, adaptivity and optimal regret
- Statistical inference for low-rank tensors: heteroskedasticity, subgaussianity, and applications
- Statistical inference in tensor completion: optimal uncertainty quantification and statistical-to-computational gaps
- Sharp concentration of simple random tensors. II: Asymmetry
- An omnibus embedding of multiple random graphs and implications for multiscale network inference
- Multivariate Analysis for Multiple Network Data via Semi-Symmetric Tensor PCA
- Community detection and network reconstruction with dependent connectivity from rich but noisy network data
- Rank and Factor Loadings Estimation in Time Series Tensor Factor Model by Pre-averaging
This page was built for publication: Tensor SVD: Statistical and Computational Limits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4562322)
