Matrix Factorization through Singular Value Decomposition

1. Any \(M \times N\) Matrix \(A\) (where \(M \geq 2\) and \(N \geq 2\)) when Multipied with it's Transpose \(A^T\) (or Conjugate Transpose \(A^\dagger\) if \(A\) is a Complex Matrix) give 2 following Matrices
   1. A Symmetric \(N \times N\) Matrix \(A^TA\) (or Hermitian \(N \times N\) Matrix \(A^\dagger A\) if \(A\) is a Complex Matrix).
   2. A Symmetric \(M \times M\) Matrix \(AA^T\) (or Hermitian \(M \times M\) Matrix \(AA^\dagger\) if \(A\) is a Complex Matrix).
   All such Symmetric/Hermitian Matrices have Real Eigen Values that are \(\geq 0\). Also all the Non Zero Eigen Values of all such Symmetric/Hermitian Matrices are same.
   
   If \(M < N\) then only \(M\) Eigen Values of Matrices \(A^TA\) / \(AA^T\) / \(A^\dagger A\) / \(AA^\dagger\) are considered to be Relavant Eigen Values.
   
   If \(M > N\) then only \(N\) Eigen Values of Matrices \(A^TA\) / \(AA^T\) / \(A^\dagger A\) / \(AA^\dagger\) are considered to be Relavant Eigen Values.
   
   If \(M = N\) then All Eigen Values of Matrices \(A^TA\) / \(AA^T\) / \(A^\dagger A\) / \(AA^\dagger\) are considered to be Relavant Eigen Values.
   
   Singular Values of Matrix \(A\) are Square Roots of Relavant Eigen Values of Matrices \(A^TA\) / \(AA^T\) / \(A^\dagger A\) / \(AA^\dagger\).
   
   The Unit Eigen Vectors corresponding to the Relavant Eigen Values of Matrices \(A^TA\) / \(AA^T\) / \(A^\dagger A\) / \(AA^\dagger\) are Orthonormal.
2. As per Singular Value Decomposition any \(M \times N\) Matrix \(A\) (where \(M \geq 2\) and \(N \geq 2\)) can be factorised as
   
   \(A = U\hspace{1mm}\Sigma\hspace{1mm}V^T\)
   
   or
   
   \(A = U\hspace{1mm}\Sigma\hspace{1mm}V^\dagger\)   (if \(A\) is a Complex Matrix) ...(1)
   
   where
   
   \(U\) is a \(M \times M\) (if \(M < N\)) or a \(M \times N\) (if \(M > N\)) Orthogonal / Unitary Matrix having Columns that are Orthonormal Eigen Vectors corresponding to Relavant Eigen Values of Matrix \(AA^T\) (or \(AA^\dagger\) if \(A\) is a Complex Matrix).
   
   \(V\) is a \(N \times N\) (if \(N < M\)) or a \(N \times M\) (if \(N > M\)) is an Orthogonal / Unitary Matrix having Columns that are Orthonormal Eigen Vectors corresponding to Relavant Eigen Values of Matrix \(A^TA\) (or \(A^\dagger A\) if \(A\) is a Complex Matrix).
   
   \(\Sigma\) is a \(M \times M\) (if \(M < N\)) or a \(N \times N\) (if \(M > N\)) is a Diagonal Matrix containing Singular Values of Matrix \(A\) as it's Main Diagonal.
   
   
