obtained by [@musco2015stronger] which are not obtained by simpler linear sketching methods.

#### Sketched preconditioning: 

Recently, subspace embedding methods were used to develop cheap preconditioners for linear regression with respect to the squared loss [@woodruff2014sketching]. Precisely, [@clarkson2013low] considered the case $\lambda=0$ (i.e, standard least-squares) and developed a preconditioning method that reduces the average condition number to a constant. Thereafter, they suggest applying a basic solver such as CG. The overall running time is dominated by the preconditioning process which runs in time $\tilde{O}(d^3+nd)$. Hence, a significant improvement over standard solvers is obtained if $n \gg d$.

The main shortcoming of this method is that it does not scale well to large dimensions. Indeed, when $d$ is very large, the overhead resulted from the preconditioning process can not be afforded.

#### Efficient preconditioning based on random sampling: 

While we focus on reducing the dependence on the dimensionality of the data, other work investigated the gain from using only a random subset of the data points to form the conditioner [@yang2014data]. The theoretical gain of this approach has been established under coherence assumptions [@yang2014data].

Preliminaries {#sec:pre}
=============

Additional notation and definitions {#sec:notation}
-----------------------------------

Any matrix $B \in \reals^{d \times n}$ of rank 