Matrix Factorization through QR Decomposition using Gram-Schmidt Process

1. Given any \(M \times N\) Matrix \(A\) as follows
   
   \(A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{m1} & a_{m2} & ... & a_{mn}\end{bmatrix}\)   ...(1)
   
   QR Decomposition of Matrix \(A\) invloves Factoring Matrix \(A\) into 2 Matrices as follows
   
   \(A=QR\)   ...(2)
   
   where
   1. \(Q\) is an Orthogonal Matrix having \(M\) Rows and \(K\) Columns (where \(1 \leq K \leq N\) ).
   2. \(R\) is Right Triangular Matrix containing \(K\) Rows and \(N\) Columns.
2. For any \(M \times N\) Matrix \(A\) (as given above) containing \(N\) Vectors \(V_1, V_2, ..., V_n\) as Columns, the corresponding Orthogonal Matrix \(Q\) containing Mutually Orthonormal \(K\) Vectors \(M_1, M_2, ..., M_k\) (where \(1 \leq K \leq N\) ) can be found using Gram-Schmidt Process as follows
   1. Add the First Vector/Column \(V_1\) of Matrix \(A\) as the First Vector/Column \(M_1\) of Matrix \(Q\).
   2. Calculate the Orthogonal Rejection OF Vector \(V_2\) of Matrix \(A\) FROM Vector Sub-space formed by Matrix \(Q\). If the Orthogonal Rejection thus obtained is a Non-Null Vector, add it to the Matrix \(Q\) as its next Vector/Column \(M_2\).
   3. Calculate the Orthogonal Rejection OF all subsequent Vectors \(V_n\) of Matrix \(A\) FROM Vector Sub-space formed by then Current Matrix \(Q\). If the Orthogonal Rejection thus obtained is a Non-Null Vector, add it to the Matrix \(Q\) as its next Vector/Column \(M_k\).
   4. Once all the Orthogonal Non-Null Rejection Vectors have been added to Matrix \(Q\), convert all the Vectors/Columns in Matrix \(Q\) to Unit Vectors, thus converting the Matrix \(Q\) to Orthogonal Matrix.
3. Once the Orthogonal Matrix \(Q\) corresponding to Matrix \(A\) is found using the Gram-Schmidt Process, the \(R\) Matrix is calculated as follows
   
   \(A=QR\)   ...(From equation 2)
   
   Pre-Multiplying Both Sides of equation (2) with \(Q^T\) we get
   
   \(Q^TA=Q^TQR\hspace{.5cm}\Rightarrow Q^TA=IR\hspace{.5cm}\Rightarrow Q^TA=R\)   (\(\because Q^TQ=I\)) ...(3)
