To achieve this guarantee, we make use of so-called lopsided embeddings. [1]} show that if a matrix \(S\)  is an \(\epsilon \)  lopsided embedding for \((V_k, (A(I-P))^\mathsf {T})\) , where \(V_k\)  is an orthonormal basis for the \(k\) -dimensional subspace that attains the cost \(\textnormal {SubApx}_{k,1}(A(I-P))\) , then \(\min _{\text{rank-}k\ X}\Vert A(I-P)S^\mathsf {T} X - A\Vert _{1,2} \le (1+\epsilon )\textnormal {SubApx}_{k,1}(A(I-P))\) . We first show that a Gaussian matrix \(\)  with \(O(k)\)  rows is an \(O(1)\)  lopsided embedding with probability \(\ge 9/10\) . Then we show that if a random matrix \(\)  is an \(O(1)\)  \(\ell _1\)  subspace embedding for the matrix \(A(I-P){}^\mathsf {T}\)  and satisfies \(_{}[\Vert M\Vert _{1,2}] = \Vert M\Vert _{1,2}\)  for any fixed matrix \(M\) , then the row space of \((A(I-P))\)  is an \(O(1)\)  approximation. We use the Lewis weight sampling algorithm of [2]} to sample a matrix \(\)  that satisfies these properties. As the matrix \({}^\mathsf {T}\) , which is a Gaussian matrix, has only \(O(k)\)  columns, the matrix \(\)  has only \(\tilde{O}(k)\)  rows. We can also instead use the \(\ell _1\)  subspace embeddings of [3]} to construct an \(\tilde{O}(k^{3.5})\) -sized \(\ell _1\)  embedding by leverage score sampling [4]}.
