Misplaced Pages

Interpolative decomposition

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (November 2016) (Learn how and when to remove this message)

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


References

Categories: