Interpolative decomposition

Let ${\displaystyle A}$ be an ${\displaystyle m\times n}$ matrix of rank ${\displaystyle r}$. The matrix ${\displaystyle A}$ can be written as

${\displaystyle A=A_{(:,J)}X,\,}$

where

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

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

Let ${\displaystyle A}$ be the ${\displaystyle 3\times 3}$ matrix of rank 2:

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

If

${\displaystyle J={\begin{bmatrix}2&1\end{bmatrix}},}$

then

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

• 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.