4. The following gives the Calculations for Finding Orthogonal Vectors/Columns \(M_1, M_2, ..., M_n\) using Gram-Schmidt Process
   
   Let \(P_1\) be the Projection Matrix Corresponding to Vector \(V_1\) (or Vector \(M_1\)). Therefore the Rejection Matrix \(R_1\) Corresponding to Vector \(V_1\) is given as
   
   \(R_1=I-P_1\)
   
   Now, Rejection OF Vector \(V_2\) (i.e. Vector \(M_2\)) FROM Vector \(V_1\) (or Vector \(M_1\)) is given as
   
   \(M_2= R_1V_2\hspace{.5cm}\Rightarrow M_2=(I-P_1)V_2\hspace{.5cm}\Rightarrow M_2=(V_2-P_1V_2)\)   ...(4)
   
   Now, Let \(P_2\) be the Projection Matrix Corresponding to Vector \(M_2\). Since \(M_1\) and \(M_2\) are Mutually Orthogonal Vectors, therefore the Projection Matrix \(P_{12}\) Corresponding to the Vector Space formed by Vectors \(M_1\) and \(M_2\) is Sum of Projection Matrices \(P_1\) and \(P_2\). That is
   
   \(P_{12}=P_1 + P_2\)
   
   Hence, the Rejection Matrix \(R_{12}\) Corresponding to the Vector Space formed by Vectors \(M_1\) and \(M_2\) is given as
   
   \(R_{12}=I-P_{12}=I-P_1 - P_2\)
   
   Therefore Rejection OF Vector \(V_3\) (i.e. Vector \(M_3\)) FROM the Vector Space formed by Vectors \(M_1\) and \(M_2\) is given as
   
   \(M_3= R_{12}V_3\hspace{.5cm}\Rightarrow M_3=(I-P_1-P_2)V_3\hspace{.5cm}\Rightarrow M_3=(V_3-P_1V_3-P_2V_3)\)   ...(5)
   
   Now, Let \(P_3\) be the Projection Matrix Corresponding to Vector \(M_3\). Since \(M_1\), \(M_2\) and \(M_3\) are Mutually Orthogonal Vectors, therefore the Projection Matrix \(P_{123}\) Corresponding to the Vector Space formed by Vectors \(M_1\), \(M_2\) and \(M_3\) is Sum of Projection Matrices \(P_1\), \(P_2\) and \(P_3\). That is
   
   \(P_{123}=P_1 + P_2 + P_3\)
   
   Hence, the Rejection Matrix \(R_{123}\) Corresponding to the Vector Space formed by Vectors \(M_1\), \(M_2\) and \(M_3\) is given as
   
   \(R_{123}=I-P_{123}=I-P_1 - P_2 - P_3\)
   
   Therefore Rejection OF Vector \(V_4\) (i.e. Vector \(M_4\)) FROM the Vector Space formed by Vectors \(M_1\), \(M_2\) and \(M_3\) is given as
   
   \(M_4= R_{123}V_4\hspace{.5cm}\Rightarrow M_4=(I-P_1-P_2-P_3)V_4\hspace{.5cm}\Rightarrow M_4=(V_4-P_1V_4-P_2V_4-P_3V_4)\)   ...(6)
   
   \(\vdots\)
   \(\vdots\)
   
   Likewise, Let \(P_{n-1}\) be the Projection Matrix Corresponding to Vector \(M_{n-1}\). Since \(M_1\), \(M_2\), \(M_3\), ... and \(M_{n-1}\) are Mutually Orthogonal Vectors, therefore the Projection Matrix \(P_{123...(n-1)}\) Corresponding to the Vector Space formed by Vectors \(M_1\), \(M_2\), \(M_3\), ... and \(M_{n-1}\) is Sum of Projection Matrices \(P_1\), \(P_2\), \(P_3\), ... and \(P_{n-1}\). That is
   
   \(P_{123...(n-1)}=P_1 + P_2 + P_3 + ... + P_{n-1}\)
   
   Hence, the Rejection Matrix \(R_{123...(n-1)}\) Corresponding to the Vector Space formed by Vectors \(M_1\), \(M_2\), \(M_3\), ... and \(M_{n-1}\) is given as
   
   \(R_{123...(n-1)}=I-P_{123...(n-1)}=I-P_1 - P_2 - P_3 - ... - P_{n-1}\)
   
   Therefore Rejection OF Vector \(V_k\) (i.e. Vector \(M_k\)) FROM the Vector Space formed by Vectors \(M_1\), \(M_2\), \(M_3\), ... and \(M_{k-1}\) is given as
   
   \(M_n= R_{123...(n-1)}V_n\hspace{.5cm}\Rightarrow M_n=(I-P_1 - P_2 - P_3 - ... - P_{n-1})V_n\hspace{.5cm}\Rightarrow M_n=V_n-P_1V_n-P_2V_n-P_3V_n - ... - P_{n-1}V_n\)   ...(7 )
   
   Please note that out of all the Vectors \(M_1, M_2,..., M_n\) that are obtained using above calculations, Only the Non-Null Vectors become a part of the Matrix \(Q\). Subsequently, all the Vectors/Columns in Matrix \(Q\) are converted to Unit Vectors, thus converting the Matrix \(Q\) to Orthogonal Matrix.