The authors would like to thank support from the National Institute of Health (NIH) grant 5R01 HG 10798-2, Office of Naval Research (ONR) grant N00014-18-1-256, and a Simons Investigator Award.


Missing proofs from Section 
Theorem A.1 (A version of Lemma 14 of [1]}) 
Let \(P\)  be an \(r\)  dimensional subspace of \(^d\)  such that
\(\sum _i (a_i,P) - \sum _i (a_i,(P \cup H)) \le \frac{\epsilon ^2}{80}\textnormal {SubApx}_{k,1}(A)\) 
for all \(k\) -dimensional subspaces \(H\) . Let \(B \in ^{d \times r}\)  be an orthonormal basis for the subspace \(P\) . For each \(a_i\) , let \(a_i^B \in ^r\)  be such that
\((a_i, Ba_i^B) \le (1+\epsilon _c)(a_i,P)\) 
and let \((1-\epsilon _c)(a_i,P) \le _i \le (1+\epsilon _c)(a_i,P)\)  for \(\epsilon _c = \epsilon ^2/6\) . Then for any \(k\)  dimensional shape \(S\) ,
\(\sum _i \sqrt{(Ba_i^B,S)^2 + _i^2} = (1 \pm 5\epsilon )\sum _i (a_i,S)\) 

We have by the Pythagorean theorem that \((Ba_i^B,a_i)^2 = (Ba_i^B,\mathbb {P}_Pa_i)^2 + (a_i,P)^2 \le (1+3\epsilon _c)(a_i,P)^2\)  which implies that \((Ba_i^B,\mathbb {P}_Pa_i)^2 \le (3\epsilon _{c})(a_i,P)^2\) .
Given a shape \(S\) , we partition \([n]\)  into two sets small and large. We say \(i \in [n]\)  is small if
\((\mathbb {P}_Pa_i, S) \le (\mathbb {P}_Pa_i, Ba_i^B).\) 
In that case, \((Ba_i^B,S)^2 \le 4(\mathbb {P}_Pa_i, Ba_i^B)^2 \le 12\epsilon _c(a_i,P)^2\)  by the triangle inequality and \(\sqrt{(Ba_i^B,S)^2 + _i^2} \le \sqrt{1 + 15\epsilon _c}(a_i,P) \le \sqrt{1+15\epsilon _c}\sqrt{(a_i,P)^2 + (\mathbb {P}_Pa_i, S)^2}\) . Similarly, \(\sqrt{(Ba_i^B,S)^2 + _i^2} \ge _i \ge (1-\epsilon _c)(a_i,P) \ge (1-4\epsilon _c)\sqrt{(\mathbb {P}_Pa_i,S)^2 + (a_i, P)^2}\)  by using the fact that \((\mathbb {P}_Pa_i, S)^2 \le 3\epsilon _c(a_i,P)^2\) .
We say that any \(i \in [n]\)  that is not small, is large. By the triangle inequality, we obtain that
\((\mathbb {P}_Pa_i, S) - (\mathbb {P}_Pa_i, Ba_i^B) \le (Ba_i^B,S) \le (\mathbb {P}_Pa_i, S) + (Ba_i^B, \mathbb {P}_Pa_i).\) 
As \(i\)  is large, \((\mathbb {P}_Pa_i, S) - (\mathbb {P}_Pa_i, Ba_i^B) > 0\)  and therefore by the AM-GM inequality, we obtain that
\((Ba_i^B,S)^2 = (1 \pm \epsilon )(\mathbb {P}_Pa_i,S)^2 + \left(1 \pm \frac{1}{\epsilon }\right)(Ba_i^B,\mathbb {P}_Pa_i)^2.\) 
Thus,
\((Ba_i^B,S)^2 \le (1+\epsilon )(\mathbb {P}_Pa_i,S)^2 + ({2}/{\epsilon })(3\epsilon _c)(a_i,P)^2\) 
and
\((Ba_i^B,S)^2 \ge (1 - \epsilon )(\mathbb {P}_Pa_i,S)^2 - ({1}/{\epsilon })(3\epsilon _c)(a_i,P)^2.\) 
Letting \(\epsilon _c = \epsilon ^2/6\) , we finally have
\((Ba_i^B,S)^2 + _i^2 \le (1+\epsilon )(\mathbb {P}_Pa_i,S)^2 + (1 + 2\epsilon )(a_i,P)^2\) 
and
\((Ba_i^B,S)^2 + _i^2 \ge (1-\epsilon )(\mathbb {P}_Pa_i,S)^2 + (1 - 3\epsilon )(a_i,P)^2.\) 
Therefore, by combining both small and large indices,
\(\sum _i \sqrt{(Ba_i^B,S)^2 + _i^2} \le \sqrt{1+O(\epsilon )}\sum _i \sqrt{(\mathbb {P}_Pa_i,S)^2 +(a_i,P)^2}\) 
and
\(\sum _i \sqrt{(Ba_i^B,S)^2 + _i^2} \ge \sqrt{1-O(\epsilon )}\sum _i \sqrt{(\mathbb {P}_Pa_i,S)^2 +(a_i,P)^2}.\) 
The theorem now follows from Theorem 8 of [1]}.

Missing Proofs from Section 
Lopsided Embeddings and Gaussian Matrices
Recall \(\Vert \cdot \Vert _h\)  is defined as \(\Vert A\Vert _h = \sum _j \Vert A_{*j}\Vert _2\) . Note that \(\Vert A\Vert _h = \Vert A^\mathsf {T}\Vert _{1,2}\)  for all matrices \(A\) . The following lemma shows that lopsided-\(\epsilon \)  embeddings for certain matrices w.r.t. the norm \(\Vert \cdot \Vert _h\)  imply a dimension reduction for \(\Vert \cdot \Vert _{1,2}\)  subspace approximation.
Lemma B.1 Given a matrix \(A \in ^{n \times d}\)  and a parameter \(k \in \mathbb {Z}_{> 0}\) , let \(U_k \in ^{n \times k}\)  and \(V_k^\mathsf {T} \in ^{k \times d}\)  be matrices such that
\(\Vert U_kV_k^\mathsf {T} - A\Vert _{1,2} = \min _{\text{rank-}k\ X}\Vert A(I-X)\Vert _{1,2}.\) 
If \(S\)  is a lopsided \(\epsilon \) -embedding for \((V_k, A^\mathsf {T})\)  with respect to the norm \(\Vert \cdot \Vert _h\) , then
\(\min _{\text{rank-}k\ X}\Vert AS^\mathsf {T}X - A\Vert _{1,2} \le (1+O(\epsilon ))\min _{\text{rank-k}\ X}\Vert A(I-X)\Vert _{1,2}.\) 

Note that \(\Vert V_kU_k^\mathsf {T} - A^\mathsf {T}\Vert _h = \min _{Y}\Vert V_kY^\mathsf {T} - A^\mathsf {T}\Vert _h\) . By definition of a lopsided embedding, we have the following for any matrix \(Y\) :
\(\Vert YV_k^\mathsf {T}S^\mathsf {T} - AS^\mathsf {T}\Vert _{1,2} = \Vert SV_kY^\mathsf {T} - SA^\mathsf {T}\Vert _h \ge (1-\epsilon )\Vert V_kY^\mathsf {T} - A^\mathsf {T}\Vert _h = (1-\epsilon )\Vert YV_k^\mathsf {T} - A\Vert _{1,2}\) 
and also that
\(\Vert U_kV_k^\mathsf {T}S^\mathsf {T} - AS^\mathsf {T}\Vert _{1,2} = \Vert SV_kU_k^\mathsf {T} - SA^\mathsf {T}\Vert _h \le (1+\epsilon )\Vert V_kU_k^\mathsf {T} - A^\mathsf {T}\Vert _h = (1+\epsilon )\Vert U_kV_k^\mathsf {T} - A\Vert _{1,2}.\) 
Using these guarantees we now show that the column span of the matrix \(AS^\mathsf {T}\)  contains a good solution to the subspace approximation problem. First consider the minimization problem
\(\min _{Y}\Vert YV_k^\mathsf {T} - A\Vert _{1,2}.\) 
Clearly, \(U_k\)  is the optimal solution to the problem. Now consider the optimal solution \(\tilde{Y}\)  to the sketched version of the above problem
\(\tilde{Y} = _{Y}\Vert YV_k^\mathsf {T}S^\mathsf {T} - AS^\mathsf {T}\Vert _{1,2}.\) 

We can see that \(\tilde{Y} = (AS^\mathsf {T})(V_k^\mathsf {T}S^\mathsf {T})^+\) . Now
\(\Vert \tilde{Y}V_k^\mathsf {T} - A\Vert _{1,2} \le \frac{1}{1-\epsilon }\Vert \tilde{Y}V_k^\mathsf {T}S^\mathsf {T} - AS^\mathsf {T}\Vert _{1,2} \le \frac{1}{1-\epsilon }\Vert U_KV_k^\mathsf {T}S^\mathsf {T} - AS^\mathsf {T}\Vert  \le \frac{1+\epsilon }{1-\epsilon }\Vert U_kV_k^\mathsf {T} - A\Vert _{1,2}.\) 
Therefore,
\(\min _{\text{rank-k}\ X}\Vert AS^\mathsf {T}X - A\Vert _{1,2} \le \Vert AS^\mathsf {T}(V_k^\mathsf {T}S^\mathsf {T})^+(V_k^\mathsf {T}) - A\Vert _{1,2} \le \frac{1+\epsilon }{1-\epsilon }\Vert U_kV_k^\mathsf {T} - A\Vert _{1,2} \le (1+3\epsilon )\min _{\text{rank-}k\ X}\Vert A(I-X)\Vert _{1,2}.\) 
Thus, if the number of rows of \(S\)  is less than \(d\) , we obtain a dimension reduction for \(\Vert \cdot \Vert _{1,2}\)  subspace approximation.

[3]} give the following sufficient conditions for a distribution of matrices to be an \(\epsilon \) -lopsided embedding for \((A,B)\) . For the sake of completeness we reproduce their proof here.
Lemma B.2 (Sufficient Conditions) 
Given matrices \((A,B)\) , let \(\)  be a matrix drawn from a distribution such that

the matrix \(\)  is a subspace \(\epsilon \) -contraction for \(A\)  with respect to \(\Vert \cdot \Vert _2\) , i.e., simultaneously for all vectors \(x\)
\(\Vert Ax\Vert _2 \ge (1-\epsilon )\Vert Ax\Vert _2\) 
with probability \(1-\delta /3\) ,

for all \(i \in [d^{\prime }]\) , with probability at least \(1-\delta \epsilon ^2/3\)  the matrix \(\)  is a subspace \(\epsilon ^2\) -contraction for \([A\ B_{*i}]\)  with respect to \(\Vert \cdot \Vert _2\) , i.e., for all vectors \(x\) ,
\(\Vert Ax - B_{*i}\Vert _2 \ge (1-\epsilon ^2)\Vert Ax-B_{*i}\Vert _2,\) 
and

