Talk:QR decomposition

From Wikipedia, the free encyclopedia

Contents

[edit] translation question

I'm trying to translate this article in french. I'm wondering about the example of Householder reflections method and especially, the calcul for the length of the vector a1. I see that \| a_1 \| = 12+6+(-4) = 14 , I would prefer \| a_1 \| = 12+6+|-4| = 22 or \| a_1 \| = \sqrt{12^2+6^2+(-4)^2} . PierreLM April 13th 2005

You know you can just use that in your French version. Dysprosia 13:30, 14 Apr 2005 (UTC)

I'm so sorry, \| a_1 \|_2 = \sqrt{12^2+6^2+(-4)^2} = 14. So there is no problem. PierreLM April 15th 2005

[edit] Sign of α in Householder

The section on the Householder method says that α should take its sign from the first element in \mathbf{x}. In the example which follows, however, the second matrix generated appears not to use the sign operation. Am I missing something, or should this be fixed?--rlhatton 16:11, 25 January 2006 (UTC)

Using the other sign does not matter if you use exact computations, as in the example. I tried to clarify this. However, perhaps it is better to change the example to match the sign convention, or at least make a remark at that point. -- Jitse Niesen (talk) 13:44, 27 January 2006 (UTC)

[edit] QR decomposition with rank deficiency

Is there somebody to editorialize the definition without assuming the full rank? S. Jo 14:03, 7 May 2006 (UTC)

Aha, I didn't notice that this was the point behind the edit I reverted. Better now? -- Jitse Niesen (talk) 01:45, 8 May 2006 (UTC)
Somehow, I don't think that we need to start with a square matrix. When we solve an over-determined system of equations in order to minimize the unitarily invariant norm of residuals, we sometimes use the QR-factorization to reduce a computational complexity. That kind of application reveals one of the essential properties among which the QR-factorization has. Also, except for the uniqueness, QR factorization has good features even in non-square matrices, I guess. For example, we can recognize that an orthonormal basis of the column space of A (=QR) consists of the columns of Q associated with non-zero diagonal entries of R. S. Jo 02:21, 8 May 2006 (UTC)
I agree that it's possible to give only the general definition (complex rectangular matrices), and that the general definition is useful, but I think that it's better from an educational point of view to start with the simpler definition (real square matrices). However, I do not feel strongly about this.
I do not understand your last sentence. If we take
A = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{bmatrix}
then A = QR where Q is the 3-by-3 identity matrix and R = A, but the column space of A is not spanned by the first and third columns of Q. -- Jitse Niesen (talk) 05:00, 8 May 2006 (UTC)
You are right. My claim was true only if A is full rank, I guess. S. Jo 21:38, 8 May 2006 (UTC)

[edit] Householder-Example: QR=A ?

Hello there,

I'm just wondering why (in the householder-example) the resulting Q- and R-matrices don't multiply to A. Futhermore, the given Q and Q^t are not equal to I. Is the example correct?

When I calculate the products, I get QR = A and QQT = I. Could you please be more specific? What value do you take for Q, and what do you get for QQT? -- Jitse Niesen (talk) 12:59, 8 June 2006 (UTC)

Oh, you're right. I'm sorry, math is too hard for me :-)

QR=\begin{pmatrix} 6/7 & -69/175 & 58/175\\ 3/7 & 158/175 & -6/175 \\ -2/7 & 6/35 & 33/35 \end{pmatrix} \cdot \begin{pmatrix} 14 & 21 & -14 \\ 0 & 175 & -70 \\ 0 & 0 & -35 \end{pmatrix} = \begin{pmatrix} 12 & -51 & 4 \\ 6 & 167 & -68 \\ -4 & 24 & -41 \end{pmatrix} =A

No worries, happens to me all the time ;) -- Jitse Niesen (talk) 13:54, 9 June 2006 (UTC)


[edit] typo ?

"We can similarly form Givens matrices G2 and G3, which will zero the sub-diagonal elements a21 and a32, forming a rectangular matrix" should this actually say triangular instead of rectangular? -- User:Richard Giuly

Yes, indeed. Now fixed. -- Jitse Niesen (talk) 12:43, 22 October 2006 (UTC)

[edit] A more stable version of Householder?

Hi, I am new to the Wikipedia community, as far as editing goes... this is my first so please let me know if this is against protocol. After studying numerical linear algebra using the textbook by Trefethen and Bau, I noticed that there is a crucial step in the Householder implementation of the QR decomposition in this article that makes this article less than optimal in numerical stability. The operation that I would like to verify is the last one in the following snippet of pseudo code from "Numerical Linear Algebra":

for k = 1 to n

x = Ak:m,k
vk = sign(x1)||x||2e1 + x
vk = vk / ||vk||2
Ak:m,k:n = Ak:m,k:n - 2vk(vk*Ak:m,k:n)

//---------

Notation:

* = complex conjugate
Ak:m,k:n = sub-matrix of A starting at the k-th row and k-th column
sign = sign of

