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 [math]\displaystyle{ A }[/math] be an [math]\displaystyle{ m \times n }[/math] matrix of rank [math]\displaystyle{ r }[/math]. The matrix [math]\displaystyle{ A }[/math] can be written as

[math]\displaystyle{ A = A_{(:,J)} X , \, }[/math]

where

• [math]\displaystyle{ J }[/math] is a subset of [math]\displaystyle{ r }[/math] indices from [math]\displaystyle{ \{ 1 ,\ldots, n \}; }[/math]
• The [math]\displaystyle{ m \times r }[/math] matrix [math]\displaystyle{ A_{(:,J)} }[/math] represents [math]\displaystyle{ J }[/math]'s columns of [math]\displaystyle{ A; }[/math]
• [math]\displaystyle{ X }[/math] is an [math]\displaystyle{ r \times n }[/math] matrix, all of whose values are less than 2 in magnitude. [math]\displaystyle{ X }[/math] has an [math]\displaystyle{ r \times r }[/math] identity submatrix.

Note that a similar decomposition can be done using the rows of [math]\displaystyle{ A }[/math] instead of its columns.

Example

Let [math]\displaystyle{ A }[/math] be the [math]\displaystyle{ 3 \times 3 }[/math] matrix of rank 2:

[math]\displaystyle{ A = \begin{bmatrix} 34 & 58 & 52 \\ 59 & 89 & 80 \\ 17 & 29 & 26 \end{bmatrix}. }[/math]

If

[math]\displaystyle{ J = \begin{bmatrix} 2 & 1 \end{bmatrix}, }[/math]

then

[math]\displaystyle{ A = \begin{bmatrix} 58 & 34 \\ 89 & 59 \\ 29 & 17 \end{bmatrix} \begin{bmatrix} 0 & 1 & \frac{29}{33} \\ 1 & 0 & \frac{1}{33} \end{bmatrix} \approx \begin{bmatrix} 58 & 34 \\ 89 & 59 \\ 29 & 17 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0.8788 \\ 1 & 0 & 0.0303 \end{bmatrix}. }[/math]

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.