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 has a subset of columns that consists the identity matrix and all its values are not larger than 2 in absolute value.

Definition

Let $A$ be an $m\times n$ matrix with 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 the $J$ 's columns of $A$
$X$ is a $r\times n$ matrix that all its values are less than 2 in magnitude. $X$ has a $r\times r$ identity sub-matrix.

Note that similar decomposition can be done using the rows of $A$ .

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&0.8788\\1&0&0.0303\end{bmatrix}}

Notes

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.