Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Yesterday, I was watching Strang's lectures on Matrix multiplication. He mentioned five different ways of looking at the multiplication $\mathbf{AB} = \mathbf{C}.$

  1. Classic way (Row of $\mathbf{A} \cdot$ Column of $\mathbf{B}$).

  2. Column of $\mathbf{B}$ at a time.

    Column of $\mathbf{C}$ are combinations of Column of $\mathbf{A}$.

  3. Row of $\mathbf{A}$ at a time.

    Rows of $\mathbf{C}$ are combinations of rows of $\mathbf{}$.

  4. Column of $\mathbf{A} \cdot$ Row of $\mathbf{B}$

    $\mathbf{AB}$ = $\sum$ Column of $\mathbf{A} \cdot$ Row of $\mathbf{B}$

  5. By blocks

The column at a time way reminded me of the the Johnson–Lindenstrauss lemma and the improvement by Achlioptas. One key insight of the idea of the embedding is that each column of B in the multiplication $\mathbf{AB}$ gives a testimony (linear combination) of the elements in a row of A. The theorems in these seminal works examine the conditions that should apply to B in order to minimize the distortion of A’s projection to a lower dimensional space. The forth way made me think of low rank approximations.

Can you think of other algorithms that use one of the intuitions above in matrix multiplication?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.