Answers.Body: <p>You can sometimes exploit the structure of your matrix to perform faster matrix multiplication. For example, if your matrix is <a href="https://en.wikipedia.org/wiki/Sparse_matrix" rel="nofollow noreferrer">sparse</a> (or dense), there are algorithms that exploit this fact. </p>
  
  <p>In your case, you can actually compute <span class="math-container">$A^n$</span> in less time than <span class="math-container">$\mathcal{O}(n^3$</span>). For example, have a look at <a href="https://cs.stackexchange.com/q/4998/20691">this question at CS SE</a> and <a href="https://stackoverflow.com/q/12311869/3924118">this one at Stack Overflow (SO)</a>. Note that the provided solutions may not be numerically stable, so I am not suggesting you use them.</p>
  
  <p>Moreover, if you perform your operations on the GPU, they could be faster in practice. See e.g. <a href="https://stackoverflow.com/q/51344018/3924118">this question at SO</a> and <a href="https://scicomp.stackexchange.com/q/5372/9925">this one at SciComp SE</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-13T13:15:31.260Z
Answers.LastActivityDate: 2020-04-13T13:15:31.260Z
Answers.UserDisplayName: nbro
Body: <p>I am trying to optimize the cost function calculation in regression analysis using a non-matrix multiplication based approach.</p>
  
  <p>More specifically, I have a point <span class="math-container">$x = (1, 1, 2, 3)$</span>, to which I want to apply a linear transformation <span class="math-container">$n$</span> times. If the transformation is denoted by a <span class="math-container">$4 \times 4$</span> matrix <span class="math-container">$A$</span>, then the final transformation would be given by <span class="math-container">$A^n * x$</span>. </p>
  
  <p>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?</p>
  
Tags: <linear-regression><statistical-ai><linear-algebra>
Title: Is there any way to apply linear transformations on a vector other than matrix multiplication?
UserDisplayName: Akshay Tilekar
ThreadText: # Is there any way to apply linear transformations on a vector other than matrix multiplication?
  
  (Asked by: username_0 on 2020-04-12)
  
  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?
  
  **Tags:** linear-regression, statistical-ai, linear-algebra
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-04-13. Score: 1
  
  You can sometimes exploit the structure of your matrix to perform faster matrix multiplication. For example, if your matrix is [sparse](https://en.wikipedia.org/wiki/Sparse_matrix) (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](https://cs.stackexchange.com/q/4998/20691) and [this one at Stack Overflow (SO)](https://stackoverflow.com/q/12311869/3924118). 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](https://stackoverflow.com/q/51344018/3924118) and [this one at SciComp SE](https://scicomp.stackexchange.com/q/5372/9925).
  
  
  ---
  
  