Modified Gram-Schmidt Orthogonalization in Matlab

Posted in Code, Matlab by Elliott Back on October 16th, 2004.

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:

Start with Ax ~= b, where A is mxn, m > n (overdetermined system)
Compute A = Q * [R O]^T^, where Q is an orthogonal mxn matrix and R is an nxn upper triangular matrix
Multiply Q^T^ * b to find new right hand side [c1 ... cn]^T^
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

This entry was posted on Saturday, October 16th, 2004 at 5:50 pm and is tagged with nbsp nbsp nbsp nbsp nbsp, squares solution, qr factorization, least squares, gram schmidt, orthogonalization, back substitution, zeros, best fit, orthogonal, matlab, algorithm, norm, cn, matrix. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback.

Viewing 4 Comments

Nemo 3 years ago 1 point
Please login to rate.

Do you already have an account? Log in and claim this comment.

??? Index exceeds matrix dimensions.

reply edit reblog flag

Anonymous 3 years ago 1 point
Please login to rate.

Do you already have an account? Log in and claim this comment.

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 edit reblog flag

shriks 10 months ago 1 point
Please login to rate.

Do you already have an account? Log in and claim this comment.

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

reply edit reblog flag

elliottback 10 months ago 1 point
Please login to rate.

Do you already have an account? Log in and claim this comment.

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

reply edit reblog flag

1 /people/elliottback/ /people/elliottback/following/