Path: news.mathworks.com!not-for-mail
From: "Bruno Luong" <b.luong@fogale.findmycountry>
Newsgroups: comp.soft-sys.matlab
Subject: Re: in [Q, R, E] = qr(A), how E is determined ?
Date: Tue, 5 May 2009 18:12:01 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 3
Message-ID: <gtpvhg$r9s$1@fred.mathworks.com>
References: <gtpuae$4b7$1@fred.mathworks.com>
Reply-To: "Bruno Luong" <b.luong@fogale.findmycountry>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1241547121 27964 172.30.248.35 (5 May 2009 18:12:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Tue, 5 May 2009 18:12:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:537624


QR is essentially a Gram-Smidth orthogonalization procedure. During the iteration #k, it is easy to show that if we pick among the set of remaining vectors (i.e., not yet included in the span) the vector that has the *largest* orthogonal component to the current subspace (generated by k first vectors), then the diagonal of R must decrease. Essentially, this can be easily prove using triangular inequality (norm of the projection <= norm of the vector). This procedure provides a permutation E and warranty the expected property without any extra cost in QR decomposition (certainly not exponential or factorial complexity).

Bruno