The reason that I say this is more accurate is because the one presented in this page requires that A be multiplied with the successive new Qn every iteration of the loop, which adds to the numerical instability of the algorithm. The pseudo code proposed by Trefethen and Bau reduces that by having a fresh copy of the original A every iteration. --Jasper 06:58, 23 January 2007 (UTC)

I'm afraid that I don't quite understand what you mean. What is the difference between the statement
Ak:m,k:n = Ak:m,k:n - 2vk(vk*Ak:m,k:n)
in Trefethen and Bau's code, and the operation
A = QkA
in the article?
I readily agree that the pseudocode is much easier to understand than the explanation in the article. Indeed, I've never been happy how the recursion is explained in the article (I think I am myself to blame for this), so please do go ahead and improve the text. -- Jitse Niesen (talk) 12:06, 24 January 2007 (UTC)
The reason that say that is because the operation you had was:
Qn = I - ...
after trying to implement that I noticed that you have to do tempA = tempA*Qn after initializing it to A with every iteration of Q. Whereas the technique I had you can get a fresh copy of A every time. —The preceding unsigned comment was added by 144.118.52.106 (talk) 17:36, 31 January 2007 (UTC).

[edit] QR decomposition for complex matrices?

hi. it seems that the algorithms that are discussed in this page are only compatible with matrices that have real elements and it seems that they can't be modified easily to be compatible with complex matrices.please guide me. —The preceding unsigned comment was added by Sina kh (talk • contribs) 11:59, 14 February 2007 (UTC).

Actually, I think that the algorithms all work for complex matrices if you replace the transpose with the conjugate transpose. For the first algorithm (Gram-Schmidt), this is mentioned in the section listed in the references. -- Jitse Niesen (talk) 04:44, 15 February 2007 (UTC)
Hi everyone.i had checked converting tranpose to transpose conjugate before and it doesn't work in householder reflectors algorithm(Q will be unitary but R won't be upper triangular).In Gram-Schmidt the algorithm have a constraint that "A" must be square(the author have mentioned it in the "definition" section).Sina kh 13:25, 27 February 2007 (UTC)
I'm afraid I don't understand you. I guess the A you're considering is not square. Why do you think R is not upper triangular when doing QR via Householder reflections? Where does it say that A has to be square for Gram-Schmidt? Did you check whether that is in fact true? -- Jitse Niesen (talk) 13:59, 28 February 2007 (UTC)

hi there.I have performed QR decomposition via householder reclection algorithm for a non-square small-sized complex matrix.I tried to follow the algorithm exactly:

A=

    -10+4i    4-5i
    2-i       8+6i
    6         7i

a1=A(:,1)=

         -10+4i
         2-i
         6

