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<d^2$

  • 1
    $\begingroup$ Isn’t the Kronecker product 1xd^2 in this setting? How is w size dx1? $\endgroup$
    – Jesse Chan
    Dec 12 '20 at 4:13
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 12 '20 at 8:19
  • $\begingroup$ Is $n$ the number of equations? The system is underdetermined then; you can't solve it with Cholesky. $\endgroup$ Dec 12 '20 at 8:31
  • $\begingroup$ @JesseChan corrected $\endgroup$ Dec 12 '20 at 17:37
  • $\begingroup$ Do the $n$ vectors $b_i$ span your $n$-dimensional space? $\endgroup$ Dec 14 '20 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.