Eritque Arcus Math Notes

QR factorization

3 min read

𝐴=𝑄𝑅
where:

  • 𝐴 is 𝑚×𝑛
  • 𝑅 is square upper triangular matrix
  • 𝑄 is Orthogonal matrix
    Features:
  • QR factorization always exists but may not unique
  • QR factorization only exists when Determinant is 0 and all diagonal elements >0.


given by numpy.linalg.qr

Steps

Gram-Schmidt

most intuitive but not stable
ref: https://kwokanthony.medium.com/important-decomposition-in-linear-algebra-detailed-explanation-on-qr-decomposition-by-classical-3f8f5425915f

  1. for column ⃗𝑎𝑖 in 𝐴, calculate 𝑢𝑖=𝑎𝑖−(∑𝑖−1𝑗=1𝑝𝑟𝑜𝑗𝑢𝑗−1𝑎𝑗)=𝑎𝑖−(∑𝑖−1𝑗=1𝑎𝑗⋅𝑢𝑗−1𝑢𝑗−1⋅𝑢𝑗−1𝑎𝑗).
  2. then 𝑞𝑖=𝑢𝑖‖𝑢𝑖‖ which is column in 𝑄
  3. repeat for all columns to get 𝑄.
  4. 𝑅=𝑄𝑇𝐴.

Householder

ref: https://kwokanthony.medium.com/detailed-explanation-with-example-on-qr-decomposition-by-householder-transformation-5e964d7f7656

cost 𝑂(𝑛3)

Steps

  1. init 𝑅0=𝐴
  2. for column ⃗𝑎𝑖 in 𝐴, calculate ⃗𝑣𝑖=⃗𝑎𝑖±‖⃗𝑎𝑖‖2𝑒𝑖 where 𝑒1 is standard basis. Choose the sign to avoid cancellation.
  3. 𝑤𝑖=⃗𝑣𝑖‖⃗𝑣𝑖‖, 𝑄𝑖=𝐼−2𝑤𝑖𝑤𝑇𝑖 and 𝑅𝑖=𝑄𝑖𝑅𝑖−1.
  4. keep this calculation column by column with only consider sub-matrix until 𝑅𝑖 is upper right triangle matrix.
  5. 𝑄=∏𝑄𝑖, 𝑅 is last result of 𝑅𝑖.

2x2 example

𝐴=[3472] ⃗𝑣1=[34]±√9+16[10]=[84] 𝑤1=1√64+26[84] 𝑄1=𝐼−2𝑤1𝑤𝑇1=[−3/5−4/5−4/53/5]

Then

𝑅1=𝑄1𝑅0=𝑄1𝐴=[−50−295−225]

Since 𝑅 is already in right upper triangle matrix. We are done with 𝑅=𝑅1 and

𝑄=𝑄1=[−35−45−4535]

It’s consist with

>>> numpy.linalg.qr(np.matrix("3,7;4,2"))  
QRResult(Q=matrix([[-0.6, -0.8],  
       [-0.8,  0.6]]), R=matrix([[-5. , -5.8],  
       [ 0. , -4.4]]))

Givens

ref: https://kwokanthony.medium.com/detailed-explanation-with-example-on-qr-decomposition-by-givens-rotation-6e7bf664fbdd

𝐺=[cos(𝜃)sin(𝜃)−sin(𝜃)cos(𝜃)]

For higher dimensions, we need to use sth like

𝐺𝑥𝑦=[cos(𝜃)sin(𝜃)0−sin(𝜃)cos(𝜃)0001] 𝐺𝑦𝑧=[1000cos(𝜃)sin(𝜃)0−sin(𝜃)cos(𝜃)] 𝐺𝑥𝑧=[cos(𝜃)0sin(𝜃)010−sin(𝜃)0cos(𝜃)]

depend on which dimension.

Steps

  1. For column 𝑎𝑖 in 𝐴, use 𝐺 to build it to consist with right upper triangle matrix
  2. e.g. if we need to remove 2nd element in 3×3 matrix, we need to use 𝐺𝑥𝑦 with 𝑐𝑜𝑠(𝜃)=𝑥𝑟 and sin(𝜃)=−𝑦𝑟 where 𝑥 is 1st element and 𝑦 is the 2nd, and 𝑟=√𝑥2+𝑦2.
  3. Then get 𝐴𝑖=𝐴𝑖−1𝐺. Then check if we need to remove another element (like 3rd element) as well.
  4. Repeat this for all columns.
  5. 𝑄=∏𝐺𝑇𝑖, 𝑅 is the last 𝐴𝑖.

Costs

if 𝐴 is upper Hessenberg matrix, it only requires 𝑛 Givens rotation.
otherwise 𝑂(𝑛2).

Graph View

Backlinks