1
$\begingroup$

I am trying to optimize the cost function calculation in regression analysis using a non-matrix multiplication based approach.

More specifically, I have a point $x = (1, 1, 2, 3)$, to which I want to apply a linear transformation $n$ times. If the transformation is denoted by a $4 \times 4$ matrix $A$, then the final transformation would be given by $A^n * x$.

Given that matrix multiplication can computational expensive, is there a way we can speed up the computation, assuming we would need to run multiple iterations of this simulation?

$\endgroup$
  • $\begingroup$ Singular value decomposition might help. $\endgroup$ – DuttaA Sep 10 at 14:26
1
$\begingroup$

You can sometimes exploit the structure of your matrix to perform faster matrix multiplication. For example, if your matrix is sparse (or dense), there are algorithms that exploit this fact.

In your case, you can actually compute $A^n$ in less time than $\mathcal{O}(n^3$). For example, have a look at this question at CS SE and this one at Stack Overflow (SO). Note that the provided solutions may not be numerically stable, so I am not suggesting you use them.

Moreover, if you perform your operations on the GPU, they could be faster in practice. See e.g. this question at SO and this one at SciComp SE.

| improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.