Kronecker-factored least-squares?

Suppose $a_i,b_i$ are $dtimes 1$ matrices, $y_i$ is scalar, and I need to find least-squares solution $w$ of the following system of $n$ equations:

$$y_i=(a_i^Totimes b_i^T)w$$

Is there a specialized approach for this system?
Converting to normal equations and applying Cholesky to solve for $w$ takes takes $O(d^6)$ operations. This is a quite a bit expensive than verifying the solution at $O(d^2)$ operations. I was hoping for an approach that scales as $O(d^4)$ or $O(d^3)$. For my problem, $dle n<d^2$