Outlier-robust additive matrix decomposition and robust matrix completion
Philip Thompson (FGV EMAp)

We study least-squares trace regression when the parameter is the sum of a $r$-low-rank matrix with a $s$-sparse matrix and a fraction $\epsilon$ of the labels is corrupted. For subgaussian distributions, we highlight three needed design properties, each one derived from a different process inequality: the ``product process inequality'', ``Chevet's inequality'' and the ``multiplier process inequality''. Jointly, these properties entail the near-optimality of a tractable estimator with respect to the effective dimensions $d_{\textrm{eff},r}$ and $d_{\textrm{eff},s}$ for the low-rank and sparse components, $\epsilon$ and the failure probability $\delta$. The near-optimal rate has the form $\mathsf{r}(n,d_{\textrm{eff},r}) + \mathsf{r}(n,d_{\textrm{eff},s}) + \sqrt{(1+\log(1/\delta))/n}+ \epsilon\log(1/\epsilon)$. Here, $\mathsf{r}(n,d_{\textrm{eff},r})+\mathsf{r}(n,d_{\textrm{eff},s})$ is the optimal rate in average when there is no contamination. Our estimator is adaptive to $(s,r,\epsilon,\delta)$ and, for fixed absolute constant $c>0$, it attains the mentioned rate with probability $1-\delta$ uniformly over all $\delta\ge\exp(-cn)$. Disconsidering matrix decomposition, our analysis also entails optimal bounds for a robust estimator adapted to the noise variance. Finally, we consider robust matrix completion. We highlight a new property for this problem: one can robustly and optimally estimate the incomplete matrix regardless of the magnitude of the corruption. Our estimators are based on ``sorted'' versions of Huber's loss. We present simulations matching the theory. In particular, it reveals the superiority of ``sorted'' Huber's losses over the classical Huber's loss..