Interpolative decomposition
Appearance
This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (November 2016) |
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]- 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.