A reasonable way to calculate all pairwise correlations is the following:
- First normalize the input rows so that each row has the arithmetic mean of 0.
- Then normalize the input rows so that for each row the sum of the squares of the elements is 1.
- Let X be the normalized input matrix.
- Calculate the (upper triangle of the) matrix product Y = XXT.
Now matrix Y contains all pairwise correlations. The only computationally-intensive part is the computation of the matrix product; the normalizations can be done in linear time in the input size.