3. The following gives the Steps for Derivation of formula for Singular Value Decomposition for any \(M \times N\) Real Matrix \(A\) as given in equation set (1). Please note that for any \(M \times N\) Complex Matrix \(A\), the Steps for Derivation of formula for it's Singular Value Decomposition will be similar with the exception that in place of a Tranpose Operations \(T\), Conjugate Transpose Operations \(\dagger\) are used.
   
   The Eigen Vector/Diagonal Matrix Decomposition of Matrices \(AA^T\) and \(A^TA\) are given as follows
   
   \(AA^T = P_1D_1{P_1}^-1\)   ...(2)
   
   \(A^T A = P_2D_2{P_2}^-1\)   ...(3)
   
   where
   
   \(P_1 = M \times M\) Matrix containing Eigen Vectors for Matrix \(AA^T\)
   
   \(D_1 = M \times M\) Diagonal Matrix containing Eigen Values for Matrix \(AA^T\)
   
   \(P_2 = N \times N\) Matrix containing Eigen Vectors for Matrix \(A^TA\)
   
   \(D_2 = N \times N\) Diagonal Matrix containing Eigen Values for Matrix \(A^TA\)
   
   Now, since the Unit Eigen Vectors of Relavant Eigen Values of Matrices \(AA^T\) and \(A^TA\) are Orthonormal, the Matrices containing them as Columns are Orthogonal (or Unitary if \(A\) is a Complex Matrix). Hence equations (2) and (3) given above can also be represented as
   
   \(AA^T = UDU^T\)   ...(4)
   
   \(A^TA = VDV^T\)   ...(5)
   
   where
   
   \(D = \) Diagonal Matrix containing Relavant Eigen Values for Matrix \(AA^T\) and \(A^TA\) as it's Main Diagonal. If \(M>N\) it is a \(N\times N\) Matrix. Otherwize it is a \(M\times M\) Matrix.
   
   \(U = \) Orthogonal Matrix contaning Orthonormal Unit Eigen Vectors corresponding to Relavant Eigen Values of Matrix \(AA^T\) as it's Columns. If \(M>N\) it is a \(M\times N\) Matrix. Otherwize it is a \(M\times M\) Matrix.
   
   \(V = \) Orthogonal Matrix contaning Orthonormal Unit Eigen Vectors corresponding to Relavant Eigen Values of Matrix \(A^TA\) as it's Columns. If \(M>N\) it is a \(N\times N\) Matrix. Otherwize it is a \(N\times M\) Matrix.
   
   Now, the Diagonal Matrix \(D\) containing the Relavant Eigen Values for Matrix \(AA^T\) and \(A^TA\) given in equation (4) and (5) above can be written as a Product of 2 Diagonal Matrices \(\Sigma\) each containing the Singular Values for Matrix \(AA^T\) and \(A^TA\). Hence equations (4) and (5) can be given as
   
   \(AA^T = U\Sigma \Sigma U^T\)   ...(6)
   
   \(A^TA = V\Sigma \Sigma V^T\)   ...(7)
   
   Now, since \(U\) and \(V\) are Orthogonal Matrices, therefore \(U^TU = V^TV = I\) (Identity Matrix). Hence we can write equations (6) and (7) as
   
   \(AA^T = U\Sigma V^T V \Sigma U^T\)   ...(8)
   
   \(A^TA = V\Sigma U^T U \Sigma V^T\)   ...(9)
   
   Since \({(U\Sigma V^T)}^T = V \Sigma U^T\), from equations (8) and (9) we get
   
   \(A=U\Sigma V^T\)   ...(10)
