QR decomposition with the output of a permutation vector

18 views (last 30 days)
It is noted that the Matlab syntax for qr decomposition (https://www.mathworks.com/help/symbolic/qr.html#d120e152496):
[Q,R,P] = qr(A) returns an upper triangular matrix R, a unitary matrix Q, and a permutation matrix P, such that A*P = Q*R. If all elements of A can be approximated by the floating-point numbers, then this syntax chooses the column permutation P so that abs(diag(R)) is decreasing.
For example: A = [12 -51 4; 6 167 -68; -4 24 -41]
Then, [Q,R, P] = qr(A)
Q =
-0.2894 -0.4682 -0.8349
0.9475 -0.0160 -0.3194
0.1362 -0.8835 0.4483
R =
176.2555 -71.1694 1.6680
0 35.4389 -2.1809
0 0 -13.7281
P =
2 3 1
What's the physcial meaning of the fact that the diagnoal elements of R matrix are decreasing in magnitude? Without the output P, the resulting Q and R occurs in a different order in its column vectors.
I am not clear of how these different demposition behaviors occur. What's the specific algorithm Matlab is using for qr? Householder reflections (https://blogs.mathworks.com/cleve/2016/10/03/householder-reflections-and-the-qr-decomposition/)? Any relevant resources are welcome.

Accepted Answer

Christine Tobler
Christine Tobler on 11 May 2020
Edited: Christine Tobler on 11 May 2020
The purpose of arranging all diagonal elements in descending order is to allow splitting R into two parts if A is low-rank or close to it. Here's an example:
>> A = [0 3 -2 1; 0 -6 4 -2; 0 2 -3 -1; 0 1 1 2];
>> [Q, R] = qr(A); R
R =
0 3.0000 -2.0000 1.0000
0 6.4031 -4.5290 1.8741
0 0 2.3426 2.3426
0 0 0 -0.0000
>> [Q, R, P] = qr(A); R
R =
-7.0711 -2.1213 4.9497 0
0 2.3452 2.3452 0
0 0 -0.0000 0
0 0 0 0
In the second case, it's easy to see from the diagonal of R that A is of rank 2 (accounting for some round-off error). Knowing this, One can use A*P = Q(:, 1:2)*R(1:2, :) as a decomposition of A that has this low rank. This would be much harder to do using Q and R from the two-output syntax of the qr function.
Here are some additional references: https://en.wikipedia.org/wiki/QR_decomposition#Column_pivoting and A BLAS-3 Version of the QR Factorization with Column Pivoting (this paper discusses details of efficiently implementing QR, but the introduction should provide more context about where column pivoting is used).

More Answers (0)

Categories

Find more on Linear Algebra in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!