Noisy tensor completion via the sum-of-squares hierarchy

DOI10.1007/s10107-022-01793-9zbMath1494.90065arXiv1501.06521OpenAlexW4220801984WikidataQ114228497 ScholiaQ114228497MaRDI QIDQ2144539

Ankur Moitra, Boaz Barak

Publication date: 14 June 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.06521

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Semidefinite programming (90C22)

Related Items (6)

Sum of Squares Bounds for the Empty Integral Hull Problem ⋮ Covariate-Assisted Sparse Tensor Completion ⋮ Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ Cross: efficient low-rank tensor completion ⋮ On polynomial time methods for exact low-rank tensor completion ⋮ Certifying Polynomial Nonnegativity via Hyperbolic Optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Low-rank tensor completion by Riemannian optimization
• Empirical margin distributions and bounding the generalization error of combined classifiers
• The convex geometry of linear inverse problems
• A spectral algorithm for latent Dirichlet allocation
• Exact matrix completion via convex optimization
• Global Optimization with Polynomials and the Problem of Moments
• Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method
• Learning mixtures of spherical gaussians
• Tensor completion and low-n-rank tensor recovery via convex optimization
• Strong Refutation Heuristics for Random k-SAT
• Relations between average case complexity and approximation complexity
• Classical deterministic complexity of Edmonds' Problem and quantum entanglement
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• An approach to obtaining global extremums in polynomial mathematical programming problems
• Sum-of-squares proofs and the quest toward optimal algorithms
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• 10.1162/153244303321897690
• Spectral Algorithms for Tensor Completion
• Strongly refuting random CSPs below the spectral threshold
• Spectral methods from tensor networks
• Rounding sum-of-squares relaxations
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Compressed Sensing Off the Grid
• Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Tighter Low-rank Approximation via Sampling the Leveraged Element
• Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization
• Hypercontractivity, sum-of-squares proofs, and their applications
• Some optimal inapproximability results
• Recognizing More Unsatisfiable Random k-SAT Instances Efficiently
• Learning Theory
• Low-rank matrix completion using alternating minimization
• Learning nonsingular phylogenies and hidden Markov models
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Distributional and \(L^q\) norm inequalities for polynomials over convex bodies in \(\mathbb{R}^n\)

This page was built for publication: Noisy tensor completion via the sum-of-squares hierarchy