4. For any \(M\times N\) Matrix \(A\), the Matrices \(U\), \(V\) and \(\Sigma\) can be obtained in following 5 configurations
   1. Compact: In this configuration
      
      U: M \(\times\) N, S: N \(\times\) N, V: N \(\times\) N   (if \(M \geq N\))
      
      U: M \(\times\) M, S: M \(\times\) M, V: N \(\times\) M   (if \(M < N\))
      
      If \(M \geq N\) for Matrix \(A\), the \(N \times N\) Matrix \(V\) is formed using Unit Eigen Vectors of Matrix \(A^TA\) and the \(N \times N\) Diagonal Matrix \(\Sigma\) is formed using Square Root of Eigen Values of \(A^TA\). Then the \(M\times N\) Matrix \(U\) containing Unit Eigen Vectors for Relavant Eigen Values of Matrix \(AA^T\) is calculated by Post Multiplying equation (10) above by \(V{\Sigma}^{-1}\) as follows
      
      \(AV{\Sigma}^{-1}=U\Sigma V^TV{\Sigma}^{-1}\)   ...(11)
      
      \(\Rightarrow U=AV{\Sigma}^{-1}\)   ...(12)
      
      If \(M < N\) for Matrix \(A\), the \(M \times M\) Matrix \(U\) is formed using Unit Eigen Vectors of Matrix \(AA^T\) and the \(M \times M\) Diagonal Matrix \(\Sigma\) is formed using Square Root of Eigen Values of \(AA^T\). Then the \(N\times M\) Matrix \(V\) containing Unit Eigen Vectors for Relavant Eigen Values of Matrix \(A^TA\) is calculated by Pre Multiplying equation (10) above by \({\Sigma}^{-1}U^T\) as follows
      
      \({\Sigma}^{-1}U^TA={\Sigma}^{-1}U^T U\Sigma V^T\)   ...(13)
      
      \(\Rightarrow {\Sigma}^{-1}U^TA=V^T\)
      
      \(\Rightarrow V={({\Sigma}^{-1}U^TA)}^T\)
      
      \(\Rightarrow V=A^T U {\Sigma}^{-1}\)   ...(14)
   2. U: M \(\times\) N, S: N \(\times\) N, V: N \(\times\) N: In this configuration, the \(N \times N\) Matrix \(V\) is formed using All Unit Eigen Vectors of Matrix \(A^TA\) and the \(N \times N\) Diagonal Matrix \(\Sigma\) is formed using Square Root of All Eigen Values of \(A^TA\). Then the \(M\times N\) Matrix \(U\) containing Unit Eigen Vectors for Relavant Eigen Values of Matrix \(AA^T\) is calculated by Post Multiplying equation (10) above by \(V{\Sigma}^{-1}\) as given in equation (11) and (12) above.
   3. U: M \(\times\) M, S: M \(\times\) M, V: N \(\times\) M: In this configuration, the \(M \times M\) Matrix \(U\) is formed using All Unit Eigen Vectors of Matrix \(AA^T\) and the \(M \times M\) Diagonal Matrix \(\Sigma\) is formed using Square Root of All Eigen Values of \(AA^T\). Then the \(N\times M\) Matrix \(V\) containing Unit Eigen Vectors for Relavant Eigen Values of Matrix \(A^TA\) is calculated by Pre Multiplying equation (10) above by \({\Sigma}^{-1}U^T\) as given in equation (13) and (14) above.
   4. U: M \(\times\) M, S: M \(\times\) N, V: N \(\times\) N, (Extra Zero Columns in U): In this configuration, the \(N \times N\) Matrix \(V\) is formed using All Unit Eigen Vectors of Matrix \(A^TA\) and the \(M \times N\) Rectangular Diagonal Matrix \(\Sigma\) is formed using Square Root of All Eigen Values of \(A^TA\) (with additional padding of 0 values). Then the \(M\times M\) Matrix \(U\) containing Unit Eigen Vectors for Relavant Eigen Values and Additional Zero Vector Columns (when \(M > N\)) of Matrix \(AA^T\) is calculated by Post Multiplying equation (10) above by \(V{\Sigma}^{-1}\) as given in equation (11) and (12) above. Please note that in this case \(\Sigma^{-1}\) is a \(N \times M\) Matrix.
   5. U: M \(\times\) M, S: M \(\times\) N, V: N \(\times\) N, (Extra Zero Columns in V): In this configuration, the \(M \times M\) Matrix \(U\) is formed using All Unit Eigen Vectors of Matrix \(AA^T\) and the \(M \times N\) Rectangular Diagonal Matrix \(\Sigma\) is formed using Square Root of All Eigen Values of \(AA^T\) (with additional padding of 0 values). Then the \(N\times N\) Matrix \(V\) containing Unit Eigen Vectors for Relavant Eigen Values and Additional Zero Vector Columns (when \(M < N\)) of Matrix \(A^TA\) is calculated by Pre Multiplying equation (10) above by \({\Sigma}^{-1}U^T\) as given in equation (13) and (14) above. Please note that in this case \(\Sigma^{-1}\) is a \(M \times N\) Matrix.
   
   Please note that the Inverse of a Any Diagonal Matrix containing 0 values in it's Main Diagonal is found by Inverting/Reciprocating the Non-Zero values of Main Diagonal.
   
   Also note that all the Tranpose Operations \(T\) given above must be replaced by Conjugate Transpose Operations \(\dagger\) if \(A\) is a Complex Matrix.