# Kronecker-factored least-squares?

Suppose $$a_i,b_i$$ are $$d\times 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^T\otimes 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, $$d\le n

• Isn’t the Kronecker product 1xd^2 in this setting? How is w size dx1? – Jesse Chan Dec 12 '20 at 4:13
• Very similar recent question, which is basically the symmetric version of your problem. It did not get a positive answer, so it looks like this one is going to be similar. – Federico Poloni Dec 12 '20 at 8:19
• Is $n$ the number of equations? The system is underdetermined then; you can't solve it with Cholesky. – Federico Poloni Dec 12 '20 at 8:31
• @JesseChan corrected – Yaroslav Bulatov Dec 12 '20 at 17:37
• Do the $n$ vectors $b_i$ span your $n$-dimensional space? – Wolfgang Bangerth Dec 14 '20 at 2:21