Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances

MAP inference in Potts models underlies vision tasks such as stereo and segmentation. It is NP-hard, yet a standard LP relaxation solves real instances almost exactly. Earlier theory explained this only for perturbation-stable instances, which real data does not satisfy. We proved that the LP still approximately recovers the solution when a stable instance is corrupted by noise, and showed that real stereo-vision instances are close to stable ones.

I am co-first author with Hunter Lang.