Robust Randomized Low-Rank Approximation with Row-Wise Outlier Detection
This addresses the problem of robust data analysis for applications with corrupted data, though it is incremental as it builds on existing randomized and robust statistical techniques.
The paper tackles robust low-rank approximation under row-wise adversarial corruption by proposing a single-pass randomized algorithm that detects and removes outlier rows using thresholding on projected norms, achieving near-optimal error bounds and scaling linearly with observations.
Robust low-rank approximation under row-wise adversarial corruption can be achieved with a single pass, randomized procedure that detects and removes outlier rows by thresholding their projected norms. We propose a scalable, non-iterative algorithm that efficiently recovers the underlying low-rank structure in the presence of row-wise adversarial corruption. By first compressing the data with a Johnson Lindenstrauss projection, our approach preserves the geometry of clean rows while dramatically reducing dimensionality. Robust statistical techniques based on the median and median absolute deviation then enable precise identification and removal of outlier rows with abnormally high norms. The subsequent rank-k approximation achieves near-optimal error bounds with a one pass procedure that scales linearly with the number of observations. Empirical results confirm that combining random sketches with robust statistics yields efficient, accurate decompositions even in the presence of large fractions of corrupted rows.