Random projections or sketching are widely used in many algorithmic and\nlearning contexts. Here we study the performance of iterative Hessian sketch\nfor least-squares problems. By leveraging and extending recent results from\nrandom matrix theory on the limiting spectrum of matrices randomly projected\nwith the subsampled randomized Hadamard transform, and truncated Haar matrices,\nwe can study and compare the resulting algorithms to a level of precision that\nhas not been possible before. Our technical contributions include a novel\nformula for the second moment of the inverse of projected matrices. We also\nfind simple closed-form expressions for asymptotically optimal step-sizes and\nconvergence rates. These show that the convergence rate for Haar and randomized\nHadamard matrices are identical, and asymptotically improve upon Gaussian\nrandom projections. These techniques may be applied to other algorithms that\nemploy randomized dimension reduction.\n