I am reading Low Rank Approximation in the Presence of Outliers by Bhaskara and Kumar and kind of stuck at the proof of Lemma 9. The paper studies robust (to outliers) low rank approximation problem. Given a matrix $A\in \mathbb{R}^{d\times n}$ ($n$ points in $\mathbb{R}^d$), the problem asks to find a decomposition $A=B+N$, where $N$ (outliers) can have at most $m$ non-zero columns such that the minimum rank-$k$ approximation (under Frobenius norm) of $B$ (inliers) is minimized over all such decomposition of $A$. In other words, given a point set $P$, parition this into $I$(inliers) and $O$(outliers) such that $\vert O\vert\leq m$ and cost of the best fit $k$-subspace of $I$ (sum of squared distance of $I$ to this subspace is minimized among all such $k$-subspace) is minimized among all such partition of $P$. I will be using the former terminology, conforming to the paper.
In section 4 of the aforementioned paper, they give a randomized approximation algorithm for the problem. I am interested in Lemma 6,8 and 9 of the paper.
Lemma 6 basically says that uniform random sampling we can find a $poly(k/\epsilon)$ dimensional space which covers a constant factor of the points, without the presence of outliers. More formally, let $S$ be a uniform random subset (without replacemet) of size $s\geq \frac{4k}{\epsilon^2}$ of $[n]$. Then with probability at least $\epsilon^2/8$ the following holds : there is a subset T of at least $\epsilon^2n/8$ columns of $A$ such that $\forall u\in T$, $\Vert u - proj_S(u)\Vert^2 \leq (1+\epsilon)\frac{\Vert A-A_k\Vert^2_F}{n}$. Here $proj_S(u)$ is the orthogonal projection of $u$ onto $span(S)$ and $A_k$ is the best rank-$k$ approximation of $A$.
Lemma 6 asserts only the existence of $T$ (even when there is no outliers). The next best thing is to choose the closest $\epsilon^2n/8$ columns of $A$ to $span(S)$. Let $X$ be this set of columns. Since $\vert X\vert \leq \vert T\vert$, it follows that
$\forall x\in X, \Vert x-proj_S(x)\vert^2 \leq \max_{u\in T}\Vert u - proj_S(u)\Vert^2 \leq (1+\epsilon)\frac{\Vert A-A_k\Vert^2_F}{n}$.
In presence of outliers, the situation is changed somewhat. Suppose $A=B+N$ is the optimal decomposition of $A$ and $B_k$ is best rank-$k$ approximation of $B$. We can assume that the columns of $B$ are arranged in increasing order in their squared distance from $B_k$. Let $Q$ be the first $\epsilon\vert B\vert$ columns of $B$. Of course we do not know $B$, we can not directly sample from $B$.
Lemma 8 says that if we sample enough columns from $A$, then with some probability we would sample at least $4k/\epsilon^2$ from $Q$ , so that we can apply Lemma 6, replacing $A$ of the lemma with $Q$. Since the success probability is only $\Omega(\epsilon^2)$, we repeat the sampling step $O(\log n/\epsilon^2)$ times to boost the success probability to $1-1/n^{O(1)}$. This is also true for any subset of columns of $A$.
This two lemma naturally gives rise to a recursive algorithm :
- START WITH $A$.
- APPLY LEMMA 8 (WHICH IMPLICITLY INVOKES LEMMA 6) AND LET $X^\star$ BE THE BEST AMONG $O(\log n/\epsilon^2)$ SAMPLING STEPS AND $S^\star$ BE ITS CORRESPONDING RANDOM SAMPLE. (meaning $\sum_{x\in X^\star}\Vert x - proj_{S^\star}(x)\Vert^2$ is minimum among all the sampling steps).
- MARK $X^\star$ AS COVERED AND REMOVE $X^\star$ FROM $A$ AND GO TO STEP 1(unless the number of columns left in $A$ is already small).
Lemma 9 analyze the above algorithm (the algorithm presented here is incomplete but gives the basic flavor, as it is not possible to find such a decomposition in polynomial time where there is exactly $m$ outliers, under some complexity theoretic conjecture. So some slack must be incorporated, see Algorithm 2 of the paper).
The basic idea that lemma 8 enables us to "cover" smallest (in terms of the optimal projection cost) $\epsilon$-fraction of the remaining inliers. Let $X_i^\star$ be the $X^\star$ in the $i$th recursive call and $S_i^\star$ be its corresponding sample and define $n^\prime = n-m$. Let $G_1$ be the first $\epsilon n^\prime$ columns of $B$, $G_2$ be the next $\epsilon(1-\epsilon)n^\prime$ columns, $G_3$ be the next $\epsilon(1-\epsilon)^2n^\prime$ columns and so on and $E_i = \sum_{p\in G_i}\Vert p-proj_{B_k}(x)\Vert^2$ is the projection cost of $G_i$. Recall that the columns of $B$ are arranged in increasing order in their squared distance from $B_k$.
Let us consider the first iteration of the above algorithm. By Lemma 6 and 8 we have that
$\forall x\in X_1^\star, \Vert x-proj_{S_1^\star}(x)\vert^2 \leq (1+\epsilon)\frac{E_1}{\vert G_1\vert}$.
Now the authors claim that "untill the algorithm marks $\epsilon n^\prime$ columns as covered, we have that average error in the marked columns is at most $(1+\epsilon)\frac{E_2}{\vert G_2\vert}$". I fail to understand this precise statement. I think what the authors meant is as follows: Let $I$ be the largest index such that $\vert \cup_{i=1}^I X_i^\star\vert \leq \epsilon n^\prime$. Then for $i=1,\cdots, I$
$\forall x\in X_i^\star, \Vert x-proj_{S_i^\star}(x) \Vert^2 \leq (1+\epsilon)\frac{E_2}{\vert G_2\vert}$.
Now if this statement is true (i am unable to prove this), then the total projection cost is bounded by $(1+\epsilon)\frac{\vert G_1\vert}{\vert G_2\vert}E_2 = \frac{1+\epsilon}{1-\epsilon}E_2$, which is what the authors want. The basic difficulty I am facing that the "remaining $\epsilon$-fraction of smallest inliers" depends on $X^\star$ and the author claim that whatever $X^\star$ be, till the point we remove at most $\epsilon n^\prime$ marked columns, the error remains bounded. I am more than sure I am missing something very trivial.
P.S. I am not sure whether this is the right platform to ask such elaborate question, but I have mailed the authors stating my doubts and awaiting a reply for quite some time. And I am not also sure what "tag" to put here. I would be immensely grateful if someone help me out here.
