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

There

$J = \begin{bmatrix} 2 & 1 & 3 \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.