Corruption tolerant algorithms for signal recovery
In many signal recovery problems, data can be corrupted. For example, highly erroneous measurements can appear from occlusions, sensor failure, sensor saturation, and preprocessing steps. In these cases, signal estimation is challenging because the distribution of outliers is typically unknown a priori. In this talk, we will discuss corruption tolerant algorithms that arise in the phase retrieval problem from X-ray crystallography and from the location recovery problem from computer vision. In both of these problems, we will show that a convex program can provably succeed at recovering a synthetic signal exactly in the presence of data corruption. In the case of phase retrieval, we will see that a semidefinite program is robust to corruptions. In the case of location recovery, we will see that a novel second order cone problem can tolerate above 60% data corruption, enjoys a recovery guarantee, has good performance on real data, and can be computed several times faster than existing methods. The discussed works are in collaboration with Laurent Demanet, Vladislav Voroninski, Choongbum Lee, Thomas Goldstein, Stefano Soatto, and Konstantine Tsotsos.