Interpolative decomposition

In numerical analysis interpolative decomposition (also known as ID for short) factors a matrix as the product of two matrices, one 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.

Definition

Let $A$ be an $m\times n$ with rank $r$. than $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}}$

Then

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