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

Example

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