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

4 Responses to “Modified Gram-Schmidt Orthogonalization in Matlab”

1. Elliott Back says:

   1/21/2008 at 10:09 am

   Yes, but it won’t give anything useful to you; you’ll end up with output like an identity matrix.

   Reply
2. shriks says:

   1/21/2008 at 6:10 am

   Can this Modified Gram-Schmidt Orthogonalization be applicable to linearly dependent vectors ?

   Reply
3. Anonymous says:

   7/3/2005 at 6:41 am

   function Q = mgs(A)

   n = size(A,2);
   Q = A;

   for k = 1:n-1,
   Q(:,k) = A(:,k) ./ norm(A(:,k));
   A(:,k+1:n) = A(:,k+1:n) – Q(:,k) * (Q(:,k)’ * A(:,k+1:n));
   end;
   Q(:,n) = A(:,n) ./ norm(A(:,n));

   Reply
4. Nemo says:

   5/9/2005 at 4:35 pm

   ??? Index exceeds matrix dimensions.

   Reply