Higher degree sum-of-squares relaxations robust against oblivious outliers. (arXiv:2211.07327v1 [cs.LG])

We consider estimation models of the form $Y=X^*+N$, where $X^*$ is some
$m$-dimensional signal we wish to recover, and $N$ is symmetrically distributed
noise that may be unbounded in all but a small $\alpha$ fraction of the
entries. We introduce a family of algorithms that under mild assumptions
recover the signal $X^*$ in all estimation problems for which there exists a
sum-of-squares algorithm that succeeds in recovering the signal $X^*$ when the
noise $N$ is Gaussian. This essentially shows that …

arxiv outliers squares