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 $A$ be an $m \times n$ matrix of rank $r$ . The matrix $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 $J$ 's columns of $A;$
$X$ is an $r \times n$ matrix, all of whose values are less than 2 in magnitude. $X$ has an $r \times 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 \times 3$ matrix of rank 2:

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

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

then

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

Notes

References

Cheng, Hongwei, Zydrunas Gimbutas, Per-Gunnar Martinsson, and Vladimir Rokhlin. "[https://amath.colorado.edu/faculty/martinss/Pubs/2004_skeletonization.pdf 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). [http://www.pnas.org/content/104/51/20167.full.pdf+html Randomized algorithms for the low-rank approximation of matrices]. Proceedings of the National Academy of Sciences, 104(51), 20167–20172.

Category:Matrix decompositions

Category:Numerical linear algebra