Before revision:  As both (1) spectral low rank approximation (A = B) and (2) linear system solving ( m = n and d = 1) are special cases, our time cannot be improved by more than a 1/\varepsilon factor (up to polylogarithmic factors) without a major breakthrough in linear algebra.
After revision:  As both (1) spectral low rank approximation (A = B) and (2) linear system solving ( n = c and d = 1) are special cases, our time cannot be improved by more than a 1/\varepsilon factor (up to polylogarithmic factors) without a major breakthrough in linear algebra.