Sums, products and linear algebra notation - avoiding loops where possible

| categories: linear algebra | View Comments

Sums, products and linear algebra notation - avoiding loops where possible

Sums, products and linear algebra notation - avoiding loops where possible

John Kitchin

Today we examine some methods of linear algebra that allow us to avoid writing explicit loops in Matlab for some kinds of mathematical operations.

Contents

Consider the operation on two vectors $\bf{a}$ and $\bf{b}$.

$$y=\sum\limits_{i=1}^n a_ib_i$$

a = [1 2 3 4 5];
b = [3 6 8 9 10];

Old-fashioned way with a loop

We can compute this with a loop, where you initialize y, and then add the product of the ith elements of a and b to y in each iteration of the loop. This is known to be slow for large vectors

y = 0;
for i=1:length(a)
    y = y + a(i)*b(i);
end

y
y =

   125

dot notation

Matlab defines dot operators, so we can compute the element-wise product of $\bf{a}$ and $\bf{b}$, and then use the builtin sum command to get the result.

y = sum(a.*b)
y =

   125

dot product

The operation above is formally the definition of a dot product. We can directly compute this in Matlab. Note that one vector must be transposed so that we have the right dimensions for legal matrix multiplication (one vector must be a row, and one must be column). It does not matter which order the multiplication is done as shown here.

y = a*b'

y = b*a'
y =

   125


y =

   125

Another example

$$y=\sum\limits_{i=1}^n w_ix_i^2$$

This operation is like a weighted sum of squares.

w = [0.1 0.25 0.12 0.45 0.98];
x = [9 7 11 12 8];

Old-fashioned method with a loop

y = 0;
for i = 1:length(w)
    y = y + w(i)*x(i)^2;
end
y
y =

  162.3900

dot operator approach

We use parentheses to ensure that x is squared element-wise before the element-wise multiplication.

y = sum(w.*(x.^2))
y =

  162.3900

Linear algebra approach

The operation is mathematically equivalent to $y = \bf{x}\bf{D_w}\bf{x^T}$ when $\bf{x}$ is a row vector. $\bf{D_w}$ is a diagonal matrix with the values of $\bf{w}$ on the diagonal, and zeros everywhere else. The Matlab command diag creates this matrix conveniently.

y = x*diag(w)*x'
y =

  162.3900

Last example

$$z=\sum\limits_{i=1}^n w_i x_i y_i$$

This operation is like a weighted sum of products.

w = [0.1 0.25 0.12 0.45 0.98];
x = [9 7 11 12 8];
y = [2 5 3 8 0];

Old fashioned method with a loop

z = 0;
for i=1:length(w)
    z = z + w(i)*x(i)*y(i);
end
z
z =

   57.7100

dot notation

we use parentheses

z = sum(w.*x.*y)
z =

   57.7100

Linear algebra approach

Note that it does not matter what order the dot products are done in, just as it does not matter what order w(i)*x(i)*y(i) is multiplied in.

z = x*diag(w)*y'
z = y*diag(x)*w'
z = w*diag(y)*x'
z =

   57.7100


z =

   57.7100


z =

   57.7100

Summary

We showed examples of the following equalities between traditional sum notations and linear algebra

$$\bf{a}\bf{b}=\sum\limits_{i=1}^n a_ib_i$$

$$\bf{x}\bf{D_w}\bf{x^T}=\sum\limits_{i=1}^n w_ix_i^2$$

$$\bf{x}\bf{D_w}\bf{y^T}=\sum\limits_{i=1}^n w_i x_i y_i$$

These relationships enable one to write the sums as a single line of Matlab code, which utilizes fast linear algebra subroutines, avoids the construction of slow loops, and reduces the opportunity for errors in the code. Admittedly, it introduces the opportunity for new types of errors, like using the wrong relationship, or linear algebra errors due to matrix size mismatches.

% categories: Linear Algebra
% tags: math
blog comments powered by Disqus