Interpolative decomposition

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.

Definition

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

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

where

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

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

Example

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

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

If

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

then

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

References

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