User:Jarle Pahr/SVD

From OpenWetWare

Jump to: navigation, search

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 \overrightarrow v that satisfies the equation

A\overrightarrow v  = \lambda \overrightarrow v

Where λ is a scalar. λ is called an eigenvalue.


Any mxn matrix A can be factored as:

A = U\sum {V^T} where:

  • U is an mXm orthogonal matrix where the columns are the eigenvectors of AAT
  • V is an nXn orthogonal matrix where the columns are the eigenvectors of ATA
  • \sum{} is an mXn diagonal matrix where the r first diagona elements are the square roots of the eigenvalues of ATA, 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 U are called the left singular vectors, and the columns of V theright singular vectors.

Contents

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 S, the change in metabolite concentrations x as function of the reaction rates v is given by the equation:

Sv = \frac{{dx}}{{dt}}

The singular value decomposition of S is

S = U\sum {V^T}

Which can be written as:

SV = U\sum

The above expression defines a series of independent equations on the form

Svk = σkuk

Where vk are the column vectors of V (the right singular vectors), σk are the singular valus and uk are the column vectors of U (the left singular vectors).


Applying the SVD to S, we get:

{U^T}\frac{{dx}}{{dt}} = \sum {V^T}v

The columns of U, called the left singular vectors and denoted Ui form linear combinations of the concentations variables. Similarly, columns of V, called the right singular vectors' and denoted Vi 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 σk there is a corresponding column uk in U and a row v_k^T whose relationship is described by the equation

\frac{{d(u_k^Tx)}}{{dt}} = {\sigma _k}(v_k^Tv),\,\,k = 1,...,r

where the linar combination of metabolite concentrations

u_k^Tx = {u_{k1}}{x_1} + {u_{k2}}{x_2} + ... + {u_{kr}}{x_m}

is being driven by the linear combination of metabolic fluxes

v_k^Tv = {v_{k1}}{v_1} + {v_{k2}}{v_2} + ... + {v_{kn}}{v_n}


Each column uk of U thus defines an eigen-reaction or systemic metabolic reaction which can be expressed as

\sum_{\text{for } v_{kj < 0}} u_{ki}x_{i}\underset{{\sum\limits_{{\text{for }}{{\text{v}}_{kj < 0}}} {{v_{kj}}{v_j}} }}{\overset{{\sum\limits_{{\text{for }}{{\text{v}}_{kj > 0}}} {{v_{kj}}{v_j}} }}{\rightleftharpoons}}  \sum_{\text{for } v_{kj > 0}} u_{ki}x_{i}

The elements of uk are called systemeic stoichiometric coefficients and the elements of vk are called systemeic participation numbers.



Attention: The right singular vectors vk should not be confused with the flux vector v.

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

http://pastebin.com/5ms5QEtn


A rational basis for the nullspace of a matrix with rational elements can be found using SymPy.

Examples

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]

A SVD of N is

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]

\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]

{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]

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:


\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]

Links

http://mathbio.colorado.edu/mediawiki/index.php/MBW:Singular_value_decomposition_of_stoichiometric_matrices

Simple SVD calculator: http://metamerist.com/excanvas/example23a.htm

http://comnuan.com/cmnn01004/

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.

Personal tools