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 {\displaystyle A} be an m × n {\displaystyle m\times n} matrix of rank r {\displaystyle r} . The matrix A {\displaystyle A} can be written as
A = A ( : , J ) X , {\displaystyle A=A_{(:,J)}X,\,}
where
J {\displaystyle J} is a subset of r {\displaystyle r} indices from { 1 , … , n } ; {\displaystyle \{1,\ldots ,n\};}
The m × r {\displaystyle m\times r} matrix A ( : , J ) {\displaystyle A_{(:,J)}} represents J {\displaystyle J} 's columns of A ; {\displaystyle A;}
X {\displaystyle X} is an r × n {\displaystyle r\times n} matrix, all of whose values are less than 2 in magnitude. X {\displaystyle X} has an r × r {\displaystyle r\times r} identity submatrix. Note that a similar decomposition can be done using the rows of A {\displaystyle A} instead of its columns.
Example Let A {\displaystyle A} be the 3 × 3 {\displaystyle 3\times 3} matrix of rank 2:
A = [ 34 58 52 59 89 80 17 29 26 ] . {\displaystyle A={\begin{bmatrix}34&58&52\\59&89&80\\17&29&26\end{bmatrix}}.}
If
J = [ 2 1 ] , {\displaystyle J={\begin{bmatrix}2&1\end{bmatrix}},}
then
A = [ 58 34 89 59 29 17 ] [ 0 1 29 33 1 0 1 33 ] ≈ [ 58 34 89 59 29 17 ] [ 0 1 0.8788 1 0 0.0303 ] . {\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}}.}
Notes
… excerpt ends here. Continue reading the full article.