the matrix \(\)  is an \(\epsilon ^2\) -dilation for \(B^*\)  with respect to \(\Vert \cdot \Vert _h\) , i.e., \(\Vert B^*\Vert _h \le (1+\epsilon ^2)\Vert B^*\Vert _h\)  with probability \(\ge 1 - \delta /3\) .

In the Condition 3 above, \(B^* = AX^*-B\)  where \(X^* = _{X}\Vert AX-B\Vert _h\) . With failure probability at most \(\delta \) , the matrix \(\)  is an affine \(6\epsilon \) -contraction for \((A,B)\)  with respect to \(\Vert \cdot \Vert _h\) , i.e., for all matrices \(X\) ,
\(\Vert (AX-B)\Vert _h \ge (1- 6\epsilon )\Vert AX-B\Vert _h\) 
and therefore a lopsided \(6\epsilon \) -embedding for \((A,B)\)  with respect to \(\Vert \cdot \Vert _h\) .

Importantly, note that Condition 2 in the lemma is about the probability of \(\)  being a subspace contraction for \([A\, B_{*i}]\)  separately for each \(i\)  and not the probability of \(\)  being simultaneously a subspace contraction for \([A\, B_{*i}]\)  for all \(i \in [d^{\prime }]\) .

Condition on the event that 1 and 3 hold. For \(i \in [d^{\prime }]\) , let \(_i\)  be an indicator random variable where \(_i = 0\)  if the matrix \(\)  is a subspace \(\epsilon ^2\) -contraction for \([A\ B_{*i}]\)  and \(_i = 1\)  otherwise. From the properties of \(\) , we have that \(\Pr [_i = 1] \le \delta \epsilon ^2/3\)  for all \(i\) . If \(_i = 1\) , we call \(i\)  bad and if \(_i = 0\) , we call \(i\)  good.
Consider an arbitrary matrix \(X\) . Say a bad \(i\)  is large if \(\Vert (AX-B)_{*i}\Vert _2 \ge (1/\epsilon )(\Vert B_{*i}\Vert _2 + \Vert B_{*i}\Vert _2)\) , otherwise a bad \(i\)  is small. We have
\(\sum _{\text{\emph {small}}\ i} \Vert (AX-B)_{*i}\Vert _2 \le (1/\epsilon )\sum _{\text{\emph {small}}\ i}\Vert B_{*i}\Vert _2 + \Vert B_{*i}\Vert _2 \le (1/\epsilon )\sum _{\text{\emph {bad}}\ i}\Vert B_{*i}\Vert _2 + \Vert B_{*i}\Vert _2.\) 
Using condition 2, we obtain that \([\sum _{\text{\emph {bad}}\ i}\Vert B^*_{*i}\Vert _2] \le (\delta \epsilon ^2/3)\sum _{i}\Vert B_{*i}^*\Vert _2 \le (\delta \epsilon ^2/3)\Delta ^*\) . By a Markov bound, we have that with probability \(\ge 1 - \delta /3\) , \(\sum _{\text{\emph {bad}}\ i}\Vert B_{*i}^*\Vert  \le \epsilon ^2\Delta ^*\) . Assume that this event holds. Similarly,
\(\sum _{\text{\emph {bad}}\ i}\Vert B_{*i}^*\Vert _2 &= \Vert B^*\Vert _h - \sum _{\text{\emph {good}}\ i}\Vert B^*_{*i}\Vert _2\\&\le (1+\epsilon ^2)\Delta ^* - (1-\epsilon ^2)\sum _{\text{\emph {good}}\ i}\Vert B_{*i}^*\Vert _2\\&\le (1+\epsilon ^2)\Delta ^* - (1-\epsilon ^2)(\Delta ^* - \epsilon ^2\Delta ^*)\\&\le 3\epsilon ^2\Delta ^*.\) 

Thus, we can bound the RHS of (REF ) and obtain
\(\sum _{\text{\emph {small}}\ i} \Vert (AX-B)_{*i}\Vert _2 \le (1/\epsilon )(\epsilon ^2\Delta ^* + 3\epsilon ^2\Delta ^*) \le 4\epsilon \Delta ^*.\) 
Now we lower bound \(\sum _{\text{\emph {bad}}\ i} \Vert (AX-B)_{*i}\Vert _2\) .
\(\sum _{\text{\emph {bad}}\ i}\Vert (AX-B)_{*i}\Vert _2 &\ge \sum _{\text{\emph {large}}\ i}\Vert (AX-B)_{*i}\Vert _2\\&\ge \sum _{\text{\emph {large}}\ i}\Vert (AX-AX^*)_{*i}\Vert _2 - \Vert B^*_{*i}\Vert _2\\&\ge \sum _{\text{\emph {large}}\ i}(1-\epsilon )\Vert (AX-AX^*)_{*i}\Vert _2- \Vert B^*_{*i}\Vert _2\\&\ge \sum _{\text{\emph {large}}\ i}(1-\epsilon )\Vert (AX-B)_{*i}\Vert _2- (1-\epsilon )\Vert B_{*i}^*\Vert _2 - \Vert B^*_{*i}\Vert _2\\&\ge \sum _{\text{\emph {large}}\ i}(1-\epsilon )\Vert (AX-B)_{*i}\Vert _2 - \epsilon \Vert (AX-B)_{*i}\Vert _2\\&\ge (1-2\epsilon )\sum _{\text{\emph {large}}\ i}\Vert (AX-B)_{*i}\Vert _2.\) 

In the above, we repeatedly used the triangle inequality for the \(\Vert \cdot \Vert _2\)  norm, and that \(\)  is a subspace \(\epsilon \) -embedding for matrix \(A\)  and for large \(i\) , we upper bound \((1-\epsilon )\Vert B^*_{*i}\Vert _2 + \Vert B^*_{*i}\Vert _2\)  by \(\epsilon \Vert (AX-B)_{*i}\Vert _2\) . We can finally lower bound \(\Vert (AX-B)\Vert _h\) .
\(\Vert (AX-B)\Vert _h &= \sum _{\text{\emph {good}}\ i}\Vert (AX-B)_{*i}\Vert _2 + \sum _{\text{\emph {bad}}\ i}\Vert (AX-B)_{*i}\Vert _2\\&\ge (1-\epsilon ^2)\sum _{\text{\emph {good}}\ i}\Vert (AX-B)_{*i}\Vert _2 + (1-2\epsilon )\sum _{\text{\emph {large}}\ i}\Vert (AX-B)_{*i}\Vert _2\\&\ge (1-\epsilon ^2)\sum _{\text{\emph {good}}\, i}\Vert (AX-B)_{*i}\Vert _2 + (1-2\epsilon )\sum _{\text{\emph {bad}}\, i}\Vert (AX-B)_{*i}\Vert _2\\&\quad - (1-2\epsilon )\sum _{\text{\emph {small}}\, i}\Vert (AX-B)_{*i}\Vert _2\\&\ge (1-2\epsilon )\Vert AX-B\Vert _h - (1-2\epsilon )4\epsilon \Delta ^*\\&\ge (1-6\epsilon )\Vert AX-B\Vert _h.\) 

Thus, by a union bound, with failure probability \(\le \delta \) , \(\)  is an affine \(6\epsilon \) -contraction for \((A,B)\)  with respect to \(\Vert \cdot \Vert _h\) .
Lemma B.3 (Gaussian Matrices are Lopsided Embeddings) 
Given arbitrary matrices \(A\)  of rank \(k\)  and \(B\)  of any rank, a Gaussian matrix \(\)  with \(\tilde{O}(k/\epsilon ^4 + 1/\epsilon ^4\delta ^2)\)  rows is an \(\epsilon \) -lopsided embedding for \((A,B)\)  with probability \(\ge 1 - \delta \) .

We now show that a Gaussian matrix, with small dimension equal to \(\tilde{O}(k/\epsilon ^4 + 1/\epsilon ^4\delta ^2)\) , satisfies all of the sufficient conditions of Lemma REF . Clearly, a Gaussian matrix with \(O((k + \log (1/\delta ))/\epsilon ^2)\)  rows satisfies condition 1 and a Gaussian matrix with \(O((k + \log (1/\delta \epsilon ))/\epsilon ^4)\)  rows satisfies condition 2 [4]}.
We now show that a Gaussian matrix with at least \(O(1/\epsilon ^4)\)  rows satisfies
\([(\Vert y\Vert _2^2 - 1)^2] \le \epsilon ^4\) 
for any given unit vector \(y\) . If \(\)  is a Gaussian matrix of \(t\)  rows with each entry drawn i.i.d. from \(N(0,1/t)\) , then the entries of \(Sy\)  are each drawn i.i.d. from \(N(0,\Vert y\Vert _2^2/t) = N(0,1/t)\) . Therefore, \(\Vert y\Vert _2^2 = _1^2 + \ldots + _{t}^2\) , where \(_i \sim N(0,1/t)\) , which gives
\([(\Vert y\Vert _2^2 - 1)^2] &= [(_1^2 + \ldots + _t^2 - 1)^2]\\&= t[_1^4] + 1 + 2\binom{t}{2}[_1^2_2^2] - 2t[_1^2] = t\frac{3}{t^2} + 1 + 2\binom{t}{2}\frac{1}{t^2} - 2t\frac{1}{t}\\&= 2/t.\) 

Thus, with \(t \ge 1/\epsilon ^4\) , we have that \([(\Vert y\Vert _2^2 - 1)^2] \le \epsilon ^4\) . By Lemma 28 of [3]}, we obtain that \([\max (\Vert y\Vert _2^4,1)] \le (1+\epsilon ^2)^2 \le 1+3\epsilon ^2\) . Now, by Holder's inequality,
\([\max (\Vert y\Vert _2,1)] \le [\max (\Vert y\Vert _2,1)^4]^{1/4} \le (1+3\epsilon ^2)^{1/4} \le 1 + (3/4)\epsilon ^2.\) 
As \((\Vert y\Vert _2 - 1)_+ = \max (\Vert y\Vert _2,1)-1\) , we obtain that \([(\Vert y\Vert _2 - 1)_+] \le (3/4)\epsilon ^2\) , which implies by scaling that for an arbitrary vector \(y\) ,
\([(\Vert y\Vert _2 - \Vert y\Vert _2)_+] \le (3/4)\epsilon ^2\Vert y\Vert _2\) 
which gives
\([(\Vert B^*\Vert _h - \Vert B^*\Vert _h)_+] &\le (3/4)\epsilon ^2\Vert B^*\Vert _h.\) 

By Markov's inequality, with probability \(\ge 1 - \delta /3\) , \((\Vert B^*\Vert _h - \Vert B^*\Vert _h)_+ \le (9/4)(\epsilon ^2/\delta )\Vert B^*\Vert _h\)  and hence,
with probability \(\ge 1 - \delta /3\) , \(\Vert B^*\Vert _h \le (1+(9/4)(\epsilon ^2/\delta ))\Vert B^*\Vert _h\) . Thus, a Gaussian matrix with \(m = O(1/\epsilon ^4\delta ^2)\)  rows satisfies that with probability \(\ge 1 - \delta /3\)  that
\(\Vert B^*\Vert _h \le (1+\epsilon ^2)\Vert B^*\Vert _h.\) 

