2026-07-23T16:35:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9408 2024-03-06T10:44:19Z ddc:004 open_access

Low Rank Approximation in the Presence of Outliers Bhaskara, Aditya Kumar, Srivatsan Low rank approximation PCA Robustness to outliers We consider the problem of principal component analysis (PCA) in the presence of outliers. Given a matrix A (d x n) and parameters k, m, the goal is to remove a set of at most m columns of A (outliers), so as to minimize the rank-k approximation error of the remaining matrix (inliers). While much of the work on this problem has focused on recovery of the rank-k subspace under assumptions on the inliers and outliers, we focus on the approximation problem. Our main result shows that sampling-based methods developed in the outlier-free case give non-trivial guarantees even in the presence of outliers. Using this insight, we develop a simple algorithm that has bi-criteria guarantees. Further, unlike similar formulations for clustering, we show that bi-criteria guarantees are unavoidable for the problem, under appropriate complexity assumptions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aditya Bhaskara and Srivatsan Kumar 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.4 urn:nbn:de:0030-drops-94087 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.4 eng https://creativecommons.org/licenses/by/3.0/legalcode