Average-case complexity of tensor decomposition for low-degree polynomials
From MaRDI portal
Cites work
- A Decomposition for Three-Way Arrays
- A nearly tight sum-of-squares lower bound for the planted clique problem
- A spectral algorithm for latent Dirichlet allocation
- A stress-free sum-of-squares lower bound for coloring
- A tensor approach to learning mixed membership community models
- Algorithmic aspects of machine learning
- Algorithmic thresholds for tensor PCA
- Analyzing tensor power method dynamics in overcomplete regime
- Bispectrum Inversion With Application to Multireference Alignment
- Community detection on mixture multilayer networks via regularized tensor decomposition
- Computational barriers to estimation from low-degree polynomials
- Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
- Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms
- Dictionary learning and tensor decomposition via the sum-of-squares method
- Disordered systems insights on computational hardness
- Estimation under group actions: recovering orbits from invariants
- Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
- Fourier PCA and robust tensor decomposition
- Fourth-Order Cumulant-Based Blind Identification of Underdetermined Mixtures
- Free Energy Wells and Overlap Gap Property in Sparse PCA
- HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS
- How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA
- scientific article; zbMATH DE number 7650426 (Why is no real title available?)
- Large Cliques Elude the Metropolis Process
- Learning mixtures of Gaussians in high dimensions
- Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
- Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model
- Limits of local algorithms over sparse random graphs
- Most tensor problems are NP-hard
- Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
- On the integrality gap of degree-4 sum of squares for planted clique
- On the optimization landscape of tensor decompositions
- Optimal detection of sparse principal components in high dimension
- Optimal low-degree hardness of maximum independent set
- Refined methods for the identifiability of tensors
- Sparse high-dimensional linear regression. Estimating squared error and a phase transition
- Spectral methods from tensor networks
- Statistical algorithms and a lower bound for detecting planted cliques
- Sum of squares lower bounds for refuting any CSP
- Tensor clustering with planted structures: statistical optimality and computational limits
- Tensor Decomposition for Signal Processing and Machine Learning
- The Average-Case Time Complexity of Certifying the Restricted Isometry Property
- The overlap gap property in principal submatrix recovery
- The sample complexity of multireference alignment
Cited in
(2)
This page was built for publication: Average-case complexity of tensor decomposition for low-degree polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499332)