Utilizing Sampling based \(\ell _1\)  embeddings
Let \(A\)  be a matrix that has \(r\)  columns. Suppose \(\)  is a random matrix such that with probability \(\ge 9/10\) , simultaneously for all vectors \(y\) ,
\(\alpha \Vert Ay\Vert _1 \le \Vert Ay\Vert _1 \le \beta \Vert Ay\Vert _1.\) 
Assume the above event holds. Let \(X\)  be an arbitrary matrix with \(t\)  columns. We have that for a suitably scaled Gaussian matrix \(\)  with \(\tilde{O}(t/\epsilon ^2)\)  columns, with probability \(\ge 9/10\) , simultaneously for all vectors \(x \in ^t\) , \(\Vert x^{\mathsf {T}}\Vert _1 = (1 \pm \epsilon )\Vert x\Vert _2\)  [6]}. Thus there exists a matrix \(M\)  with \(\tilde{O}(t/\epsilon ^2)\)  columns such that for all vectors \(x \in ^t\) ,
\(\Vert x^\mathsf {T}M\Vert _1 = (1 \pm \epsilon )\Vert x\Vert _2.\) 
Therefore,
\(\frac{1}{1+\epsilon }\Vert AXM\Vert _{1,1} \le \Vert AX\Vert _{1,2} = \frac{1}{1-\epsilon }\Vert AXM\Vert _{1,1}\) 
and
\(\frac{1}{1+\epsilon }\Vert AXM\Vert _{1,1} \le \Vert AX\Vert _{1,2} \le \frac{1}{1-\epsilon }\Vert AXM\Vert _{1,1}\) 
Now we upper bound \(\Vert AX\Vert _{1,2}\) .
\(\Vert AX\Vert _{1,2} &\le \frac{1}{1-\epsilon }\Vert AXM\Vert _{1,1} \le \frac{1}{1-\epsilon }\sum _{j}\Vert A(XM)_{*j}\Vert _1\\&\le \frac{\beta }{1-\epsilon }\sum _j\Vert A(XM)_{*j}\Vert _1 = \frac{\beta }{1-\epsilon }\Vert AXM\Vert _{1,1} \le \beta \frac{1+\epsilon }{1-\epsilon }\Vert AX\Vert _{1,2}.\) 

We now lower bound \(\Vert AX\Vert _{1,2}\)  similarly.
\(\Vert AX\Vert _{1,2} &\ge \frac{1}{1+\epsilon }\Vert AXM\Vert _{1,1} = \frac{1}{1+\epsilon }\sum _j \Vert A(XM)_{*j}\Vert _1\\&\ge \frac{\alpha }{1+\epsilon }\sum _j \Vert A(XM)_{*j}\Vert _1 = \frac{\alpha }{1+\epsilon }\Vert AXM\Vert _{1,1} \ge \alpha \frac{1-\epsilon }{1+\epsilon }\Vert AX\Vert _{1,2}.\) 

By picking appropriate \(\epsilon \) , we conclude that for any matrix \(X\) ,
\(\frac{\alpha }{2}\Vert AX\Vert _{1,2} \le \Vert AX\Vert _{1,2} \le 2\beta \Vert AX\Vert _{1,2}.\) 
Lemma B.4 If \(^\mathsf {T}\)  is a random Gaussian matrix with \(O(k)\)  columns such that with probability \(\ge 9/10\) ,
\(\min _{\text{rank-}k\ X}\Vert A^\mathsf {T}X - A\Vert _{1,2} \le (3/2)\min _{\text{rank-}k\ X}\Vert AX - A\Vert _{1,2},\) 
and if \(\)  is a random matrix drawn from a distribution such that with probability \(\ge 9/10\)  over the draw of matrix \(\) ,
\(\alpha \Vert A^\mathsf {T}y\Vert _{1} \le \Vert A^\mathsf {T}y\Vert _{1} \le \beta \Vert A^\mathsf {T}y\Vert _1\) 
for all vectors \(y\)  and
\(_[\Vert M\Vert _{1,2}] = \Vert M\Vert _{1,2}\) 
for any matrix \(M\) , then with probability \(\ge 3/5\) , all matrices \(X\)  such that \(\Vert A^\mathsf {T}X - A\Vert _{1,2} \le 10\cdot \textnormal {SubApx}_{k,1}(A)\)  satisfy
\(\Vert A^\mathsf {T} X - A\Vert _{1,2} \le \left(2 + 40/\alpha \right)\textnormal {SubApx}_{k,1}(A).\) 

Let \(X_1 = _{\text{rank-}k\ X}\Vert A^\mathsf {T}X - A\Vert _{1,2}\) . With probability \(\ge 9/10\) , we have that \(\Vert A^\mathsf {T} X_1 - A\Vert _{1,2} \le (3/2)\text{SubApx}_{k,1}(A)\) . By a Markov bound, we obtain that with probability \(\ge 4/5\) , \(\Vert A^\mathsf {T} X_1 - A\Vert _{1,2} \le 10\textnormal {SubApx}_{k,1}(A)\) . Assume this event holds.
For any matrix \(X\) ,
\(\Vert A^\mathsf {T}X - A\Vert _{1,2} \ge \Vert A^\mathsf {T}X - A^\mathsf {T}X_1\Vert _{1,2} - \Vert A^\mathsf {T}X_1 - A\Vert _{1,2}.\) 
We have
\(\Vert A^\mathsf {T}X - A\Vert _{1,2} \ge \Vert A^\mathsf {T}X - A^\mathsf {T}X_1\Vert _{1,2} - 10\cdot \textnormal {SubApx}_{k,1}(A).\) 
From (REF ), we have
\(\Vert A^\mathsf {T}X - A\Vert _{1,2} &\ge \frac{\alpha }{2}\Vert A^\mathsf {T}X - A^\mathsf {T}X_1\Vert _{1,2} - 10\cdot \textnormal {SubApx}_{k,1}(A)\\&\ge \frac{\alpha }{2}\Vert A^\mathsf {T}X - A\Vert _{1,2}-\frac{\alpha }{2}\Vert A^\mathsf {T}X_1 - A\Vert _{1,2} - 10 \cdot \textnormal {SubApx}_{k,1}(A)\\&\ge \frac{\alpha }{2}\Vert A^\mathsf {T}X - A\Vert _{1,2} - (3\alpha /4 + 10)\cdot \textnormal {SubApx}_{k,1}(A).\) 

Thus, for any matrix \(X\)  of rank \(r\) , if \(\Vert A^\mathsf {T} X - A\Vert _{1,2} > (2/\alpha )(20 + 3\alpha /4)\cdot \textnormal {SubApx}_{k,1}(A)\) , then \(\Vert A^\mathsf {T}X - A\Vert _{1,2} > 10\cdot \textnormal {SubApx}_{k,1}(A)\) .

Main Theorem for constructing an \((O(1),\tilde{O}(k))\) -bicriteria solution
Theorem B.1 Given any matrix \(A \in ^{n \times d}\)  and a matrix \(B \in ^{d \times c_1}\)  with orthonormal columns, Algorithm REF  returns a matrix \(\hat{X}\)  with \(\tilde{O}(k)\)  orthonormal columns that with probability \(1-\delta \)  satisfies
\(\Vert A(I-BB^\mathsf {T})(I - \hat{X}\hat{X}^\mathsf {T})\Vert _{1,2} \le O(1) \cdot \textnormal {SubApx}_{k,1}(A(I-BB^\mathsf {T})),\) 
in time \(\tilde{O}(((A) + d(k/\epsilon ))\log (1/\delta ))\) .

It is shown in Lemma REF  that a Gaussian matrix with \(O(k)\)  rows is a \(1/6\) -lopsided embedding for \((V_k,A^\mathsf {T})\)  with probability \(\ge 9/10\) . Thus by Lemma REF , we obtain that
\(\min _{\text{rank-}k\ X}\Vert A(I-BB^\mathsf {T})^\mathsf {T}X - A(I-BB^\mathsf {T})\Vert _{1,2} \le (3/2)\text{SubApx}_{k,1}(A(I-BB^\mathsf {T}))\) 
with probability \(\ge 9/10\) . [7]} show that a sampling matrix \(\)  obtained using Lewis weights has \(\tilde{O}(k)\)  rows and is a \((1/2,3/2)\)  \(\ell _1\)  subspace embedding for the matrix \(A(I-BB^\mathsf {T})^\mathsf {T}\) . Thus, the matrices \(^\mathsf {T}\)  and \(\)  constructed in Algorithm REF  satisfy the conditions of Lemma REF . Therefore from Lemma REF , with probability \(\ge 3/5\) , if a matrix \(X\)  satisfies
\(\Vert A(I-BB^\mathsf {T})^\mathsf {T}X - A(I-BB^\mathsf {T})\Vert _{1,2} \le 10\cdot \text{SubApx}_{k,1}(A(I-BB^\mathsf {T})),\)  then \(\Vert A(I-BB^\mathsf {T})^\mathsf {T}X - A(I-BB^\mathsf {T})\Vert _{1,2} \le 82 \cdot \text{SubApx}_{k,1}(A(I-BB^\mathsf {T}))\) .
Let \(\tilde{X} = _{\text{rank-}k\ X}\Vert A(I-BB^\mathsf {T})^\mathsf {T} X - A(I-BB^\mathsf {T})\Vert _{1,2}\) . We have \(\Vert A(I-BB^\mathsf {T})^\mathsf {T}\tilde{X} - A(I-BB^\mathsf {T})\Vert _{1,2} \le (3/2)\text{SubApx}_{k,1}(A(I-BB^\mathsf {T}))\) . By Markov's bound, with probability \(\ge 3/4\) , \(\Vert A(I-BB^\mathsf {T})^\mathsf {T}\tilde{X} - A(I-BB^\mathsf {T})\Vert _{1,2} \le 10 \cdot \text{SubApx}_{k,1}(A(I-BB^\mathsf {T}))\) . We now have the following:
\(\Vert A(I-BB^\mathsf {T})^\mathsf {T}\tilde{X}(A(I-BB^\mathsf {T}))^+A(I-BB^\mathsf {T}) - A(I-BB^\mathsf {T})\Vert _{1,2} \le 10 \cdot \text{SubApx}_{k,1}(A(I-BB^\mathsf {T})).\) 
Thus
\(\Vert A(I-BB^\mathsf {T})^\mathsf {T}\tilde{X}(A(I-BB^\mathsf {T}))^+A(I-BB^\mathsf {T}) - A(I-BB^\mathsf {T})\Vert _{1,2} \le 82 \cdot \text{SubApx}_{k,1}(A(I-BB^\mathsf {T})).\) 
Finally,
\(&\Vert A(I-BB^\mathsf {T})(A(I-BB^\mathsf {T}))^+(A(I-BB^\mathsf {T})) - A(I-BB^\mathsf {T})\Vert _{1,2}\\&\le \Vert A(I-BB^\mathsf {T})^\mathsf {T}\tilde{X}(A(I-BB^\mathsf {T}))^+A(I-BB^\mathsf {T}) - A(I-BB^\mathsf {T})\Vert _{1,2}\\&\le 82\cdot \text{SubApx}_{k,1}(A(I-BB^\mathsf {T})).\) 

