  We study least-squares trace regression when the parameter is the sum of a
$r$-low-rank matrix and a $s$-sparse matrix and a fraction $\epsilon$ of the
labels is corrupted. For subgaussian distributions and feature-dependent noise,
we highlight three needed design properties, each one derived from a different
process inequality: a "product process inequality", "Chevet's inequality" and a
"multiplier process inequality". These properties handle, simultaneously,
additive decomposition, label contamination and design-noise interaction. They
imply the near-optimality of a tractable estimator with respect to the
effective dimensions $d_{eff,r}$ and $d_{eff,s}$ of the low-rank and sparse
components, $\epsilon$ and the failure probability $\delta$. The near-optimal
rate is $\mathsf{r}(n,d_{eff,r}) + \mathsf{r}(n,d_{eff,s}) +
\sqrt{(1+\log(1/\delta))/n} + \epsilon\log(1/\epsilon)$, where
$\mathsf{r}(n,d_{eff,r})+\mathsf{r}(n,d_{eff,s})$ is the optimal rate in
average with 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)$. Without matrix decomposition, our analysis also entails
optimal bounds for a robust estimator adapted to the noise variance. 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.
