Elliott C. Back: In Aere Aedificare

As promised, I’ve got the cleaned up US state boundary data, perfect for creating visualizations in Excel or Matlab. It’s a dataset of (x,y) points for each state, cleaned so that all of the state boundaries lie exactly on top of each other. So, the map is a continuous set of polygons. Here are a couple pictures:

Download it in Matlab .mat or Excel .xls, and feel free to use it in any projects.

Without any ado at all, I present Matlab 6.5 code to do Modified Gram-Schmidt Orthogonalization, otherwise known as QR Factorization. You can use a QR factorization to compute a number of things, the least of which is the least squares solution, which can be computed in the following manner:

1. Start with Ax ~= b, where A is mxn, m > n (overdetermined system)
2. Compute A = Q * [R O]^T^, where Q is an orthogonal mxn matrix and R is an nxn upper triangular matrix
3. Multiply Q^T^ * b to find new right hand side [c1 … cn]^T^
4. Use back-substitution to solve R * x = [c1 … cn]^T^ for x

Great!! Now you can find your own best fit lines. Here’s the QR factorization algorithm:

function [q, r] = QR(A)
        [m, n] = size(A);

        q = zeros(m, n);
        r = zeros(n, n);

        for k = 1:n
                r(k,k) = norm(A(1:m, k));

                if r(k,k) == 0
                        break;
                end

                q(1:m, k) = A(1:m, k) / r(k,k);

                for j = k+1:n
                        r(k, j) = dot(q(1:m, k), A(1:m, j));
                        A(1:m, j) = A(1:m, j) - r(k, j) * q(1:m, k);
                end
        end