The first inequality follows from the fact that for all \(x\)  and \(y\) , \(\Vert x^\mathsf {T}(A)^{+}(A) - x^\mathsf {T}\Vert _2 \le \Vert y^\mathsf {T}(A)^+(A) - x^\mathsf {T}\Vert _2\) .
By a union bound, with probability \(\ge 1/2\) , the matrix \(\hat{X}\)  computed by Algorithm REF , which is an orthonormal basis for the rowspace of \(A(I-BB^\mathsf {T})\) , satisfies
\(\Vert A(I-BB^\mathsf {T})(I - \hat{X}\hat{X}^\mathsf {T})\Vert _{1,2} \le 82 \cdot \text{SubApx}_{k,1}(A(I-BB^\mathsf {T})).\) 
Thus the matrix \(\hat{X}\)  which has the minimum value over \(\tilde{O}(\log (1/\delta ))\)  trials satisfies with probability \(\ge 1 - \delta \)  that
\(\Vert A(I-BB^\mathsf {T})(I - \hat{X}\hat{X}^\mathsf {T})\Vert _{1,2} \le O(1) \cdot \text{SubApx}_{k,1}(A(I-BB^\mathsf {T})).\) 
The running time of Lewis weight sampling can be seen to be \(O(((A)+k^2d(c_1 + k))\log (\log (n)))\)  from [7]}. Thus, the total running time is \(\tilde{O}(((A) + k^2d(c_1 + k))\log (1/\delta ))\) .

