User:Jarle Pahr/SVD
Notes on Singular Value Decomposition (SVD):
See also http://en.wikipedia.org/wiki/Singular_value_decomposition
Eigenvectors and eigenvalues:
An eigenvector of a matrix is A is a non-zero vector [math]\displaystyle{ \overrightarrow v }[/math] that satisfies the equation
[math]\displaystyle{ A\overrightarrow v = \lambda \overrightarrow v }[/math]
Where [math]\displaystyle{ \lambda }[/math] is a scalar. [math]\displaystyle{ \lambda }[/math] is called an eigenvalue.
Any [math]\displaystyle{ mxn }[/math] matrix A can be factored as:
[math]\displaystyle{ A = U\sum {V^T} }[/math] where:
- [math]\displaystyle{ U }[/math] is an mXm orthogonal matrix where the columns are the eigenvectors of [math]\displaystyle{ AA^T }[/math]
- [math]\displaystyle{ V }[/math] is an nXn orthogonal matrix where the columns are the eigenvectors of [math]\displaystyle{ A^{T}A }[/math]
- [math]\displaystyle{ \sum{} }[/math] is an mXn diagonal matrix where the [math]\displaystyle{ r }[/math] first diagona elements are the square roots of the eigenvalues of [math]\displaystyle{ A^{T}A }[/math], also called the singular values of A. Singular values are always real and positive.
For any SVD, the following facts apply:
- The rank of a matrix A equals the number of singular values of A.
- The column space of A is spanned by the first r columns of U.
- The null space of A is spanned by the last n − r columns of V.
- The row space of A is spanned by the first r columns of V.
- The null space of AT is spanned by the last m − r columns of U.
The columns of [math]\displaystyle{ U }[/math] are called the left singular vectors, and the columns of [math]\displaystyle{ V }[/math] theright singular vectors.
SVD in NumPy
http://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.svd.html
To find the rank of a matrix A, assign u,s,vh = linalg.svd(A) and r = len(s)
Applications to metabolic networks
Given a metabolic network with stoichoimetric matrix [math]\displaystyle{ S }[/math], the change in metabolite concentrations [math]\displaystyle{ x }[/math] as function of the reaction rates [math]\displaystyle{ v }[/math] is given by the equation:
[math]\displaystyle{ Sv = \frac{{dx}}{{dt}} }[/math]
The singular value decomposition of S is
[math]\displaystyle{ S = U\sum {V^T} }[/math]
Which can be written as:
[math]\displaystyle{ SV = U\sum }[/math]
The above expression defines a series of independent equations on the form
[math]\displaystyle{ S{v_k} = {\sigma _k}{u_k} }[/math]
Where [math]\displaystyle{ v_k }[/math] are the column vectors of V (the right singular vectors), [math]\displaystyle{ {\sigma _k} }[/math] are the singular valus and [math]\displaystyle{ u_k }[/math] are the column vectors of U (the left singular vectors).
Applying the SVD to S, we get:
[math]\displaystyle{ {U^T}\frac{{dx}}{{dt}} = \sum {V^T}v }[/math]
The columns of U, called the left singular vectors and denoted [math]\displaystyle{ U_i }[/math] form linear combinations of the concentations variables. Similarly, columns of V, called the right singular vectors' and denoted [math]\displaystyle{ V_i }[/math] form linear combinations of the fluxes. Linear combinations of concentration variablesare called pools while linear combinations of fluxes are called pathways.
For each nonzero singular value [math]\displaystyle{ \sigma _k }[/math] there is a corresponding column [math]\displaystyle{ u_k }[/math] in U and a row [math]\displaystyle{ v_k^T }[/math] whose relationship is described by the equation
[math]\displaystyle{ \frac{{d(u_k^Tx)}}{{dt}} = {\sigma _k}(v_k^Tv),\,\,k = 1,...,r }[/math]
where the linar combination of metabolite concentrations
[math]\displaystyle{ u_k^Tx = {u_{k1}}{x_1} + {u_{k2}}{x_2} + ... + {u_{kr}}{x_m} }[/math]
is being driven by the linear combination of metabolic fluxes
[math]\displaystyle{ v_k^Tv = {v_{k1}}{v_1} + {v_{k2}}{v_2} + ... + {v_{kn}}{v_n} }[/math]
Each column [math]\displaystyle{ u_k }[/math] of U thus defines an eigen-reaction or systemic metabolic reaction which can be expressed as
[math]\displaystyle{ \sum_{\text{for } v_{kj \lt 0}} u_{ki}x_{i}\underset{{\sum\limits_{{\text{for }}{{\text{v}}_{kj \lt 0}}} {{v_{kj}}{v_j}} }}{\overset{{\sum\limits_{{\text{for }}{{\text{v}}_{kj \gt 0}}} {{v_{kj}}{v_j}} }}{\rightleftharpoons}} \sum_{\text{for } v_{kj \gt 0}} u_{ki}x_{i} }[/math]
The elements of [math]\displaystyle{ u_k }[/math] are called systemeic stoichiometric coefficients and the elements of [math]\displaystyle{ v_k }[/math] are called systemeic participation numbers.
Attention: The right singular vectors [math]\displaystyle{ v_k }[/math] should not be confused with the flux vector [math]\displaystyle{ v }[/math].
Links
http://www.uwlax.edu/faculty/will/svd/
math.stackexchange.com/questions/261801/how-can-you-explain-the-singular-value-decomposition-to-non-specialists
http://www.ams.org/samplings/feature-column/fcarc-svd
http://campar.in.tum.de/twiki/pub/Chair/TeachingWs05ComputerVision/3DCV_svd_000.pdf
http://langvillea.people.cofc.edu/DISSECTION-LAB/Emmie%27sLSI-SVDModule/p4module.html
Finding the null space of a matrix
Finding null space of matrix: http://www.math.odu.edu/~bogacki/cgi-bin/lat.cgi
https://github.com/amilsted/evoMPS/blob/master/evoMPS/nullspace.py
http://wiki.scipy.org/Cookbook/RankNullspace
A rational basis for the nullspace of a matrix with rational elements can be found using SymPy.
Examples
[math]\displaystyle{ N = \left[ {\begin{array}{*{20}{c}} 1&{ - 1}&0&{ - 1}&0&0&0 \\ 0&1&{ - 1}&0&0&0&0 \\ 0&1&0&1&{ - 1}&0&0 \\ 0&0&1&1&0&{ - 1}&0 \\ 0&0&1&0&0&0&{ - 1} \end{array}} \right] }[/math]
A SVD of N is
[math]\displaystyle{ U = \left[ {\begin{array}{*{20}{c}} {0.64}&{ - 0.10}&{0.11}&{ - 0.71}&{ - 0.27} \\ { - 0.22}&{0.57}&{ - 0.12}&0&{ - 0.78} \\ { - 0.64}&{0.10}&{ - 0.11}&{ - 0.71}&{0.27} \\ { - 0.37}&{ - 0.63}&{0.52}&0&{ - 0.43} \\ {0.04}&{ - 0.51}&{ - 0.83}&0&{ - 0.23} \end{array}} \right] }[/math]
[math]\displaystyle{ \sum = \left[ {\begin{array}{*{20}{c}} {2.43}&0&0&0&0&0&0 \\ 0&{2.09}&0&0&0&0&0 \\ 0&0&{1.11}&0&0&0&0 \\ 0&0&0&1&0&0&0 \\ 0&0&0&0&{0.69}&0&0 \end{array}} \right] }[/math]
[math]\displaystyle{ {V^T} = \left[ {\begin{array}{*{20}{c}} {0.26}&{ - 0.61}&{ - 0.79}&{ - 0.68}&{0.26}&{0.15}&{0.02} \\ { - 0.05}&{0.37}&{ - 0.82}&{ - 0.20}&{ - 0.05}&{0.30}&{0.24} \\ {0.09}&{ - 0.30}&{ - 0.17}&{0.03}&{0.10}&{ - 0.47}&{0.75} \\ { - 0.71}&0&0&0&{0.71}&0&0 \\ { - 0.39}&{ - 0.36}&{0.20}&{0.15}&{ - 0.39}&{0.63}&{0.34} \\ {0.48}&{0.31}&{0.31}&{0.16}&{0.48}&{0.48}&{0.31} \\ { - 0.20}&{0.41}&{0.41}&{ - 0.61}&{ - 0.20}&{ - 0.20}&{0.41} \end{array}} \right] }[/math]
If N is a stoichiometric matrix, we find for the first eigenreaction:
A larger example is given below, using the stoichiometric matrix of the example metabolic network from Navid & Almaas 2012:
[math]\displaystyle{ \left[ \begin{array}{{cccccccccccccccccccc}}
0& 0& 0& 0& 0& 0& 0& 0& 1& 1& 0& 0& 0& {-1}& 0& 0& 0& 0&0& 0\\
0& 0& 0& 0& 0& {-1}& 0& 1& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0&0& 0\\
0& 0& 1& {-1}& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0&0& 0\\
{-2}&4.5&0&0&0&11.5&0& {-10}&{-1}&0&0&0&0&0& 0& 0& 0& 0& 0& 0\\
0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& {-1}&0& 0\\
0& 0& {-}1& 0& 0& 1& 2& {-0.1}& 0& 0& 0& {-1}& 0& 0& 0& 0& 0& 0& 0& 0 \\
0& 1& {-1}& 0& 0& 0& {-1}& {-1}& 0& 0& 0& 0& {-1}& 0& 0& 0& 0& 0&0& 0\\
0& 0& 0& 1& {-1}& 0& {-1}& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0&0& 0\\
0& 0& 0& 0& 1& {-1}& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0&0& 0\\
2& -1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0&0& 0\\
0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0&{-1}& 0\\
0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0&0& {-1}\\
{-1}& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0&0& 0\\
0& 0& 0& 0& 0& 1& 0& -1& 0& -1& 0& 0& 0& 0& 0& 0& 0& 0&0& 0\\
0& 0& 0& 0& 0& 0& 0& 0& 0& 0& {-1}& 0& 0& 0& 0& {-1}& 0& 0&0& 0\\
2&{-4.5}&0& 0& 0&{-11.5} &0&10& 1& 0& 0& 0&0& 0& 0& 0& 0& 0& 0& 0\\
0& 0& 1& 0& 2& 0& 1& 0& 0& 0& 0& 0& 0& 0& {-1}& 0& 0& 0&0& 0\\
0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& {-1}& 0&0& 0\\
\end{array}\right] }[/math]
Links
Simple SVD calculator: http://metamerist.com/excanvas/example23a.htm
http://www.dotnumerics.com/MatrixCalculator/default.aspx
Bibliography
Palsson, 2006. Systems Biology: Properties of reconstructed networks. Cambridge.
Famili & Palsson. Journal of theoretical biology 224 (2003) 87-96.
