Majid Hosseini avatar Majid Hosseini committed 0e549a6 Draft

rank factorisation is added

Comments (0)

Files changed (4)

biblio/linalgdecompose.bib

+<<<<<<< local
+@BOOK{ lapackuserguide1999,
+	title = "LAPACK Users' guide",
+	publisher = "Society for Industrial Mathematics",
+	year = "1999",
+	author = "Anderson, E. and Bai, Z. and Bischof, C. and Blackford, S. and Demmel, J. and Dongarra, J. and Du Croz, J. and Greenbaum, A. and Hammarling, S. and McKenney, A. and others",
+	volume = "9"
+=======
 % This file was created with JabRef 2.5.
 % Encoding: UTF-8
 
 	J. and Dongarra, J. and Du Croz, J. and Greenbaum, A. and Hammarling,
 	S. and McKenney, A. and others},
   volume = {9}
+>>>>>>> other
 }
 
-@BOOK{golubvanloan1996matrix,
-  title = {Matrix computations},
-  publisher = {Johns Hopkins Univ Pr},
-  year = {1996},
-  author = {Golub, G.H. and Van Loan, C.F.},
-  edition = {3rd edition}
+@BOOK{ golubvanloan1996matrix,
+	title = "Matrix computations",
+	publisher = "Johns Hopkins Univ Pr",
+	year = "1996",
+	author = "Golub, G.H. and Van Loan, C.F.",
+	edition = "3rd edition"
 }
 
+<<<<<<< local
+@ARTICLE{ hager1984condition,
+	author = "William W. Hager",
+	title = "Condition estimates",
+	journal = "SIAM J. Sci. Stat. Comput.",
+	year = "1984",
+	volume = "5",
+	pages = "311--316",
+	number = "2"
+=======
 @INPROCEEDINGS{Escribano2001,
   author = {Gonz\'{a}lez-Escribano, Arturo and Gemund, Arjan J. C. van and Carde\~{n}oso-Payo,
 	Valent\'{\i}n and Alonso-L\'{o}pez, Judith and Mart\'{\i}n-Garc\'{\i}a,
   owner = {majid},
   timestamp = {2012.08.10},
   url = {http://dl.acm.org/citation.cfm?id=647052.715598}
+>>>>>>> other
 }
 
+<<<<<<< local
+@BOOK{ hornjohnson1986matrixanalysis,
+	title = "Matrix analysis",
+	publisher = "Cambridge Univ. Press, Cambrige",
+	year = "1986",
+	author = "Charles R. Johnson and Roger A. Horn"
+=======
 @TECHREPORT{Guitart2001,
   author = {J. Guitart, X. Martorell, J. Torres, and E. Ayguadé},
   title = {Improving Java Multithreading Facilities: the Java Nanos Environment},
   type = {Research Report UPC-DAC-2001-8, Computer Architecture Department},
   owner = {majid},
   timestamp = {2012.08.10}
+>>>>>>> other
 }
 
+<<<<<<< local
+@ARTICLE{ higham2000block,
+	author = "Nicholas J. Higham and Fran{\c{c}}oise Tisseur",
+	title = "A block algorithm for matrix 1-norm estimation, with an application to 1-norm pseudospectra",
+	journal = "SIAM J. Matrix Anal. Appl.",
+	year = "2000",
+	volume = "21",
+	pages = "1185--1201"
+}
+
+@MANUAL{ matlab2012docs,
+	title = "MATLAB R2012a Documentation",
+	author = "Mathworks Inc.,"
+}
+
+@ARTICLE{ hogbenhandbook,
+	author = "Leslie Hogben",
+	title = "{Handbook of linear algebra}",
+	year = "2007",
+	publisher = "CRC Press"
+}
+
+@ARTICLE{ moler1973algorithm,
+	author = "Moler, C.B. and Stewart, G.W.",
+	title = "An algorithm for generalized matrix eigenvalue problems",
+	journal = "SIAM Journal on Numerical Analysis",
+	year = "1973",
+	pages = "241--256"
+=======
 @MANUAL{matlab2012docs,
   title = {MATLAB R2012a Documentation},
   author = {Mathworks Inc.,},
   year = {2012}
+>>>>>>> other
 }
 
-@ARTICLE{moler1973algorithm,
-  author = {Moler, C.B. and Stewart, G.W.},
-  title = {An algorithm for generalized matrix eigenvalue problems},
-  journal = {SIAM Journal on Numerical Analysis},
-  year = {1973},
-  pages = {241--256}
+@BOOK{ molernumericalcompmatlab,
+	title = "Numerical computing with MATLAB",
+	publisher = "Society for Industrial Mathematics",
+	year = "2004",
+	author = "Cleve B. Moler"
 }
 
-@BOOK{molernumericalcompmatlab,
-  title = {Numerical computing with MATLAB},
-  publisher = {Society for Industrial Mathematics},
-  year = {2004},
-  author = {Cleve B. Moler}
+@ARTICLE{ navarra2010guide,
+	author = "Navarra, A. and Simoncini, V.",
+	title = "A Guide to Empirical Orthogonal Functions for Climate Data Analysis",
+	year = "2010",
+	publisher = "Springer Verlag"
 }
 
-@ARTICLE{navarra2010guide,
-  author = {Navarra, A. and Simoncini, V.},
-  title = {A Guide to Empirical Orthogonal Functions for Climate Data Analysis},
-  year = {2010},
-  publisher = {Springer Verlag}
+@ARTICLE{ rice1966theory,
+	author = "Rice, J.R.",
+	title = "A theory of condition",
+	journal = "SIAM Journal on Numerical Analysis",
+	year = "1966",
+	volume = "3",
+	pages = "287--310",
+	number = "2"
 }
 
+<<<<<<< local
+=======
 @ARTICLE{rice1966theory,
   author = {Rice, J.R.},
   title = {A theory of condition},
   timestamp = {2012.08.08}
 }
 
-
-@ARTICLE{higham2000block,
-  author = {Nicholas J. Higham and Fran{\c{c}}oise Tisseur},
-  title = {A block algorithm for matrix 1-norm estimation, with an application
-	to 1-norm pseudospectra},
-  journal = {SIAM J. Matrix Anal. Appl.},
-  year = {2000},
-  volume = {21},
-  pages = {1185--1201}
-}
-
-
-
-@ARTICLE{hager1984condition,
-  author = {William W. Hager},
-  title = {Condition estimates},
-  journal = {SIAM J. Sci. Stat. Comput.},
-  year = {1984},
-  volume = {5},
-  pages = {311--316},
-  number = {2}
-}
-
-
-@ARTICLE{hogbenhandbook,
-  author = {Leslie Hogben},
-  title = {{Handbook of linear algebra}},
-  year = {2007},
-  publisher = {CRC Press}
-}
-
-
-
-@BOOK{hornjohnson1986matrixanalysis,
-  title = {Matrix analysis},
-  publisher = {Cambridge Univ. Press, Cambrige},
-  year = {1986},
-  author = {Charles R. Johnson and Roger A. Horn}
-}
-
-
-
+>>>>>>> other

decompose-eigenvaluesrelated.tex

 the corresponding diagonal elements of $T$, $\lambda_i = S_{ii}/T_{ii}$, are the
 generalised eigenvalues that solve the generalised eigenvalue problem
 $Av=\lambda Bv$, where $\lambda$ is an unknown scalar and $v$ is an unknown
-nonzero vector\cite{hornjohnson1986matrixanalysis,golubvanloan1996matrix}.
+nonzero vector\cite{hornjohnson1990matrix,golubvanloan1996matrix}.
 
 \subsubsection{Real QZ Decomposition}
 Real version of QZ Decomposition: $A=QSZ^T$ and $B=QTZ^T$ where $A$, $B$, $Q$,

decompose-linearequationsrelated.tex

 	    0 & I 
     \end{pmatrix}. 
 \end{equation}
-\section{Rank factorisation}
+\section{Rank factorization}
+Given an $m \times n$ matrix $A$ of rank $r$, a rank decomposition or rank factorization of $A$ is a product $A\ =\ CF$, where $C$ is an $m \times r$ matrix and
+$F$ is an $r \times n$ matrix. Every finite dimensional matrix has a rank decomposition: Let $A$ be an $m\times n$ matrix whose column rank is $r$. Therefore,
+there are $r$ linearly independent columns in $A$; equivalently, the dimension of the column space of $A$ is $r$ (the explanation in this section comes mostly
+from \cite{Wiki2012rf}).
+
+Let $c_1,c_2,\ldots,c_r$ be any basis for
+the column space of $A$ and place them as column vectors to form the $m\times r$ matrix $C\ =\ [c_1:c_2:\ldots:c_r]$. Therefore, every column vector of $A$ is a
+linear combination of the columns of C. To be precise, if $ A = [a_1:a_2:\ldots:a_n]$ is an $m\times n$ matrix with $a_j$ as the $j-th$ column, then
+\begin{equation}
+    a_j = f_{1j}c_1 + f_{2j}c_2 + \cdots + f_{rj}c_r,
+    \label{eq:4}
+\end{equation}
+where $f_{ij}$'s are the scalar coefficients of $a_j$ in terms of the basis $c_1,c_2,\ldots,c_r$. This implies that $A\ =\ CF$, where $f_{ij}$ is the $(i,j)-th$
+element of $F$.
+\subsection{Rank Factorization from Row Echelon Forms}
+In practice, we can construct one specific rank factorization as follows: we can compute B, the reduced row echelon form of A. Then C is obtained by removing
+from A all non-pivot columns, and F by eliminating all zero rows of B.
+
+\textbf{Example}
+Consider the matrix
+\begin{equation}
+    A = \begin{bmatrix} 
+    1 & 3 & 1 & 4 \\ 
+    2 & 7 & 3 & 9 \\ 
+    1 & 5 & 3 & 1 \\ 
+    1 & 2 & 0 & 8 
+    \end{bmatrix}
+\sim 
+  \begin{bmatrix} 
+    1 & 0 & -2 & 0 \\ 
+    0 & 1 & 1 & 0 \\ 
+    0 & 0 & 0 & 1 \\ 
+    0 & 0 & 0 & 0 
+    \end{bmatrix}=B.
+\label{eq:5}
+\end{equation}
+
+$B$ is in reduced echelon form. Then $C$ is obtained by removing the third column of $A$, the only one which is not a pivot column, and $F$ by getting rid of
+the last row of zeroes, so
+\begin{equation}
+    C = \begin{bmatrix} 
+    1 & 3 & 4 \\ 
+    2 & 7 & 9 \\ 
+    1 & 5 & 1 \\ 
+    1 & 2 & 8 
+    \end{bmatrix},
+\qquad 
+    F = \begin{bmatrix} 
+    1 & 0 & -2 & 0 \\ 
+    0 & 1 & 1 & 0 \\ 
+    0 & 0 & 0 & 1 
+  \end{bmatrix}.
+  \label{eq:6}
+\end{equation}
+It is straightforward to check that
+\begin{equation}
+   A = \begin{bmatrix} 
+    1 & 3 & 1 & 4 \\ 
+    2 & 7 & 3 & 9 \\ 
+    1 & 5 & 3 & 1 \\ 
+    1 & 2 & 0 & 8 
+    \end{bmatrix} = 
+    \begin{bmatrix} 
+    1 & 3 & 4 \\ 
+    2 & 7 & 9 \\ 
+    1 & 5 & 1 \\
+    1 & 2 & 8 
+    \end{bmatrix}
+    \begin{bmatrix} 
+    1 & 0 & -2 & 0 \\ 
+    0 & 1 & 1 & 0 \\ 
+    0 & 0 & 0 & 1 
+    \end{bmatrix} = CF.
+  \label{eq:7}
+\end{equation}
+
+There are few applications highlighted in \cite{Piziak1999} for \textit{rank factorization} where one is to calculate the inverse of a matrix. However, the
+authors in \cite{Piziak1999} confess that matrix inversion can be done by $SVD\ decomposition$ with less complexity. 
 
 
 

digest-LinearAlgDecompositions.tex

 
 Rules of contributors:
 \begin{itemize}
+ \item use static word wrap (Word Wrap Document in Kile) - it is easier for revision control systems to track editions;
+ \item contributions with unclear sources or \textit{direct} wikipedia copypaste\footnote{There is nothing wrong with Wikipedia - you can add the mathematical
+formulas from there to save your time, but \textbf{please take a time to check the math!} Better use some reliable scientific sources like \textit{Linear
+Algebra Handbook}.} will be challenged and erased;
  \item use static word wrap (Word Wrap Document in Kile) - it is easier for
 revision control systems to track editions;
  \item contributions with unclear sources or \textit{direct} wikipedia
 copypaste\footnote{There is nothing wrong with Wikipedia - you can add the
-mathematical
-formulas from there to save your time, but \textbf{please take a time to check
-the math!} Better use some reliable scientific sources like \textit{Linear
-Algebra Handbook}.} will be challenged and erased;
- \item use static word wrap (Word Wrap Document in Kile) - it is easier for
-revision control systems to track editions;
+mathematical formulas from there to save your time, but \textbf{please take a
+time to check the math!} Better use some reliable scientific sources like
+\textit{Linear Algebra Handbook}.} will be challenged and erased;
  \item add citations in BiBTeX database in \verb+biblio/linalgdecompose+;
  \item use British/Australian variant of English.
 \end{itemize}
 \input{decompose-matrixproperties}
 %%%%%%%%%%%% Chapter:  Matrix properties, like norm, condition number
 
-\bibliographystyle{unsrt} 
-\bibliography{biblio/linalgdecompose,biblio/kmvlinalgdecompose}
+\bibliographystyle{unsrt}  \bibliography{biblio/linalgdecompose}
 \end{document}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.