Outlier-robust sparse/low-rank least-squares regression and robust matrix completion

Outlier-robust estimation has been a topic studied for many decades since the seminal work by Huber [ 44 ]. One of the objectives of the field is to device estimators w hich are less sensitive to outlier sample contamination. The formalization of outlyingness and the construction of robust estimators matured in several directions. One common assumption is that the adver sary can only change a fraction ǫ of the original sample. For a extensive overview we refer, e.g., to Hampel et al. [ 42 ], Maronna et al. [ 61 ], Huber and Ronchenulli [ 45 ] and references therein. Within a verygeneralframework, the minimax optimality of severalrobust estimation problems have been recently obtained in a series of elegant works by Chen et al. [ 16, 17 ], Gao [ 40 ]. The construction, however, is based on Tukey's depth, a hard computational problem in higher dimensions. A recent trend of research, initiated by Diakonikolas et al. [ 32 ], Lai et al. [ 52 ], has focused in obtaining optimality of robust estimators within the class of computationally tractable algorithms. The oblivious model assumes the contamination is independent of the original sample.