Interpolative decomposition explained

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 x n matrix of rank r . The matrix A can be written asA = A _{(:,J)} X , whereJ is a subset of r indices from \{ 1 ,\ldots, n \};

• The

m x r matrix A _{(:,J)} represents J 's columns of A; X is an r x n matrix, all of whose values are less than 2 in magnitude. X has an r x 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 x 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 & (29)/(33) \\ 1 & 0 & (1)/(33) \end{bmatrix} ≈ \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.