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,\dots ,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=\left[\begin{array}{ccc}34& 58& 52\\ 59& 89& 80\\ 17& 29& 26\end{array}\right].$

If

$J=\left[\begin{array}{cc}2& 1\end{array}\right],$

then

$A=\left[\begin{array}{cc}58& 34\\ 89& 59\\ 29& 17\end{array}\right]\left[\begin{array}{ccc}0& 1& \frac{29}{33}\\ 1& 0& \frac{1}{33}\end{array}\right]\approx \left[\begin{array}{cc}58& 34\\ 89& 59\\ 29& 17\end{array}\right]\left[\begin{array}{ccc}0& 1& 0.8788\\ 1& 0& 0.0303\end{array}\right].$

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.