alfa=norm(a1)=sqrt(a1'*a1) ("'" means transpose conjugate)

alfa=12.53

u1=a1-(alfa*e) e=(1,0,0)t

u1=

   -22.53+4i
   2-i
   6

v1=u1/norm(u1)=

               -0.9482+0.1683i
               0.0842-0.0421i
               0.2525

q1=I(3*3)-2*v1*v1'=

                    -0.8548             0.1738 + 0.0515i   0.4789 - 0.0850i
                    0.1738 - 0.0515i    0.9823            -0.0425 + 0.0213i
                    0.4789 + 0.0850i   -0.0425 - 0.0213i   0.8725

q1*a=

         11.8198 - 4.0000i   -1.7425 + 9.0803i
         0.1775 + 0.3551i    8.1473 + 4.5214i
         -0.0000 + 1.0652i   2.1279 + 3.6281i

as it is clear,the elements (2,1) and (3,1) of the matrix "q1*a" are not zero.(against the algorithm).I continued the algorithm but i don't want to take your time more than this.finally:

Q=

  -0.8548            -0.2307 + 0.4265i   0.0231 - 0.1837i
  0.1738 - 0.0515i   -0.1566 - 0.0464i    -0.5619 - 0.7904i
  0.4789 + 0.0850i   -0.4857 + 0.7088i   0.1520 + 0.0464i

and

R=

 11.8198 - 4.0000i  -1.7425 + 9.0803i
  0.8315 - 0.6607i   0.3750 - 4.5215i
 -0.3873 + 0.1202i  -7.9021 + 4.6355i


I also performed QR decomposition in MATLAB and the result was:

Q=

    -0.7981 + 0.3192i  -0.3036 - 0.2224i   0.3220 - 0.1260i
     0.1596 - 0.0798i  -0.7472 - 0.4151i  -0.4190 + 0.2490i
     0.4789 - 0.0000i  -0.1779 - 0.3101i   0.8017 - 0.0085i

and

R=

    12.5300            -3.9904 + 7.6616i
       0               -10.7413          
       0               0

PS:I apologize if the text has some mistakes gramatically or in vocabulary.I'm not a native speaker and i am not fluent and i am not familiar with the other languages of the the article. thank you.Sina kh 17:07, 5 March 2007 (UTC)

It took me a while before I had time to go through it; sorry. It also was more complicated than I'd expected. Householder reflections behave a bit differently in complex spaces.
You are right, the algorithm does not work for complex matrices. However, it's possible to fix it. Instead of
Q = I - 2vv^\top,
you have to take
Q = I - (1+\omega) vv^* \quad\text{with}\quad \omega = \frac{\overline{v^*x}}{v^*x}.
Of course, if v and x are real vectors then ω = 1 and we get the same algorithm as before.
In your Matlab code, you write q1 = eye(3) - (1 + conj(v1'*a1)/(v1'*a1)) * v1*v1' instead of q1 = eye(3) - 2*v1*v1' and it should work.
This formulation of the method is taken from Dirk Laurie's post to NA Digest. Apparently, this is somewhere in Golub and Van Loan; I'll look it up and add to the Wikipedia article. Let me know if you need some more help.
PS: Your English is fine. -- Jitse Niesen (talk) 06:45, 10 March 2007 (UTC)
In fact, Golub & Van Loan and Stoer & Bulirsch use a slightly different (but equivalent) approach. I added a sentence about it to the article. -- Jitse Niesen (talk) 07:19, 14 March 2007 (UTC)

[edit] FULL QR decomposition

Hello everyone. Is anyone interested in adding some information for FULL QR decomposition? Since currently, everything seem to be in reduced form. —The preceding unsigned comment was added by Yongke (talk • contribs) 22:11, 6 March 2007 (UTC).

[edit] QR alorithm

There is a page on the same topic on QR algorithm, which I think should be merged in this page, and then the QR algorithm should link to this page.

--Fbianco 22:12, 15 April 2007 (UTC)

I don't think they should be merged. This page explains the QR decomposition and algorithms for computing it. The QR algorithm describes an algorithm for computing the eigenvalues of a matrix, which uses the QR decomposition. Those are different topics. -- Jitse Niesen (talk) 03:35, 16 April 2007 (UTC)

[edit] Suggested fix for number of iterations using Householder reflections

The text has- "After t iterations of this process, t = min(m,n) − 1" I think it should be t = min(m − 1,n). Consider A = \begin{pmatrix} 12 & -51 & 4 \end{pmatrix}. It neads no iterations and correctly t = min(1,2) − 1 = 0.

But

A = \begin{pmatrix} 12 \\ 6 \end{pmatrix} needs one iteration. Incorrectly t = min(2,1) − 1 = 0

If the #rows > #columns every column needs to be "triangularized" in turn
If the #columns >= #rows then every row except the first needs to be "triangularized".
Thanks for all the work ( I stumbled on this while implementing)

I am making the change-chad

[edit] Householder Problem

In the Householder section, since R = Qm...Q2Q1A, shouldn't it follow that the QR decomp is given by Q = Q1TQ2T... QmT instead of just Q = Q1Q2...Qm? -- anonymous

Yep, you're right. Thanks for bringing this to our attention. -- Jitse Niesen (talk) 16:58, 27 October 2007 (UTC)

[edit] Mention Octave instead of Matlab

I guess Wikipedia doesn't have a specific policy on using non-free software for mathematics, but I thought it would be nice to mention GNU Octave instead of Octave in the section where it mentions the numerical QR factorisation. I note that Octave's result is -Q and -R of Matlab's result.

I know lots of people have vociferous opposition to free software in mathematics, so this is why I ask before I go ahead and do it. I don't want to start an edit war. Swap 17:39, 26 October 2007 (UTC)

I'm not sure why Matlab is mentioned at all. It doesn't seem to add anything, so I removed that sentence.
On my computer, the R matrix returned by Matlab has minus signs on the diagonal just like Octave. That's not so surprising because both of them use the same routines (LAPACK) to do the factorization. I guess different versions of Matlab yield different results and that's why the article had R with the opposite sign. -- Jitse Niesen (talk) 16:58, 27 October 2007 (UTC)

[edit] total flop counts

Does someone know the total flop counts for the various QR algorithms (in particular, for a general m x n matrix, not necessarily square)?

Also, this link at the bottom of the page is bad -- maybe someone knows the new URL? The failed URL is http://www.cs.ut.ee/~toomas_l/linalg/lin2/node5.html Lavaka (talk) 16:18, 4 April 2008 (UTC)

I'll answer my own question, thanks to Golub and Van Loan's "Matrix Computations". The setup is: A is a m x n matrix, with m >= n. I assume that if m < n, then everything still holds if you swap m and n. The flop counts for various algorithms are:
"Householder QR": 2n2(m − n / 2)
"Givens QR": 3n2(m − n / 3)
"Hessenberg QR via Givens" (i.e. A is in Hessenberg form): 2n2
"Fast Givens QR": 2n2(m − n / 3)
"Modified Gram-Schmidt": 2mn2
So, if m << n, then it looks like Modified Gram-Schmidt is the winner. 131.215.105.118 (talk) 19:10, 4 April 2008 (UTC)