Noisy tensor completion via the sum-of-squares hierarchy
From MaRDI portal
Publication:2144539
DOI10.1007/s10107-022-01793-9zbMath1494.90065arXiv1501.06521OpenAlexW4220801984WikidataQ114228497 ScholiaQ114228497MaRDI QIDQ2144539
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
Related Items
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\)
