A note on probably certifiably correct algorithms
From MaRDI portal
Publication:1695210
DOI10.1016/j.crma.2015.11.009zbMath1387.68315arXiv1509.00824OpenAlexW2963368828MaRDI QIDQ1695210
Publication date: 7 February 2018
Published in: Comptes Rendus. Mathématique. Académie des Sciences, Paris (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1509.00824
Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (5)
Probably certifiably correct \(k\)-means clustering ⋮ Fast certifiable relative pose estimation with gravity prior ⋮ On semidefinite relaxations for the block model ⋮ Scalable Low-Rank Semidefinite Programming for Certifiably Correct Machine Perception ⋮ Fast and robust certifiable estimation of the relative pose between two calibrated cameras
Cites Work
- Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
- High-dimensional analysis of semidefinite relaxations for sparse principal components
- Theory of semidefinite programming for sensor network localization
- Complementarity and nondegeneracy in semidefinite programming
- Exact Recovery in the Stochastic Block Model
- Relax, No Need to Round
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Sum-of-squares proofs and the quest toward optimal algorithms
- Compressed sensing
This page was built for publication: A note on probably certifiably correct algorithms