is then to analyze the quality of the solution produced, ultimately leading to the following theorem.

\[thm:otp\] Fix $\epsilon \in (0,1]$. Suppose that there are $K \ge m$ 1-dim subspaces of $\mathbb{R}^m$ containing the columns $a^t$’s and that $B \ge \Omega\left(\frac{m}{\epsilon^3} \log \frac{K}{\epsilon}\right)$. Then algorithm [<span style="font-variant:small-caps;">OTP</span>]{}returns a feasible solution with expected value at least $(1 - 5\epsilon) {\ensuremath{\textrm{OPT}}}$.

Let $S = \{\sigma(1), \ldots, \sigma(\epsilon n)\}$ be the (random) index set of the columns sampled by [<span style="font-variant:small-caps;">OTP</span>]{}. We use $p^S$ to denote the optimal dual solution obtained by [<span style="font-variant:small-caps;">OTP</span>]{}; notice that $p^S$ is completely determined by $S$. To simplify the notation, we also use $x^S$ to denote $x(p^S)$.

Notice that, for all the scenarios where $x^S$ is feasible, the solution returned by [<span style="font-variant:small-caps;">OTP</span>]{}is identical to $x^S$ with its components $x^S_{\sigma(1)}, \ldots, x^S_{\sigma(\epsilon n)}$ set to zero. Given this observation and the fact that ${\mathbb{E}}[\sum_{t \leq \epsilon n} \pi_{\sigma(t)} x^S_{\sigma(t)}] \leq \epsilon {\ensuremath{\textrm{OPT}}}$, one can prove that the following lemma implies Theorem \[thm:otp\].

\[lemma:goodOtp\] Fix $\epsilon \in (0,1]$. Suppose that there are $K \ge m$ 1-dim subspaces of $\mathbb{R}^m$ containing the columns $a^t$’s and that $B \ge \Omega\left(\frac{m}{\epsilon^3} \log \frac{K}{\epsilon}\right)$. Then with probability at least $(1 - \epsilon)$, 