where \(\mathbf {S}\in \mathbb {R}^{s\times n}\)  is the sketch matrix. We consider three sketching methods, one dense (slow and accurate) and two sparse variants (fast but less accurate). (i) Gaussian sketch: we let \(\mathbf {S}_{i,j}\stackrel{iid}{\sim } {\mathcal {N}}(0, 1)\) . (ii) CountSketch [1]}: for each column of \(\mathbf {S}\) , we randomly pick a row and generate a Rademacher variable. (iii) LESS-Uniform [2]}: for each row of \(\mathbf {S}\) , we randomly pick a fixed number of nonzero entries and generate a Rademacher variable for each one. We let the number of nonzero entries of each row to be \(0.1d\) . The sketches are then scaled appropriately so that \(\mathbb {E}[{\hat{}}()]=()\) .
