Permutation matrix P in the qr function

5 次查看(过去 30 天)
Hello,
I understand that using the following sintax
[Q,R,P]=qr(A)
I obtain the QR decomposition of the matrix A and, P is a permutation matrix that reorder A such that AP=QR where abs(diag(R)) is decreasing.
How this matrix P is obtained?
Let's call the new matrx B=AP. Are the columns of the matrix B ordered from the most to the least independent?
Thank you in advance,
Gabri

采纳的回答

David Goodmanson
David Goodmanson 2021-3-10
编辑:David Goodmanson 2021-3-10
Hello Gabriele,
I don't think you can conclude anything about the columns of A. That's because the usual qr decomposition is unique (not counting the signs of the diagonal elements of R. Those are easy to make all positive if desired, along with simultaneously changing Q) Matlab does not choose to do so).
But the solution with the P option is not unique. In the code below, [Q R P] = qr(A) is the Matlab solution, and A*P puts the columns of A into the order [2 1 4 3].
However, Q1,R1,P1 below is also a solution. R1 has different values from R (still decreasing in abs value down the diagonal as required) and P1 is a lot different from P, putting the columns of A into the order [4 2 3 1].
The column associated with the smallest diagonal value of R is different in each case. Same for column associated with the largest diagonal value. it's hard to draw any conclusions.
A = ...
[1.0933 -1.2141 -0.7697 -1.0891
1.1093 -1.1135 0.3714 0.0326
-0.8637 -0.0068 -0.2256 0.5525
0.0774 1.5326 1.1174 1.1006];
[Q R P] = qr(A);
Q =
-0.5396 -0.3593 0.3554 0.6734
-0.4949 -0.4048 -0.7354 -0.2244
-0.0030 0.6125 -0.5175 0.5975
0.6811 -0.5761 -0.2551 0.3730
R =
2.2501 -1.0836 1.3195 0.9933
0 -1.4155 0.0825 -0.6557
0 0 -0.9777 -0.7149
0 0 0 -0.3196
P =
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
% another solution
Q1 =
-0.6623 -0.0135 0.0242 0.7487
0.0198 -0.8560 0.5164 -0.0146
0.3360 -0.4569 -0.7616 0.3136
0.6693 0.2414 0.3909 0.5839
R1 =
1.6443 1.8056 1.1893 -0.9405
0 1.3426 0.0653 -0.5510
0.0000 0 0.7818 1.2872
-0.0000 -0.0000 -0.0000 0.5767
P1 =
0 0 0 1
0 1 0 0
0 0 1 0
1 0 0 0
chk = Q1*R1-A*P1 % for a solution, should be small. comes out
% ~~1e-3 if the data is used from the listing above,
% since there are only three significant figures.
chk =
1.0e-15 *
0 -0.4441 0.1110 0
-0.4372 -0.2220 -0.3331 0.2220
0 0.1240 -0.1665 -0.3331
0 0.2220 0 -0.3053
  2 个评论
Gabriele Galli
Gabriele Galli 2021-3-10
编辑:Gabriele Galli 2021-3-10
Hello David,
Thank you for your reply! How did you get the second qr decomposition (i.e. Q1, R1, P1)?
I tried to run multiple time the [Q,R,P]=qr(A) but I am always getting the same result which is the same as your Q, R, P.
Is the algorithm behind the [Q,R,P]=qr(A) sintax the so-called "Rank Revealing QR"?
David Goodmanson
David Goodmanson 2021-3-11
Hello Gabriele.
all I did was
A = ...
[1.0933 -1.2141 -0.7697 -1.0891
1.1093 -1.1135 0.3714 0.0326
-0.8637 -0.0068 -0.2256 0.5525
0.0774 1.5326 1.1174 1.1006];
p = [4 2 3 1]; % one that works
P = full(sparse(p,1:4,1))
[q r] = qr(A*P)
In the code above, a permutation p and the constructed permutation matrix P shuffle the columns of A identically,
A(:,p) = A*P
When you impose a permutation matrix P, it is not always going to be the case that R has decreasing absolute values down the diagonal, making it conform to the same rule as the Matlab result. I just ran through some random matrices A and permutations p until I found one that worked . It did not take long.
I wish I knew, but I have no idea if RRQR is involved with what Matlab is doing here.

请先登录,再进行评论。

更多回答(1 个)

Shiva Kalyan Diwakaruni
Permutation information, returned as a matrix or vector. The shape of P depends on the value of outputForm. Also, qr selects P to satisfy different criteria depending on whether the first input matrix is full or sparse:
  • Full — qr selects P so that abs(diag(R)) is decreasing.
  • Sparse — qr selects P to reduce fill-in in R.
please refer to the below link for more information
hope it helps,
thanks.
  1 个评论
Gabriele Galli
Gabriele Galli 2021-3-9
Hello Shiva,
Thank you for the answer.
If the matrix is selected using the "Full" criteria, this means that the new matrix B=A*P, (where A is the input matrix) is a matrix with columns ordered from the most to the less independent?
Thank you! Gabri

请先登录,再进行评论。

类别

Help CenterFile Exchange 中查找有关 Linear Algebra 的更多信息

Community Treasure Hunt

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

Start Hunting!

Translated by