Interpolative decomposition Source: en.wikipedia.org/wiki/Interpolative_decomposition

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (November 2016) (Learn how and when to remove this message)

In numerical analysis, interpolative decomposition (ID) factors a matrix as the product of two matrices, one of which contains selected columns from the original matrix, and the other of which has a subset of columns consisting of the identity matrix and all its values are no greater than 2 in absolute value.

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

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

where

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

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

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

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

If

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

then

${\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}}.}$

• 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.