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

edit

Let   be an   matrix of rank  . The matrix   can be written as

 

where

  •   is a subset of   indices from  
  • The   matrix   represents  's columns of  
  •   is an   matrix, all of whose values are less than 2 in magnitude.   has an   identity submatrix.

Note that a similar decomposition can be done using the rows of   instead of its columns.

Example

edit

Let   be the   matrix of rank 2:

 

If

 

then

 

Notes

edit


References

edit