Jump to content

Interpolative decomposition

From Wikipedia, the free encyclopedia
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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 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

Let be the matrix of rank 2:

If

then

Notes


References