Finding Best Solution Among Candidate Solutions
Algorithm REF  finds candidate solutions \(\hat{X}^{(1)},\ldots ,\hat{X}^{(t)}\)  for \(t = O(\log (1/\delta ))\)  and returns the best candidate solution that minimizes the cost
\(\Vert A(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _{1,2}.\) 
The proof of Theorem REF  shows that, for all \(i=1,\ldots ,t\) , with probability \(\ge 3/5\) , \(\Vert A(I-BB^\mathsf {T})(I-\hat{X}^{(i)}(\hat{X}^{(i)})^\mathsf {T})\Vert _{1,2} \le O(1) \cdot \text{SubApx}_{k,1}(A(I-BB^\mathsf {T}))\) . Therefore with probability \(\ge 1 - \delta /2\)
\(\min _{i}\Vert A(I-BB^\mathsf {T})(I-\hat{X}^{(i)}(\hat{X}^{(i)})^\mathsf {T})\Vert _{1,2} \le O(1) \cdot \text{SubApx}_{k,1}(A(I-BB^\mathsf {T}))\) 
i.e., with probability \(\ge 1 - \delta \) , there is a solution \(\hat{X}^{(i)}\)  among the \(t\)  potential solutions that has a cost at most \(O(1) \cdot \text{SubApx}_{k,1}(A(I-BB^\mathsf {T}))\) . We first compute
\(\text{apx}_i = \Vert A(I-BB^\mathsf {T})(I-\hat{X}^{(i)}(\hat{X}^{(i)})^\mathsf {T})\Vert _{1,2}\) 
where \(\)  is a scaled Gaussian matrix with \(O(\log (n/\delta ))\)  columns. Values of \(\text{apx}_j\)  for all \(j \in [t]\)  can be computed in time \(\tilde{O}(((A) + (n+d)(k/\epsilon ))\cdot \log (1/\delta ))\) .
We have using the union bound that, with probability \(\ge 1 - \delta /2\) , for all \(j \in [n]\)  and \(i \in [t]\)  that
\(\Vert A_{j*}(I-BB^\mathsf {T})(I-\hat{X}^{(i)}(\hat{X}^{(i)})^\mathsf {T})\Vert _2 = (1/2,3/2) \Vert A_{j*}(I-BB^\mathsf {T})(I-\hat{X}^{(i)}(\hat{X}^{(i)})^\mathsf {T})\Vert _2.\) 
Therefore with probability \(\ge 1 - \delta /2\) , for all \(i \in [t]\) ,
\(_i \in (1/2,3/2)\Vert A(I-BB^\mathsf {T})(I-\hat{X}^{(i)}(\hat{X}^{(i)})^\mathsf {T})\Vert _{1,2}.\) 
Let \(\tilde{i} = _{i \in [t]}_i\)  and \(i^* = _{i \in [t]}\Vert A(I-BB^\mathsf {T})(I-\hat{X}^{(i)}(\hat{X}^{(i)})^\mathsf {T})\Vert _{1,2}\) . By a union bound, with probability \(\ge 1 - \delta \)
\(\Vert A(I-BB^\mathsf {T})(I-\hat{X}^{(\tilde{i})}(\hat{X}^{(\tilde{i})})^\mathsf {T})\Vert _{1,2} &\le 2_{\tilde{i}}\\&\le 2_{i^*}\\&\le 4\Vert A(I-BB^\mathsf {T})(I-\hat{X}^{(i^*)}(\hat{X}^{(i^*)})^\mathsf {T})\Vert _{1,2}\\&\le O(1) \cdot \text{SubApx}_{k,1}(A(I-BB^\mathsf {T})).\) 

Thus, Algorithm REF , with probability \(\ge 1 - \delta \) , returns a subspace that has cost at most \(O(\sqrt{k}) \cdot \text{SubApx}_{k,1}(A(I-BB^\mathsf {T}))\)  and has a running time of \(\tilde{O}(((A) + (n+d)(k/\epsilon )) \cdot \log (1/\delta ))\) .

Main Theorem for Constructing a \((1+\varepsilon , k^{3.5}/\varepsilon ^2)\)  Bicriteria Solution
Theorem B.2 (Residual Sampling) 
Given matrix \(A \in \mathbb {R}^{n \times d}\) , matrices \(B \in \mathbb {R}^{d\times c_1}\)  and \(\hat{X} \in ^{d \times c_2}\)  with orthonormal columns such that
\(\Vert A(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _{1,2} \le K\cdot \textnormal {SubApx}_{1,k}(A(I-BB^\mathsf {T})),\) 
Algorithm REF  returns a matrix \(U\)  having \(c = \tilde{O}(c_2 + K \cdot k^3/\epsilon ^2\cdot \log (1/\delta ))\)  orthonormal columns such that with probability \(\ge 1 - \delta \)
\(\Vert A(I-BB^\mathsf {T})(I-UU^\mathsf {T})\Vert _{1,2} \le (1+\epsilon )\textnormal {SubApx}_{1,k}(A(I-BB^\mathsf {T})) \) 
in time \(\tilde{O}((A) + d \cdot (k/\epsilon ))\) . Moreover we also have that \(U^\mathsf {T}B = 0\) , i.e., the column spaces of \(U\)  and \(B\)  are orthogonal to each other.

As the matrix \(G\)  is a Gaussian matrix with \(t = O(\log (n/\delta ))\)  columns, we have that with probability \(\ge 1 - (\delta /2)\) , for all \(i \in [n]\) ,
\(\Vert M_{i*}\Vert _2 = \Vert A_{i*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})G\Vert _2 = (1 \pm 1/10)\Vert A_{i*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})G\Vert _2.\) 
Therefore, the probabilities \(p_i\)  computed by Algorithm REF  are such that
\(p_i = \frac{\Vert M_{i*}\Vert _2}{\Vert M\Vert _{1,2}} \ge \frac{(9/10)\Vert A_{i*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _{2}}{(11/10)\Vert A(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _{1,2}} \ge \frac{9}{11}\frac{\Vert A_{i*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _{2}}{\Vert A(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _{1,2}}.\) 
Hence, by applying Lemma REF  to the matrix \(A(I-BB^\mathsf {T})\) , we obtain that with probability \(\ge 1-\delta \) , the matrix \(U\)  returned by Algorithm REF  satisfies
\(\Vert A(I-BB^\mathsf {T})(I-UU^\mathsf {T})\Vert _{1,2} \le (1+\epsilon )\text{SubApx}_{1,k}(A(I-BB^\mathsf {T})).\) 
The matrix \(M\)  can be computed in time \(O((A)\log (n/\delta ) + (c_1 + c_2)d\log (n/\delta ))\) . And \(s = \tilde{O}(K \cdot k^3/\epsilon ^2 \cdot \log (1/\delta ))\)  independent samples can be drawn from the distribution \(p\)  in time \(O(n + s)\) . Finally, the orthonormal basis \(U\)  can be computed in time \(O(d(c+c_1)^2) = O(d(k/\epsilon ))\) .

Missing Proofs from Section 
Lemma C.1 With probability \(\ge 2/3\) , Algorithm  finds an \(\tilde{O}(k^{3}/\epsilon ^3)\) -dimensional subspace \(S\)  such that for all \(k\) -dimensional subspaces \(W\) ,
\(\Vert A(I-\mathbb {P}_S)\Vert _{1,2}-\Vert A(I-\mathbb {P}_{S+W})\Vert _{1,2}\le 4\epsilon \cdot \textnormal {SubApx}_{k,1}(A).\) 

Suppose that the loop in Algorithm  is run for all \(t = 10/\epsilon + 1\)  iterations instead of stopping after \(i^*\)  iterations. Let \(\hat{X}_i,U_i,B_i\)  be the values of the matrices in the algorithm at the end of \(i\)  iterations. Let \(B_0 = []\)  be the empty matrix. Condition on the event that all the calls to Algorithm REF  in the algorithm succeed. By a union bound over the failure event of each call to Algorithm REF , this event holds with probability \(\ge 9/10\) . Therefore, by Theorem REF , we obtain that
\(& \Vert A(I-\mathbb {P}_{B_{i-1}})(I - \mathbb {P}_{\hat{X}_i})\Vert _{1,2}\\& \le \tilde{O}(\sqrt{k}) \cdot \text{SubApx}_{k,1}(A(I-\mathbb {P}_{B_{i-1}}))\) 

for all \(i \in [10/\epsilon +1]\)  and also that \(\hat{X}_i\)  has \(\tilde{O}(k)\)  columns. Now we condition on the event that all the calls to Algorithm REF  succeed. By a union bound, this holds with probability \(\ge 9/10\) . Thus we have
\(&\Vert A(I-\mathbb {P}_{B_i})\Vert _{1,2} = \Vert A(I-\mathbb {P}_{B_{i-1}})(I - \mathbb {P}_{U_i})\Vert _{1,2}\\&\le (1+\epsilon ) \cdot \text{SubApx}_{k,1}(A(I-\mathbb {P}_{B_{i-1}}))\) 

for all iterations \(i \in [10/\epsilon +1]\)  and also that \(U_i\)  has \(\tilde{O}(k^{3}/\epsilon ^2)\)  columns which implies that \(B_i\)  has \(\tilde{O}(ik^{3}/\epsilon ^2)\)  columns. In particular, we have that \(\Vert A(I-\mathbb {P}_{B_1})\Vert _{1,2} \le (1+\epsilon )\text{SubApx}_{k,1}(A)\) . Therefore
\(&(1+\epsilon )\text{SubApx}_{k,1}(A) - \Vert A(I-\mathbb {P}_{B_t})\Vert _{1,2}\\&\ge \Vert A(I-\mathbb {P}_{B_1})\Vert _{1,2} - \Vert A(I-\mathbb {P}_{B_t})\Vert _{1,2}\\&=\sum _{i=2}^\mathsf {T} \Vert A(I-\mathbb {P}_{B_{i-1}})\Vert _{1,2} - \Vert A(I-\mathbb {P}_{B_i})\Vert _{1,2} \ge 0.\) 

The last inequality follows from the fact that \(\text{colspace}(B_i) \supseteq \text{colspace}(B_{i-1})\) . The summation in the above equation has \(10/\epsilon \)  non-negative summands that all sum to at most \((1+\epsilon )\text{SubApx}_{k,1}(A)\) . Therefore, at least \(9/\epsilon \)  summands have value \(\le \epsilon (1+\epsilon )\text{SubApx}_{k,1}(A)\) . In particular, with probability \(\ge 9/10\) ,
\(\Vert A(I-\mathbb {P}_{B_{i^*}})\Vert _{1,2} - \Vert A(I-\mathbb {P}_{B_{i^*+1}})\Vert _{1,2} \le \epsilon (1+\epsilon )\text{SubApx}_{k,1}(A).\) 
But we also have that
\(\Vert A(I-\mathbb {P}_{B_{i^*+1}})\Vert _{1,2} &= \Vert A(I - \mathbb {P}_{B_{i^*}})(I-\mathbb {P}_{U_{i^*}})\Vert _{1,2}\\&\le (1+\epsilon )\text{SubApx}_{k,1}(A(I-\mathbb {P}_{B_{i^*}}))\\&\le (1+\epsilon )\Vert A(I - \mathbb {P}_{B_{i^*}})(I-\mathbb {P}_{W})\Vert _{1,2}\\&=(1+\epsilon )\Vert A(I - \mathbb {P}_{B_{i^*} + W})\Vert _{1,2}\) 

where \(W\)  is any rank \(k\)  matrix. The second inequality follows from the fact that \(\text{SubApx}_{k,1}(A(I-\mathbb {P}_{B_{i^*}})) = \min _{\text{rank-}k\, W}\Vert A(I-\mathbb {P}_{B_{i^*}})(I-\mathbb {P}_W)\Vert _{1,2}\) . Therefore, for any rank-\(k\)  matrix \(W\) , we obtain that
\(&\Vert A(I-\mathbb {P}_{B_{i^*}})\Vert _{1,2} - \Vert A(I-\mathbb {P}_{B_{i^*} \cup W})\Vert _{1,2}\\&\le \Vert A(I-\mathbb {P}_{B_{i^*}})\Vert _{1,2} - \frac{1}{1+\epsilon }\Vert A(I-\mathbb {P}_{B_{i^*+1}})\Vert _{1,2}\\&\le \Vert A(I-\mathbb {P}_{B_{i^*}})\Vert _{1,2} - (1-\epsilon )\Vert A(I-\mathbb {P}_{B_{i^*+1}})\Vert _{1,2}\\&\le (\Vert A(I-\mathbb {P}_{B_{i^*}})\Vert _{1,2} - \Vert A(I-\mathbb {P}_{B_{i^*+1}})\Vert _{1,2}) + \epsilon \Vert A(I-\mathbb {P}_{B_{i^*+1}})\Vert _{1,2}\\&\le 4\epsilon \cdot \text{SubApx}_{k,1}(A).\) 
Theorem C.1 Given a matrix \(A \in ^{n \times d}\) , \(k \in \mathbb {Z}\)  and an accuracy parameter \(\epsilon > 0\) , Algorithm  returns a matrix \(B\)  with \(\tilde{O}(k^{3}/\epsilon ^6)\)  orthonormal columns and a matrix \(\text{Apx} = [X\, v]\)  such that for any \(k\)  dimensional shape \(S\) ,
\(\sum _i \sqrt{(BX_{i*}^\mathsf {T}, S)^2 + v_i^2} = (1 \pm \varepsilon )\sum _i (A_i, S).\) 
The algorithm runs in time \(O({(A)}/\epsilon ^2 + (n+d)(k/\epsilon ))\) .

From the above lemma, we have that the subspace \(B\)  satisfies with probability \(\ge 9/10\) , that for any \(k\)  dimensional subspace \(W\) ,
\(\Vert A(I-\mathbb {P}_B)\Vert _{1,2} - \Vert A(I-\mathbb {P}_{B \cup W})\Vert _{1,2} \le \frac{\varepsilon ^2}{80}\text{SubApx}_{k,1}(A).\) 
From Theorem 2.10 of [4]}, we obtain that with probability \(\ge 9/10\) , for all \(i \in [n]\) , the matrix \(_j\)  found for \(i \in [n]\)  is such that \(_j\)  is a \(\Theta (\epsilon ^2)\)  subspace embedding for the matrix \([B\, A_{i*}^\mathsf {T}]\) . Therefore, \(x_i\)  is such that
\(\Vert Bx_{i} - A_{i*}^\mathsf {T}\Vert _2 \le (1 + \Theta (\epsilon ^2))\Vert (I-BB^\mathsf {T})A_{i*}^\mathsf {T}\Vert _2.\) 
and
\(v_i = (1 \pm \Theta (\epsilon ^2))\Vert (I-BB^\mathsf {T})A_{i*}^\mathsf {T}\Vert _2\) . Now the proof follows from Theorem REF .

Missing Proofs from Section 
Obtaining an \((O(1),(k))\)  Approximation
[t]
PolyApproxDense


Input: \(A\in ^{n\times d}\) , \(B \in ^{d \times c_1}\) , \(k \in \mathbb {Z}, \delta , b\) 
Output: \(\hat{X} \in ^{d \times c_2}\) 
\(\text{cols} \leftarrow O(k + 1/\delta ^2)\) 
\(^\mathsf {T} \leftarrow \mathcal {N}(0,1)^{d \times \text{cols}}\) 
\(\leftarrow \)  \(\ell _1\)  embedding for \(O(k)\)  dimensions from [10]}
\([Q,R] \leftarrow \)  QR decomposition of \((A)(I-BB^\mathsf {T})^\mathsf {T}\) 
\(I_1,\ldots ,I_b \leftarrow \)  Equal size partition of \([n]\)  into \(b\)  parts
\(_1 \leftarrow \)  Cauchy matrix with \(O(\log (n))\)  rows
\(j = 1,\ldots ,b\) 
\(M^{(j)} \leftarrow (_1A_{I_j})(I-BB^\mathsf {T})^\mathsf {T}R^{-1}\) 
\(_j \leftarrow \sum _{\text{col} \in \text{cols}(M^{(j)})}\text{median}(\text{abs}(M^{(j)}_{*\text{col}}))\) 
\(\leftarrow \)  Cauchy matrix with \(O(\log (n))\)  columns
\(\text{samples} \leftarrow \tilde{O}(k^{3.5})\) 
\(\leftarrow []\) 
\(\text{samples}\)  iterations
Sample \(j \in [b]\)  with probability proportional to \(_j\) 
\(P^{(j)} \leftarrow A_{I_j}(I-BB^\mathsf {T})^\mathsf {T}R^{-1}\) 
For \(i \in I_j\) , \(p^{(j)}_i \leftarrow \text{median(abs($P^{(j)}_{i*}$))}\) 
Sample \(i \in I_j\)  with probability proportional to \(p^{(j)}_i\) 
Append \(\frac{1}{\frac{p_i^{(j)}}{\sum _{i \in I(j)}p_i^{(j)}}\frac{_j}{\sum _{j=1}^b _j}\cdot \text{samples}}e_i^\mathsf {T}\)  to matrix \(\) 
\(\hat{X} \leftarrow \)  Orthonormal Basis for rowspace(\(A(I - BB^\mathsf {T})\) )
Repeat the above O(\(\log (1/\delta )\) ) times and return best \(\hat{X}\)
Theorem D.1 Given \(A \in ^{n \times d}\) , \(B \in ^{d \times c_1}\) , \(k \in \mathbb {Z}\)  and \(\delta \) , Algorithm REF  returns \(\hat{X}\)  with \(\tilde{O}(k^{3.5})\)  orthonormal columns that with probability \(1-\delta \)  satisfies
\(\Vert A(I-BB^\mathsf {T})(I - \hat{X}\hat{X}^\mathsf {T})\Vert _{1,2}\le O(1) \cdot \textnormal {SubApx}_{k,1}(A(I-BB^\mathsf {T})).\) 
Given that the matrices \(_1A_{I_j}\)  for all \(j \in [b]\)  and \(A\)  are precomputed for all \(O(\log (1/\delta ))\)  trials, the algorithm can be implemented in time \(\tilde{O}(((nd/b)\cdot k^{3.5} + d(k/\epsilon ))\log (1/\delta ))\) .

The proof is similar to proof of Theorem REF . That proof only makes use of the facts that

for any fixed matrix \(M\) , \([\Vert M\Vert _{1,2}] = [\Vert M\Vert _{1,2}]\) ,

with probability \(\ge 9/10\) , for all vectors \(x\) , \((1/2)\Vert Ax\Vert _1 \le \Vert Ax\Vert _1 \le (3/2)\Vert Ax\Vert _1\) , and

to conclude with the statement in the theorem. We now show that the matrix \(\)  computed by Algorithm REF  satisfies all the above three properties.
Note that the random matrix \(\)  is constructed by sampling \(N\)  rows, where each row is independently equal to \((1/Np_i)e_i^\mathsf {T}\)  with probability \(p_i\) . Thus
\([\Vert M\Vert _{1,2}] = [\sum _{i=1}^N \Vert _{i*}M\Vert _2] = N[\Vert _{1*}M\Vert _2] = N\sum _{j=1}^n\Vert (1/Np_j)e_j^\mathsf {T}M\Vert _2p_j = \sum _{j=1}^n \Vert M_{j*}\Vert _2 = \Vert M\Vert _{1,2}.\) 
We now prove property 2. From Theorem 1.3 of [10]}, we have that \(\)  has \(O(k\log (k))\)  rows and that with probability \(\ge 99/100\) , for all vectors \(x\)
\(\Vert A(I-BB^\mathsf {T})^\mathsf {T}x\Vert _1 \le \Vert A(I-BB^\mathsf {T})^\mathsf {T}x\Vert _1 \le O(k\log (k))\Vert A(I-BB^\mathsf {T})^\mathsf {T}x\Vert .\) 
Let \(\ell _i = \Vert A_{i*}(I-BB^\mathsf {T})^\mathsf {T} R^{-1}\Vert _1\)  for \(i \in [n]\) . From Theorem REF , if the probability that the \(i^\textnormal {th}\)  row is sampled is \(\ge (1/2)(\ell _i/\sum _{i^{\prime }} \ell _{i^{\prime }})\)  for all \(i \in [n]\) , then the matrix \(\)  constructed is a \((1/2,3/2)\)  \(\ell _1\) -subspace embedding with probability \(\ge 99/100\) . Now consider sampling a row of the matrix \(\)  in the algorithm. We have that the sampled row is in the direction of \(e_i\)  with probability \((_{j(i)}/\sum _{j^{\prime } \in [b]}_{j^{\prime }}) \cdot (p_{i}^{j(i)}/\sum _{i^{\prime } \in I_{j(i)}}p_{i^{\prime }}^{j(i)})\) . We use \(j(i)\)  to denote \(j \in [b]\)  such that \(i \in I_j\) . We show that this probability is at least \((1/2)(\ell _i/\sum _{i^{\prime }}\ell _{i^{\prime }})\) . For \(j \in [b]\) ,
\(_j = \sum _{\text{col}}\text{median}(\text{abs}(M^{(j)}_{*\text{col}})).\) 
From Theorem 1 of [12]}, we have with probability \(\ge 1 - 1/100b\)  that
\(\text{median}(\text{abs}(M^{(j)}_{*\text{col}})) = (1 \pm 1/6)\Vert A_{I_j}(I-BB^\mathsf {T})^\mathsf {T}R^{-1}_{*\text{col}}\Vert _1.\) 
Thus \(\sum _{\text{col}}\text{median}(\text{abs}(M^{(j)}_{*\text{col}})) = (1 \pm 1/6)\sum _{\text{col}}\Vert A_{I_j}(I-BB^\mathsf {T})^\mathsf {T}R^{-1}_{*\text{col}}\Vert _1 = (1 \pm 1/6)\sum _{i \in I_j}\Vert A_{i*}(I-BB^\mathsf {T})^\mathsf {T}R^{-1}\Vert _{1} = (1 \pm 1/6)\sum _{i \in I_j}\ell _i\) . Therefore, by a union bound, with probability \(\ge 99/100\) , for all \(j \in [b]\)
\(_j = (1 \pm 1/6)\sum _{i \in I_j}\ell _i.\) 
Again, from [12]}, we obtain that with probability \(\ge 99/100\) , that for all \(i \in [n]\)
\(\text{median}(\text{abs}(A_{i*}(I-BB^\mathsf {T})^\mathsf {T} R^{-1})) = (1 \pm 1/6)\Vert A_{i*}(I-BB^\mathsf {T})^\mathsf {T} R^{-1}\Vert _1 = (1 \pm 1/6)\ell _i.\) 
Thus, with probability \(\ge 99/100\) , for all \(j\)  and \(i \in I_j\) , we have \(p^{(j)}_{(i)} = (1 \pm 1/6)\ell _i\) . By a union bound, with probability \(\ge 98/100\) , the probability that an arbitrary row \(i\)  is sampled in an iteration of the algorithm is
\((_{j(i)}/\sum _{j^{\prime } \in [b]}_{j^{\prime }}) \cdot (p_{i}^{j(i)}/\sum _{i^{\prime } \in I_{j(i)}}p_{i^{\prime }}^{j(i)}) \ge \frac{5}{7}\frac{\sum _{i^{\prime } \in I_j}\ell _{i^{\prime }}}{\sum _{i^{\prime }\in [n]}\ell _{i^{\prime }}}\frac{5}{7}\frac{\ell _i}{\sum _{i^{\prime }\in I_j}\ell _{i^{\prime }}} \ge \frac{1}{2}\frac{\ell _i}{\sum _{i^{\prime }\in [n]}\ell _{i^{\prime }}}.\) 
Thus by a union bound, \(\)  is a \((1/2,3/2)\)  subspace embedding. Now the proof and argument for the running time follow.

