Posts

The huger the mob, and the greater the apparent anarchy, the more perfect is its sway. It is the supreme law of Unreason. – Sir Francis Galton This post is the continuation of the previous post over here. Last Time In the previous post, we began the analysis of a randomized matrix multiplication algorithm. We managed to prove that the output of the algorithm gives us our product $AB$ in expectation, and furthermore, that the expected squared deviation $\mathbb{E}[\|D-AB\|_F^2]$ satisfies ...

千里之行，始於足下。 [The journey of a thousand miles begins with a simple step.] – Lao Tzu Introduction We all have to start somewhere, and I have decided to start the blog with something simple, that most people in the quantitative sciences would have to deal with at some point in their lives: matrix multiplication. Performing matrix multiplication fast is important for many applications, like machine learning or numerical methods. We will consider matrices (square of order $n$, for simplicity) $A=(a_{ij})_{i,j=1}^n$, and $B=(b_{ij})_{i,j=1}^n$, think about ways to evaluate $AB$. The simplest, most naive algorithm would be as follows: ...