3
$\begingroup$

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$

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

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.