Obtaining a \((1+\epsilon ,(k/\epsilon ))\)  Solution
EpsApproxDense


Input: \(A\in ^{n\times d}\) , \(B \in ^{d \times c_1}\) , \(\hat{X} \in ^{d \times c_2}\) , \(k \in \mathbb {Z}, K, \epsilon , \delta , b\) 
Output: \(U \in ^{d \times c}\) 
\(t \leftarrow O(\log (n))\) , \(\leftarrow \mathcal {N}(0,1)^{d \times \text{cols}}\) 
\(I_1,\ldots ,I_b \leftarrow \)  Equal size partition of \([n]\)  into \(b\)  parts
\(_1 \leftarrow \)  Cauchy matrix with \(O(\log (n))\)  rows
\(j = 1,\ldots ,b\) 
\(M^{(j)} \leftarrow (_1A_{I_j})(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})(/t)\sqrt{\pi /2}\) 
\(_j \leftarrow \sum _{\text{col} \in \text{cols}(M^{(j)})}\text{median}(\text{abs}(M^{(j)}_{*\text{col}}))\) 
\(\text{samples} \leftarrow \tilde{O}(K \cdot k^3/\epsilon ^2 \cdot \log (1/\delta ))\) , \(\leftarrow \varnothing \) 
samples iterations
Sample \(j \in [b]\)  with probability proportional to \(_j\) 
\(P^{(j)} \leftarrow A_{I_j}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\) 
For \(i \in I_j\) , \(p^{(j)}_i \leftarrow \Vert P^{(j)}_{i*}\Vert _2\) 
Sample \(i \in I_j\)  with probability proportional to \(p^{(j)}_i\) 
\(\leftarrow \cup i\) 
\(U \leftarrow \text{colspan}((I-BB^\mathsf {T})[\hat{X}\, (A_{})^\mathsf {T}])\) 
Return \(U\)
Theorem D.2 Given a matrix \(A \in ^{n \times d}\) , orthonormal matrices \(B \in ^{n \times c_1}\)  and \(\hat{X} \in ^{n \times c_2}\)  such that
\(\Vert A(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _{1,2} \le K \cdot \text{SubApx}_{1,k}(A(I-BB^\mathsf {T})),\) 
and parameters \(k\) , \(\epsilon \) , and \(\delta \) , Algorithm REF  outputs a matrix \(U\)  with \(c = c_1 + \tilde{O}(K \cdot k^3/\epsilon ^2 \cdot \log (1/\delta ))\)  orthonormal columns such that with probability \(\ge 1 - \delta \) ,
\(\Vert A(I-BB^\mathsf {T})(I-UU^\mathsf {T})\Vert _{1,2} \le (1+\epsilon )\text{SubApx}_{1,k}(A(I-BB^\mathsf {T})).\) 
Given that \(_1 A_{I_j}\)  is precomputed for all \(j \in [b]\) , the algorithm runs in time \(\tilde{O}((nd/b) \cdot (K \cdot k^{3}/\epsilon ^2 \log (1/\delta )) + d(k/\epsilon ))\) .

We show that the probability that a row \(i\)  is sampled in an iteration of the Algorithm is \(\ge (1/12)\Vert A_{i*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _2/\Vert A(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _{1,2}\) . Then the proof follows as in the proof of Theorem REF . First assume that \(_j\)  for \(j \in [b]\)  computed by the algorithm satisfies
\(_j = (1/2,2) \sum _{i \in I_j}\Vert A_{j*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _2.\) 
Now the probability \(p_i\)  with which a row \(i\)  is sampled by the algorithm is given by
\(p_i = \frac{_{j(i)}}{\sum _{j \in [b]}_j} \cdot \frac{\Vert A_{i*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _2}{\sum _{i^{\prime } \in I_{j(i)}}\Vert A_{i^{\prime }*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _{2}}.\) 
As \(\)  is a Gaussian matrix with \(t = O(\log (n/\delta ))\)  columns, we have that with probability \(\ge 1 - \delta \)  that for all \(i^{\prime } \in [n]\)  \(\Vert A_{i^{\prime }*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _2 = (1 \pm 1/2)\Vert A_{i^{\prime }*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _2 \cdot \sqrt{t}\) . Therefore
\(p_i&= \frac{_{j(i)}}{\sum _{j \in [b]}_j} \cdot \frac{\Vert A_{i*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _2}{\sum _{i^{\prime } \in I_{j(i)}}\Vert A_{i^{\prime }*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _{2}}\\&\ge \frac{1}{12} \frac{\Vert A_{i*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _2}{\Vert A(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _{1,2}}.\) 

We now prove our assumption which concludes the proof.
Let \(x \in ^d\)  be an arbitrary vector. As \(\)  is a Gaussian matrix with \(t = O(\log (n/\delta ))\)  columns, Lemma 5.3 of [14]} states that
\(\Pr \left[\left|\frac{1}{t}\Vert x^\mathsf {T}G\Vert _1 - \sqrt{\frac{2}{\pi }}\Vert x\Vert _2\right| \ge \alpha \Vert x\Vert _2\right] \le C\exp (-ct\alpha ^2).\) 
Picking an appropriate \(\alpha = O(1)\) , by a union bound, with probability \(\ge 1 - \delta /3\) , we obtain
\(& \Vert {A_{i*}}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})(G/t)\sqrt{\pi /2}\Vert _1\\&= (4/5,6/5)\Vert A_{i*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _2\) 

for all \(i \in [n]\) .
Now, if \(C\)  is a Cauchy matrix with \(O(\log (n/\delta ))\)  rows, then with probability \(1 - \delta /(3nb)\) , we have that
\(\text{median}(\text{abs}(Cx)) = (1 \pm 1/5)\Vert x\Vert _1.\) 
Therefore, by a union bound, we obtain that, with probability \(\ge 1 -\delta /3\) , for all \(j \in [b]\)  and \(i \in t\)  that
\(\text{median}(\text{abs}(CA_{I_j*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})_{*i})) = (1 \pm 1/5)\Vert A_{I_j*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})_{*i}\Vert _1.\) 
Therefore, with probability \(\ge 1 - 2\delta /3\) , for all \(j \in [b]\) ,
\(_j &= \sum _{i}\textnormal {median}(\textnormal {abs}((M^{(j)})_{*i})) =\sum _{i=1}^\mathsf {T} \text{median}(\text{abs}(CA_{I_j*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})(_{*i}/t)\sqrt{\pi /2}))\\&= (1 \pm 1/5)\sum _{i=1}^\mathsf {T}\Vert A_{I_j*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})(_{*i}/t)\sqrt{\pi /2}\Vert _1\\&= (1 \pm 1/5)\sum _{i \in I_j}\Vert A_{i*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})(/t)\sqrt{\pi /2}\Vert _1\\&= (4/5,6/5)(4/5,6/5)\sum _{i \in I_j}\Vert A_{i*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _2\\&= (1/2,2)\sum _{i \in I_j}\Vert A_{i*}(I-BB^\mathsf {T})(I-\hat{X}\hat{X}^\mathsf {T})\Vert _2.\) 

The only term in the running time that involves a factor \(nd\)  is in computing the matrix \(P^{(j)}\)  for the chosen \(j\) . A total of \(\tilde{O}(K \cdot k^{3}/\varepsilon ^2 \cdot \log (1/\delta ))\)  such \(j \in [b]\)  are sampled. Therefore, the total running time for computing the matrices \(P^{(j)}\)  for \(j\)  sampled by the algorithm is equal to \((nd/b) \cdot \log (n) \cdot \tilde{O}(K \cdot k^{3}/\varepsilon ^2 \cdot \log (1/\delta )) + d \cdot (k/\epsilon )\) .

Overall Algorithm
[t]
DimensionReductionDense


Input: \(A\in ^{n\times d}\) , \(k, \epsilon >0\) .
Output: \(B \in ^{d \times c}\)  with orthonormal columns
\(t \leftarrow 10/\varepsilon + 1\) 
\(i^* \leftarrow \)  uniformly random integer from \([10/\epsilon +1]\) .
Initialize \(B \leftarrow []\) 
\(b \leftarrow k^{3.5}/\epsilon ^3\) 
\(\delta = \Theta (\epsilon )\) 
\(i = 1,\ldots ,i^*\)
\(\hat{X} \leftarrow \)  PolyApproxDense\((A,B,k,\delta , b)\) .
\(U \leftarrow \)  EpsApproxDense\((A,B,\hat{X},k, \tilde{O}(\sqrt{k}), \Theta (\epsilon ),\delta , b)\) .
\(B \leftarrow [B\, |\, U ]\) .
Return \(B\) .
Lemma D.1 Given matrix \(A \in ^{n \times d}, k \in \mathbb {Z}\)  and \( \epsilon > 0\) , Algorithm REF  returns a matrix \(B\)  with \(\tilde{O}(k^{3.5}/\epsilon ^3)\)  orthonormal columns such that, with probability \(\ge 3/5\) , for all \(k\)  dimensional spaces \(W\) ,
\(\Vert A(I-\mathbb {P}_{B})\Vert _{1,2} - \Vert A(I-\mathbb {P}_{B \cup W})\Vert _{1,2} \le \epsilon \cdot \text{SubApx}_{k,1}(A).\) 
The Algorithm runs in time \(\tilde{O}(nd + (n+d)(k/\epsilon ))\) .

The proof of the lemma is similar to that of Lemma REF . We now argue that all the pre-computed matrices required across all the iterations of the algorithm can be computed in time \(\tilde{O}(nd)\) . The Cauchy matrix \(_1\)  used in Algorithm REF  has \(O(\log (n))\)  rows and the matrix \(\)  has \(\tilde{O}(k)\)  rows. Note that we have
\(\begin{bmatrix}_1A_{I_1}\\ _1A_{I_2}\\ \\ _1A_{I_b}\\ A\end{bmatrix} = \begin{bmatrix}_1 & & & & \\& _1 & & & \\& & & &\\& & & & _1\\& & & &\end{bmatrix}A.\) 
Thus all the matrices required for Algorithm REF  can be computed by multiplying a \((k/\epsilon ) \times n\)  matrix with \(A\) . Similarly, we can compute all the matrices required for Algorithm REF  by computing the product of a \((k/\epsilon ) \times n\)  matrix with \(A\) . Thus, all the matrices required across all iterations of Algorithm REF  can be computed by multiplying a \((k/\epsilon ) \times n\)  matrix with \(A\) , which can be done in time \(\tilde{O}(nd)\)  by the algorithm of [15]}, assuming \(n \gg (k/\epsilon )\) . Now each iteration of the loop in Algorithm REF  takes \(\tilde{O}((nd/b)k^{3.5}/\epsilon ^2 + (n+d)(k/\epsilon ))\)  time. As there are \(O(1/\epsilon )\)  iterations, the algorithm runs in time \(\tilde{O}((nd/b)k^{3.5}/\epsilon ^3 + (n+d)(k/\epsilon ))\) . Since the value of \(b\)  is chosen to be \(k^{3.5}/\epsilon ^3\) , we obtain that the running time of the algorithm is \(\tilde{O}(nd + (n+d)(k/\epsilon ))\) , including the time to compute the required pre-computed matrices.

Coreset Construction using Dimensionality Reduction
Algorithm  gives the general algorithm to construct a coreset for any objective involving the sum-of-distances metric. In this section, we discuss the coreset construction for two such problems: the \(k\) -median and \(k\) -subspace approximation problems.

CoresetConstruction


Input: \(A \in ^{n \times d}\) , \(k\) , \(\epsilon \) 
Output: Coreset
\((B, \text{Apx}) \leftarrow \textsc {CompleteDimReduce}(A,k,\epsilon )\) 
Construct a coreset for the instance \(\text{Apx}\begin{bmatrix}B^\mathsf {T} & 0\\0 & 1\end{bmatrix}\)  and return
For \((B,\text{Apx}=[X\, v])\)  returned by Algorithm , we have the guarantee that, with probability \(\ge 9/10\) , for any \(k\) -dimensional shape \(S\) ,
\(\sum _{i}\sqrt{(BX_{i*}^\mathsf {T}, S)^2 + v_i^2} = (1 \pm \epsilon )\sum _{i}(A_{i*},S).\) 
Given a set \(S\) , let \(S_{+1}\)  denote the set \(\lbrace (s,0)\,|\, s\in S\rbrace \) . Let \(\text{diag}(B^\mathsf {T}, 1) = \begin{bmatrix}B^\mathsf {T} & 0\\0 & 1\end{bmatrix}\) . Using this notation, we have that
\(\sum _i (\text{Apx}_{i*}\cdot \text{diag}(B^\mathsf {T},1 ), S_{+1}) = (1 \pm \epsilon )\sum _{i}(A_{i*},S).\) 
Using the above relation, we give a coreset construction for the \(k\) -subspace approximation and \(k\) -median problems. These constructions are as in [1]}. For any matrix \(M\) , let \(M_{+1}\)  denote the matrix \(M\)  with a new column of 0s appended at the end and let \(M_{-1}\)  denote the matrix \(M\)  with the last column deleted.
Theorem E.1 (Coreset for Subspace Approximation) 
There exists a sampling-and-scaling matrix \(T\)  that samples and scales \(\tilde{O}(k^{3}/\epsilon ^8)\)  rows of the matrix \(\text{Apx}\)  such that, with probability \(\ge 3/5\) , for any projection matrix \(P\)  of rank \(k\)  that projects onto a subspace \(S\)  of dimension at most \(k\) , we have
\(\Vert (( T \cdot \text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1} - T \cdot \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)\Vert _{1,2} &= (1 \pm O(\epsilon ))\Vert ((\text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1} - \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)\Vert _{1,2}\\&= (1 \pm O(\epsilon ))\sum _i (A_i, S).\) 

This sampling matrix can be computed in time \(O(n \cdot (k/\epsilon ))\) .

We first have \(\Vert ((\text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1} - \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)\Vert _{1,2} = \sum _i \Vert ((\text{Apx}_{i*} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1} - \text{Apx}_{i*} \cdot \text{diag}(B^\mathsf {T},1)\Vert _2 = \sum _i \sqrt{\Vert (I-P)BX_{i*}^\mathsf {T}\Vert _2^2 + v_i^2} = \sum _i \sqrt{(BX_{i*}^\mathsf {T}, S)^2 + v_i^2} = (1 \pm \epsilon )\sum _i (A_{i*},S)\) .
We now show \(\Vert (( T \cdot \text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1} - T \cdot \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)\Vert _{1,2} = (1 \pm O(\epsilon ))\Vert ((\text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1} - \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)\Vert _{1,2}\)  proving the claim. Let \(G\)  be a Gaussian matrix with \(\tilde{O}(d/\epsilon ^2)\)  columns. Then with probability \(\ge 9/10\) , for all \(x \in ^{d+1}\) ,
\(\Vert x^\mathsf {T}G\Vert _1 = (1 \pm \epsilon )\Vert x\Vert _2.\) 
See [1]} for references. Thus we have that with probability \(\ge 9/10\) , for all projection matrices \(P\)  of rank at most \(k\) , we have
\(\Vert ((\text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1}G - \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)G\Vert _{1,1} = (1 \pm \epsilon )\Vert ((\text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1} - \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)\Vert _{1,2}.\) 
Note that for any \(P\) , the columns of the matrix \(((\text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1}G - \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)G\)  lie in the column space of the matrix \(\text{Apx}\) . Let \(T\)  be a \((1 \pm \epsilon )\)  \(\ell _1\) -subspace embedding constructed for the matrix \(\text{Apx}\)  constructed using [7]}. Therefore
\(\Vert T \cdot ((\text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1}G - T \cdot \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)G\Vert _{1,1} = (1 \pm \epsilon )\Vert ((\text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1}G - \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)G\Vert _{1,1}.\) 
Again, using the fact that \(\Vert x^\mathsf {T}G\Vert _1 = (1 \pm \epsilon )\Vert x\Vert _2\)  for all \(d+1\)  dimensional vectors \(x\) , we obtain that
\(&\Vert T \cdot ((\text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1} - T \cdot \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)\Vert _{1,2}\\&= (1 \pm \epsilon )\Vert T \cdot ((\text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1}G - T \cdot \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)G\Vert _{1,1}\\&= (1 \pm O(\epsilon ))\Vert ((\text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1}G - \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)G\Vert _{1,1}\\&= (1 \pm O(\epsilon ))\Vert ((\text{Apx} \cdot \text{diag}(B^\mathsf {T},1))_{-1}P)_{+1} - \text{Apx} \cdot \text{diag}(B^\mathsf {T},1)\Vert _{1,2}\\&= (1 \pm O(\epsilon ))\sum _i (A_i, S).\) 

The matrix \(T\)  is computed by Lewis Weight Sampling. As the matrix \(\text{Apx}\)  has dimensions \(n \times \tilde{O}(k^{3}/\epsilon ^6)\) , we see from [7]} that the matrix \(T\)  can be computed in time \(n \cdot (k/\epsilon )\) .
Theorem E.2 (Coreset for \(k\) -median) 
There exists a subset \(T \subseteq [n]\)  with \(|T| = \tilde{O}(k^4/\epsilon ^8)\)  and weights \(w_i\)  for \(i \in T\)  such that, with probability \(\ge 3/5\) , for any set \(C\)  of size \(k\) ,
\(\sum _{i \in T}w_i (\text{Apx}_{i*} \cdot \text{diag}(B^\mathsf {T}, 1), C_{+1}) = (1 \pm \epsilon )\sum _{i \in [n]}(A_{i*}, C).\) 
Recall that \(C_{+1} = {(c,0)\,|\,c \in C}\) .

Let \(S\)  denote the rowspan of the matrix \(\text{diag}(B^\mathsf {T},1)\) . We have \(\text{dim}(S) = \tilde{O}(k^{3}/\epsilon ^6)\) . Let \(\hat{S}\)  be the subspace \(S\)  along with an orthogonal dimension. Thus \(\hat{S}\)  is an \(\tilde{O}(k^{3}/\epsilon ^6)\)  dimensional subspace of \(^{d+1}\) . Let \(C = {c_1,\ldots , c_k}\)  be an arbitrary set of \(k\)  centers of \(^{d+1}\) . Now it is easy to see that we can find a set of \(k\)  points \(\hat{C} = {\hat{c}_1,\ldots , \hat{c}_k} \subseteq \hat{S}\)  such that \(\mathbb {P}_S c_i = \mathbb {P}_S \hat{c}_i\)  i.e., the projections of \(c_i\)  and \(\hat{c}_i\)  onto the subspace \(S\)  are the same, and also that \((c_i,\mathbb {P}_S(c_i)) = (\hat{c}_i, \mathbb {P}_S(\hat{c}_i))\)  and therefore, for any point \(a \in S\) , \((a, C) = (a, \hat{C})\) .
Now if \(T \subseteq [n]\)  and the weights \(w_i\)  for \(i \in T\)  are such that
\(\sum _{i \in T}w_i(\text{Apx}_{i*} \cdot \text{diag}(B^\mathsf {T}, 1), \tilde{C}) = (1 \pm \epsilon )\sum _{i=1}^n (\text{Apx}_{i*} \cdot \text{diag}(B^\mathsf {T}, 1), \tilde{C})\) 
for all \(k\) -center sets \(\tilde{C} \subseteq \hat{S}\) , then for any \(k\)  center set \(C \subseteq ^{d+1}\) , we have
\(\sum _{i \in T} w_i(\text{Apx}_{i*} \cdot \text{diag}(B^\mathsf {T}, 1), C) &= \sum _{i \in T}w_i(\text{Apx}_{i*} \cdot \text{diag}(B^\mathsf {T}, 1), \hat{C})\\&= (1 \pm \epsilon )\sum _{i = 1}^n (\text{Apx}_{i*} \cdot \text{diag}(B^\mathsf {T}, 1), \hat{C})\\&=(1 \pm \epsilon )\sum _{i = 1}^n (\text{Apx}_{i*} \cdot \text{diag}(B^\mathsf {T}, 1), {C}).\) 

Thus, preserving the \(k\) -median distances with respect to the \(k\)  center sets that lie in \(\hat{S}\) , preserves the \(k\) -median distances to all the center sets in \(^{d+1}\) . Using the coreset construction of [20]} on the matrix \(\text{Apx}\) , we can obtain a subset \(T \subseteq [n]\)  of size \(\tilde{O}(k^{4}/\epsilon ^8)\)  along with weights \(w_i\)  such that for any \(k\) -center set \(C \subseteq ^{d+1}\) , we have
\(\sum _{i \in T} w_i(\text{Apx}_{i*} \cdot \text{diag}(B^\mathsf {T}, 1), C) = (1 \pm \epsilon )\sum _{i = 1}^n (\text{Apx}_{i*} \cdot \text{diag}(B^\mathsf {T}, 1), {C}).\) 
As \(\text{Apx}\)  is an \(n \times (k/\epsilon )\) -sized matrix, the algorithm of [20]} can be run in time \(n \cdot (k/\epsilon )\) . Thus, the above subset \(T\)  and weights \(w_i\)  for \(i \in T\)  can be found in time \(n(k/\epsilon )\) . Now, for any \(k\) -center set \(C \subseteq ^d\) , we have that
\(\sum _{i = 1}^n (A_{i*}, C) &= (1 \pm \epsilon )\sum _{i=1}^n \sqrt{(BX_{i*}^\mathsf {T}, C) + v_i^2}\\&= (1 \pm \epsilon )\sum _{i=1}^n (\text{Apx}_{i*} \cdot \text{diag}(B^\mathsf {T}, 1), C_{+1})\\&= (1 \pm \epsilon )\sum _{i \in T} w_i (\text{Apx}_{i*} \cdot \text{diag}(B^\mathsf {T},1), C_{+1}).\) 

