• Images
• Videos
• Documents
• Books
• Articles

Definition

Let A {\displaystyle A} be an m × n {\displaystyle m\times n} matrix of rank r {\displaystyle r} . The matrix A {\displaystyle A} can be written as

A = A ( : , J ) X , {\displaystyle A=A_{(:,J)}X,\,}

where

• J {\displaystyle J} is a subset of r {\displaystyle r} indices from { 1 , … , n } ; {\displaystyle \{1,\ldots ,n\};}
• The m × r {\displaystyle m\times r} matrix A ( : , J ) {\displaystyle A_{(:,J)}} represents J {\displaystyle J} 's columns of A ; {\displaystyle A;}
• X {\displaystyle X} is an r × n {\displaystyle r\times n} matrix, all of whose values are less than 2 in magnitude. X {\displaystyle X} has an r × r {\displaystyle r\times r} identity submatrix.

Note that a similar decomposition can be done using the rows of A {\displaystyle A} instead of its columns.

Example

Let A {\displaystyle A} be the 3 × 3 {\displaystyle 3\times 3} matrix of rank 2:

A = [ 34 58 52 59 89 80 17 29 26 ] . {\displaystyle A={\begin{bmatrix}34&58&52\\59&89&80\\17&29&26\end{bmatrix}}.}

If

J = [ 2 1 ] , {\displaystyle J={\begin{bmatrix}2&1\end{bmatrix}},}

then

A = [ 58 34 89 59 29 17 ] [ 0 1 29 33 1 0 1 33 ] ≈ [ 58 34 89 59 29 17 ] [ 0 1 0.8788 1 0 0.0303 ] . {\displaystyle A={\begin{bmatrix}58&34\\89&59\\29&17\end{bmatrix}}{\begin{bmatrix}0&1&{\frac {29}{33}}\\1&0&{\frac {1}{33}}\end{bmatrix}}\approx {\begin{bmatrix}58&34\\89&59\\29&17\end{bmatrix}}{\begin{bmatrix}0&1&0.8788\\1&0&0.0303\end{bmatrix}}.}

Notes

• Cheng, Hongwei, Zydrunas Gimbutas, Per-Gunnar Martinsson, and Vladimir Rokhlin. "On the compression of low rank matrices." SIAM Journal on Scientific Computing 26, no. 4 (2005): 1389–1404.
• Liberty, E., Woolfe, F., Martinsson, P. G., Rokhlin, V., & Tygert, M. (2007). Randomized algorithms for the low-rank approximation of matrices. Proceedings of the National Academy of Sciences, 104(51), 20167–20172.