Average-case complexity of tensor decomposition for low-degree polynomials (Q6499332)

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

Average-case complexity of tensor decomposition for low-degree polynomials

scientific article; zbMATH DE number 7844703

Language	Label	Description	Also known as
default for all languages	No label defined
English	Average-case complexity of tensor decomposition for low-degree polynomials	scientific article; zbMATH DE number 7844703

Statements

instance of

scholarly article

0 references

title

Average-case complexity of tensor decomposition for low-degree polynomials (English)

0 references

author

Alexander S. Wein

0 references

publication date

8 May 2024

0 references

zbMATH Keywords

low-degree polynomials

0 references

tensor decomposition

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

A spectral algorithm for latent Dirichlet allocation

0 references

A tensor approach to learning mixed membership community models

0 references

Analyzing tensor power method dynamics in overcomplete regime

0 references

Estimation under group actions: recovering orbits from invariants

0 references

Q5875785

0 references

A nearly tight sum-of-squares lower bound for the planted clique problem

0 references

Dictionary learning and tensor decomposition via the sum-of-squares method

0 references

Algorithmic thresholds for tensor PCA

0 references

Free Energy Wells and Overlap Gap Property in Sparse PCA

0 references

Optimal detection of sparse principal components in high dimension

0 references

How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA

0 references

Refined methods for the identifiability of tensors

0 references

Bispectrum Inversion With Application to Multireference Alignment

0 references

Fourth-Order Cumulant-Based Blind Identification of Underdetermined Mixtures

0 references

The Average-Case Time Complexity of Certifying the Restricted Isometry Property

0 references

Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model

0 references

Statistical algorithms and a lower bound for detecting planted cliques

0 references

The overlap gap property in principal submatrix recovery

0 references

Disordered systems insights on computational hardness

0 references

Limits of local algorithms over sparse random graphs

0 references

Sparse high-dimensional linear regression. Estimating squared error and a phase transition

0 references

Learning mixtures of Gaussians in high dimensions

0 references

Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms

0 references

On the optimization landscape of tensor decompositions

0 references

Fourier PCA and robust tensor decomposition

0 references

Most tensor problems are NP-hard

0 references

On the integrality gap of degree-4 sum of squares for planted clique

0 references

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors

0 references

Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)

0 references

Large Cliques Elude the Metropolis Process

0 references

Community detection on mixture multilayer networks via regularized tensor decomposition

0 references

A stress-free sum-of-squares lower bound for coloring

0 references

Sum of squares lower bounds for refuting any CSP

0 references

Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio

0 references

Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications

0 references

A Decomposition for Three-Way Arrays

0 references

Tensor clustering with planted structures: statistical optimality and computational limits

0 references

Algorithmic aspects of machine learning

0 references

Spectral methods from tensor networks

0 references

The sample complexity of multireference alignment

0 references

HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS

0 references

Computational barriers to estimation from low-degree polynomials

0 references

Tensor Decomposition for Signal Processing and Machine Learning

0 references

Optimal low-degree hardness of maximum independent set

0 references

Identifiers

DOI

10.1145/3564246.3585232

0 references

Mathematics Subject Classification ID

68Qxx

0 references

zbMATH DE Number

7844703

0 references

Sitelinks

Mathematics(1 entry)

mardi Average-case complexity of tensor decomposition for low-degree polynomials