Therefore we obtain a coreset of size \(\tilde{O}(k^{4}/\epsilon ^8)\)  in overall time \(\tilde{O}((A)/\epsilon ^2 + (n+d)(k/\epsilon ))\) .

Near-Linear Time Coreset for \(k\) -Median
Let \(A \in ^{n \times d}\)  be the dataset, where each row \(A_{i*}\)  of \(A\)  denotes a point in \(^d\) , for \(i \in [n]\) . We observe that the coreset construction of [22]} can be implemented in \(\tilde{O}((A) + (n+d)(k/\epsilon ))\)  time. The authors only need to compute a constant factor approximation and assignment of each point to a center, which gives a constant factor approximation to the optimum. We show that we can compute such an assignment in time \(O((A) + (n+d)(k/\epsilon ))\) .
The usual \(k\) -median objective is the following
\(\min _{y_1,\ldots ,y_k \in ^d}\sum _{i=1}^n \min _j \Vert A_i^* - y_j\Vert _2.\) 
We can restrict \(y_j\)  to be a row of \(A_i^*\)  and lose at most a factor of 2 as follows. Suppose \(y_1^*,\ldots ,y_k^*\)  is the optimal solution. Let \(\mathcal {C^*} = (\mathcal {C}_1^*,\mathcal {C}_2^*,\ldots ,\mathcal {C}_n^*)\)  be the partition of \([n]\)  induced by the optimal solution \(y_1^*,\ldots ,y_k^*\) , where \(\mathcal {C}_j^*\)  denotes all the indices \(i\)  such that \(y_j^*\)  is the closest center to \(A_{i*}\) . Therefore, the optimal cost for \(k\) -median is
\(= \sum _{j=1}^k \sum _{i \in \mathcal {C}^*_j} d(A_{i*},y_j^*).\) 
Let \(A_{c(j)}\)  be the point closest to \(y_j^*\) , i.e.,
\(\text{for all $i \in \mathcal {C}_j^*$},\ d(A_{i*},y_j^*) \ge d(A_{c(j)*},y_j^*).\) 
We claim that the \(k\) -median cost of the centers \(A_{c(1)},\ldots ,A_{c(k)}\)  is at most twice the optimum:
\(\sum _{j=1}^k \sum _{i \in \mathcal {C}_j^*}d(A_{i*},A_{c(j)*}) \le \sum _{j=1}^k \left(\sum _{i \in \mathcal {C}_j^*}d(A_{i*},y_j^*) + d(A_{c(j)*},y_j^*)\right) \le \sum _{j=1}^k\sum _{i \in \mathcal {C}_j^*}2d(A_{i*},y_j^*) \le 2.\) 
Metric \(k\) -median
In this version of \(k\) -median, we restrict to center sets \(C\)  that are subsets of the data, i.e., we solve the optimization problem
\(\min _{y_1,\ldots ,y_k \in A}\sum _{i=1}^n \min _j \Vert A_i^* - y_j\Vert _2.\) 
Let \(_{\text{metric}}\)  denote the optimum objective value for metric \(k\) -median. From the above, we obtain that
\(_{\text{metric}} \le 2 \text{}.\) 
Therefore, a \(c\) -approximate solution for metric \(k\) -median is at most a \(2c\) -approximate solution for Euclidean \(k\) -median. Let \(\Pi \)  be a Johnson Lindenstrauss matrix embedding \(^d\)  into \(^m\) , where \(m = O(\log (n))\) , such that
\(\frac{1}{2}d(A_{i*},A_{i^{\prime }*}) \le d(\Pi A_{i*},\Pi A_{i^{\prime }*}) \le \frac{3}{2} d(A_{i*}, A_{i^{\prime }*})\) 
for all \(i,i^{\prime } \in [n]\) . Now consider the metric \(k\) -median problem on the points \(\Pi A_{1*},\ldots ,\Pi A_{n*}\) . We can obtain an 11-approximate solution to the metric \(k\) -median problem in time \(\tilde{O}(nk+k^7)\)  (see Theorem 6.2 of [23]}). Let \(A_{c^*(1)*},\ldots ,A_{c^*(k)*}\)  be the optimal centers for the metric \(k\) -median problem on \(A_{1*},\ldots , A_{n*}\) , and \(\Pi A_{c^{\prime }(1)},\ldots ,\Pi A_{c^{\prime }(k)}\)  be an 11-approximate solution to the metric \(k\) -median on \(\Pi A_{1*},\ldots , \Pi A_{n*}\) . Let \(\mathcal {C}^{\prime } = (\mathcal {C}_1,\ldots ,\mathcal {C}^{\prime }_k)\)  be the partition of \([n]\)  corresponding to this 11-approximate solution. Then the following shows that \(A_{c^{\prime }(1)},\ldots ,A_{c^{\prime }(k)}\)  is a good solution for the metric \(k\) -median problem on the original dataset:
\(\sum _{j=1}^k \sum _{i \in \mathcal {C}^{\prime }_j}d(A_{i*},A_{c^{\prime }(j)*}) &\le 2\sum _{j=1}^k \sum _{i \in \mathcal {C}^{\prime }_j}d(\Pi A_{i*},\Pi A_{c^{\prime }(j)*})\\&\le 2 \cdot 11 \sum _{j=1}^k \sum _{i \in \mathcal {C}^*_j}d(\Pi A_{i*},\Pi A_{c^*(j)*})\\&\le 2 \cdot 11 \cdot \frac{3}{2}\sum _{j=1}^k \sum _{i \in \mathcal {C}^*_j}d(A_{i*}, A_{c^*(j)*})\\&\le 33_{\text{metric}} \le 66.\) 
The time taken to compute \(\Pi A_{1*},\ldots , \Pi A_{n*}\)  is \(O({(A)}\log (n))\) , and then we can compute the \(k\)  centers and an assignment of points such that this is a 66-approximate solution in time \(\tilde{O}(nk+k^7)\) . Using this assignment, we can implement the first stage of importance sampling in the algorithm of [22]} in time \(\tilde{O}({(A)} + n \cdot (k/\epsilon ))\) . We note that the first stage of the algorithm of [22]} only needs a constant factor approximation of the distance of a point to its assigned centers, which can be computed as \(d(\Pi A_{i*}, \Pi A_{c^{\prime }(j)*})\) , in time \(\tilde{O}(\log (n))\) , if the point \(i\)  is assigned to cluster \(j\) . The second stage of their algorithm can be implemented in time \(d \cdot (k/\epsilon )\) . Thus, we can find a strong coreset for \(k\) -median in time
\(\tilde{O}({(A)} + (n+d) \cdot (k/\varepsilon )).\) 
