Tensor SVD: Statistical and Computational Limits
From MaRDI portal
Factor analysis and principal components; correspondence analysis (62H25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Factorization of matrices (15A23) Multilinear algebra, tensor calculus (15A69) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)
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
(77)- High-Dimensional Gaussian Graphical Regression Models with Covariates
- Model-Based Tensor Low-Rank Clustering
- Adaptive singular value shrinkage estimate for low rank tensor denoising
- Fourth order random tensors and their applications in statistics
- Guaranteed Functional Tensor Singular Value Decomposition
- Estimating Higher-Order Mixed Memberships via the l2,∞ Tensor Perturbation Bound
- Euclidean Mirrors and Dynamics in Network Time Series
- Subexponential-time algorithms for sparse PCA
- Convex set-oriented singular value decomposition with bounded uncertainties
- Contextual tensor decomposition by projected alternating least squares
- Smoothing composite proximal gradient algorithm for sparse group Lasso problems with nonsmooth loss functions
- Large-dimensional independent component analysis: statistical optimality and computational tractability
- Parsimonious Tensor Discriminant Analysis
- Tensor clustering with planted structures: statistical optimality and computational limits
- A random matrix approach to low-multilinear-rank tensor approximation
- The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
- Statistical-computational trade-offs in tensor PCA and related problems via communication complexity
- Covariate-adjusted tensor classification in high dimensions
- Stochastic Low-Rank Tensor Bandits for Multi-Dimensional Online Decision Making
- The Tucker low-rank classification model for tensor data
- An optimal statistical and computational framework for generalized tensor estimation
- Inference for low-rank tensors -- no need to debias
- Normal approximation and confidence region of singular subspaces
- Generalized Low-Rank Plus Sparse Tensor Estimation by Fast Riemannian Optimization
- Isotonic regression with unknown permutations: statistics, computation and adaptation
- Deflated HeteroPCA: overcoming the curse of ill-conditioning in heteroskedastic PCA
- Kronecker-structured covariance models for multiway data
- 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
- Optimal estimation and computational limit of low-rank Gaussian mixtures
- Matrix‐based introduction to multivariate data analysis, by KoheiAdachi2nd edition. Singapore: Springer Nature, 2020. pp. 457.
- Long random matrices and tensor unfolding
- Tensor factor model estimation by iterative projection
- Tensor-on-tensor regression: Riemannian optimization, over-parameterization, statistical-computational gap and their interplay
- Computational barriers to estimation from low-degree polynomials
- Latent Space Model for Higher-Order Networks and Generalized Tensor Decomposition
- NT-DPTC: a non-negative temporal dimension preserved tensor completion model for missing traffic data imputation
- Sparse higher-order partial least squares for simultaneous variable selection, dimension reduction and tensor denoising
- Generalized Tensor Decomposition With Features on Multiple Modes
- Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
- A stochastic perturbation analysis of the QR decomposition and its applications
- Multilayer random dot product graphs: estimation and online change point detection
- Optimal clustering by Lloyd's algorithm for low-rank mixture model
- scientific article; zbMATH DE number 7415122 (Why is no real title available?)
- Generalized Liquid Association Analysis for Multimodal Data Integration
- Robust Low-Rank Tensor Decomposition with the L 2 Criterion
- Tensor Canonical Correlation Analysis With Convergence and Statistical Guarantees
- Nonconvex Low-Rank Tensor Completion from Noisy Data
- Tucker tensor factor models: matricization and mode-wise PCA estimation
- Statistical inference on the significance of rows and columns for matrix-valued data in an additive model
- Sharp concentration of simple random tensors
- Asymmetry helps: eigenvalue and eigenvector analyses of asymmetrically perturbed low-rank matrices
- Distributed Tensor Principal Component Analysis with Data Heterogeneity
- Multi-Dimensional Domain Generalization with Low-Rank Structures
- Rank and Factor Loadings Estimation in Time Series Tensor Factor Model by Pre-averaging
- Joint Tensor Modeling of Single Cell 3D Genome and Epigenetic Data with Muscle
- Factor Models for High-Dimensional Tensor Time Series
- Statistical Inference for High-Dimensional Matrix-Variate Factor Models
- Computational lower bounds for graphon estimation via low-degree polynomials
- Computational and statistical thresholds in multi-layer stochastic block models
- Hyper-Laplacian regularized multi-view subspace clustering with low-rank tensor constraint
- Learning polynomial transformations via generalized tensor decompositions
- Statistical query lower bounds for tensor PCA
- Community detection on mixture multilayer networks via regularized tensor decomposition
- Heteroskedastic PCA: algorithm, optimality, and applications
- Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations
- Mode-wise principal subspace pursuit and matrix spiked covariance model
- Correlation Tensor Decomposition and Its Application in Spatial Imaging Data
- scientific article; zbMATH DE number 7415085 (Why is no real title available?)
- \(L^{\infty}\) estimation of tensor truncations
- Limiting behavior of largest entry of random tensor constructed by high-dimensional data
- Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
- CP factor model for dynamic tensors
- On the multiway principal component analysis
- Cross: efficient low-rank tensor completion
- The coefficient estimation of tensor autoregression based on TR decomposition
- Statistical inference for structured high-dimensional models. Abstracts from the workshop held March 11--17, 2018
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)
