Householder transformation | Householder Reflection with QR Decomposition

Householder Reflection or Transformation is one the methods of decomposing a matrix into an Orthogonal Matrix (Q) and Right Upper Triangular Matrix (R). It helps to solve systems of equation using backward substitution.

1. Householder Transformation and QR
Decomposition
Isaac Amornortey Yowetu
NIMS-GHANA
January 4, 2021

2. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

3. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Introduction
The Householder matrix (reector) is a unitary (or orthogonal)
matrix that is often used to decompose a matrix into an
triangular matrix. In particular,
Householder matrices are usually used to destroy the entries
below the main diagonal of a matrix.
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

4. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Householder Properties
The Householder Transformation or Matrix has the following
properties:
IIt is symmetric
H=H
T
IIt is also orthogonal
H
T
=H
1
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

5. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Consider H to be the Householder Matrix:
Proof: Symmetry
H=H
T
(1)
H=I2vv
T
(2)
H
T
= (I2vv
T
)
T
(3)
=I
T
2(vv
T
)
T
(4)
=I
T
2(v
T
)
T
v
T
(5)
=I2vv
T
(6)
=H (7)
Hence, proved!
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

6. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Consider H to be the Householder Matrix:
Proof: Orthogonality
H
T
=H
1
(8)
H
T
H=H
1
H=I (9)
H
T
H= (I2vv
T
)
T
(I2vv
T
) (10)
= (I2vv
T
)(I2vv
T
) (11)
=I2(vv
T
)2(vv
T
) +4vv
T
vv
T
(12)
=I4(vv
T
) +4v(v
T
v)v
T
(13)
=I4(vv
T
) +4vv
T
(14)
=I (15)
Hence;proved! (16)
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

7. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Householder Reection(Matrix) Derivation
1. u
Considering n dimensional vectorx= [x1;x2; :::;xn]
T
and
e= [1;0; :::;0]
T
which a rst standard basis vector.
u=x jjxjje1
2. v
v=
u
jjujj
3.
H=I2vv
T
=I
2uu
T
jjujj
2
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

8. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Remark
When the Householder Matrix H is a applied to x, it obtains
its reection. Say,
x
0
=Hx
Proof
x
0
=Hx= (I2vv
T
)x=

I
2uu
T
jjujj
2

x (17)
jjujj
2
= (x jjxjje1)
T
(x jjxjje1) (18)
= (x
T
jjxjje
T
1)(x jjxjje1) (19)
=x
T
x jjxjjx
T
e1 jjxjje
T
1x+jjxjj
2
e
T
1e1(20)
=jjxjj
2
2jjxjjx1+jjxjj
2
(21)
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

9. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Proof continues...
=2jjxjj
2
2jjxjjx1 (22)
=2(jjxjj
2
jjxjjx1) (23)
x
0
=

I
2u(x jjxjje1)
T
2(jjxjj
2
jjxjjx1)

x (24)
=x
2u(x
T
x jjxjje
T
1x)
2(jjxjj
2
jjxjjx1)
(25)
=x
u(jjxjj
2
jjxjjx1)
(jjxjj
2
jjxjjx1)
(26)
=xu (27)
=x(x jjxjje1) (28)
=jjxjje1 (29)
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

10. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Question 1
Consider the matrix
B=
2
4
11 1
1 3 3
11 5
3
5
using Householder Reection, determine the QR Factorization.
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

11. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Solution
We considerx1= [1;11]
T
andjjx1jj2=
p
3
u1=x1 jjx1jje1
=
2
4
1
1
1
3
5
p
3
2
4
1
0
0
3
5=
2
4
2:7321
1:0000
1:0000
3
5
v1=
u1
jju1jj
=
2
4
0:8881
0:3251
0:3251
3
5
H1=I2vv
T
=
2
4
0:5774 0:57740:5774
0:5774 0:7887 0:2113
0:5774 0:2113 0:7887
3
5
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

12. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Solution Continues...
H1B=
2
4
0:5774 0:57740:5774
0:5774 0:7887 0:2113
0:5774 0:2113 0:7887
3
5
2
4
11 1
1 3 3
11 5
3
5
R1=
2
4
1:7321 2:88681:7321
0 1:5774 4:0000
0 0:4226 4:0000
3
5
Q1=H1=
2
4
0:5774 0:57740:5774
0:5774 0:7887 0:2113
0:5774 0:2113 0:7887
3
5
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

13. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Solution continues...
We considerx2= [0;1:5774;0:4226]
T
andjjx2jj2=1:6330
u2=x2 jjx2jje2
=
2
4
0
1:5774
0:4226
3
51:6330
2
4
0
1
0
3
5=
2
4
0
0:0556
0:4226
3
5
v2=
u2
jju2jj
=
2
4
0
0:1305
0:9914
3
5
H2=I2vv
T
=
2
4
1:0000 0 0
0 0:9659 0:2588
0 0:25880:9659
3
5
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

14. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Solution Continues...
H2R1=
2
4
1:0000 0 0
0 0:9659 0:2588
0 0:25880:9659
3
5
2
4
1:7321 2:88681:7321
0 1:5774 4:0000
0 0:4226 4:0000
3
5
R2=
2
4
1:7321 2:88681:7321
0 1:6330 4:8990
0 0 2:8284
3
5
Q2=H1H2
=
2
4
0:5774 0:57740:5774
0:5774 0:7887 0:2113
0:5774 0:2113 0:7887
3
5
2
4
1:0000 0 0
0 0:9659 0:2588
0 0:25880:9659
3
5
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

15. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Solution:
Q=Q2
2
4
0:57740:40820:7071
0:57740:8165 0
0:57740:4082 0:7071
3
5
R=R2
2
4
1:7321 2:88681:7321
0 1:6330 4:8990
0 0 2:8284
3
5
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

16. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Question 2
Find QR Decomposition using Householder Method of the
matrix
B=
2
6
6
4
11 4
1 42
1 4 2
11 0
3
7
7
5
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

17. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Solution
We considerx1= [1;1;1;1]
T
andjjx1jj2=2
u1=x1 jjx1jje1
=
2
6
6
4
1
1
1
1
3
7
7
5
2
2
6
6
4
1
0
0
0
3
7
7
5
=
2
6
6
4
1
1
1
1
3
7
7
5
v1=
u1
jju1jj
=
2
6
6
4
0:5000
0:5000
0:5000
0:5000
3
7
7
5
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

18. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
H1=
2
6
6
4
0:50 0:50 0:50 0:50
0:50 0:500:500:50
0:500:50 0:500:50
0:500:500:50 0:50
3
7
7
5
H1B=
2
6
6
4
0:50 0:50 0:50 0:50
0:5000 0:50000:500:50
0:500:50 0:500:50
0:500:500:50 0:50
3
7
7
5
2
6
6
4
11 4
1 42
1 4 2
11 0
3
7
7
5
R1=
2
6
6
4
2 3 2
0 0 0
0 0 4
05 2
3
7
7
5
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

19. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Solution Continues...
Q1=H1=
2
6
6
4
0:5000 0:5000 0:5000 0:5000
0:5000 0:50000:50000:5000
0:50000:5000 0:50000:5000
0:50000:50000:5000 0:5000
3
7
7
5
We considerx2= [0;0;0;5]
T
andjjx2jj2=5
u2=x2 jjx2jje2
=
2
6
6
4
0
0
0
5
3
7
7
5
5
2
6
6
4
0
1
0
0
3
7
7
5
=
2
6
6
4
0
5
0
5
3
7
7
5
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

20. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Solution continues...
v2=
u2
jju2jj
=
2
6
6
4
0
0:7071
0
0:7071
3
7
7
5
H2=I2vv
T
=
2
6
6
4
1:00 0 0 0
0 0 0 1
0 0 1 0
01 0 0
3
7
7
5
H2R1=
2
6
6
4
1:00 0 0 0
0 0 0 1
0 0 1 0
01 0 0
3
7
7
5
2
6
6
4
2 3 2
0 0 0
0 0 4
05 2
3
7
7
5
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

21. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Solution Continues...
R2=
2
6
6
4
2 3 2
0 52
0 0 4
0 0 0
3
7
7
5
Q2=H1H2
=
2
6
6
4
0:50 0:50 0:50 0:50
0:50 0:500:500:50
0:500:50 0:500:50
0:500:500:50 0:50
3
7
7
5
2
6
6
4
1:00 0 0 0
0 0 0 1
0 0 1 0
01 0 0
3
7
7
5
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

22. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
Solution:
Q=Q2
2
6
6
4
0:500:50 0:50 0:50
0:50 0:500:500:50
0:50 0:50 0:500:50
0:500:500:500:50
3
7
7
5
R=R2
2
6
6
4
2 3 2
0 52
0 0 4
0 0 0
3
7
7
5
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition

23. Introduction
Proof of Householder Transformation Properties
Householder Reection Derivation
Application of Householder Reection to QR Decomposition
End
THANKYOU
Reference
www.statlect.com/matrix-algebra/Householder-matrix
Isaac Amornortey Yowetu Householder Transformation and QR Decomposition