Robust Randomized Low-Rank Approximation with Row-Wise Outlier Detection
Journal:
arXiv
Published Date:
Apr 3, 2025
Abstract
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.
