Fixed-Parameter and Approximation Algorithms for PCA with Outliers

In this subsection we give the detailed proof of our hardness result, Theorem 1.5, which we restate here for convenience. Recall that ROBUST SUBSPACE RECOVERY is the special case of PCA WITH OUTLIERS where the task is to represent A exactly as the sum of a low-rank matrix and an outlier matrix. Theorem 1.5. There is no algorithm solving ROBUST SUB-SPACE RECOVERY in time f (d) • n o(d) for any computable function f of d, unless ETH fails. Proof. We show a reduction from CLIQUE. First, we need a set of points satisfying a certain generality condition. Definition 5.1. For d < n, let us say that a set W ⊂ R d of size n is in a forest-general position if for any forest F such that V (F ) ⊂ W and |E(F )| plus the number of isolated vertices in F is exactly d, the set is linearly independent and of size d. Note that this definition extends the common notion of vectors in a general linear position, which requires every d vectors to be linearly independent, since F can also be an empty forest on d vertices. The next claim extends the behavior in Definition 5.1 to forests of any size. Claim 4. If a set W ⊂ R d is in a forest-general position, for any forest F such that V (F ) ⊂ W , rank(vect(F )) = min(d, | vect(F )|). Proof. If | vect(F )| = d, the claim is by definition.