A note on probably certifiably correct algorithms

DOI10.1016/j.crma.2015.11.009zbMath1387.68315arXiv1509.00824OpenAlexW2963368828MaRDI QIDQ1695210

Afonso S. Bandeira

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

Mathematics Subject Classification ID

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