2026-07-24T05:02:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19598 2024-03-06T11:04:26Z ddc:004 open_access

A Combinatorial Approach to Robust PCA Kong, Weihao Qiao, Mingda Sen, Rajat Robust PCA Sparse Recovery Robust Statistics We study the problem of recovering Gaussian data under adversarial corruptions when the noises are low-rank and the corruptions are on the coordinate level. Concretely, we assume that the Gaussian noises lie in an unknown k-dimensional subspace U ⊆ ℝ^d, and s randomly chosen coordinates of each data point fall into the control of an adversary. This setting models the scenario of learning from high-dimensional yet structured data that are transmitted through a highly-noisy channel, so that the data points are unlikely to be entirely clean. Our main result is an efficient algorithm that, when ks² = O(d), recovers every single data point up to a nearly-optimal 𝓁₁ error of Õ(ks/d) in expectation. At the core of our proof is a new analysis of the well-known Basis Pursuit (BP) method for recovering a sparse signal, which is known to succeed under additional assumptions (e.g., incoherence or the restricted isometry property) on the underlying subspace U. In contrast, we present a novel approach via studying a natural combinatorial problem and show that, over the randomness in the support of the sparse signal, a high-probability error bound is possible even if the subspace U is arbitrary. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Weihao Kong and Mingda Qiao and Rajat Sen 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.70 urn:nbn:de:0030-drops-195984 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.70 eng https://creativecommons.org/licenses/by/4.0/legalcode