Interpolative decomposition - Alchetron, the free social encyclopedia

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 has a subset of columns that consists the identity matrix and all its values are not larger than 2 in absolute value.

Definition

Let A be an m × n matrix with rank r . The matrix A can be written as:

A = A ( : , J ) X ,

where:

J is a subset of r indices from 1 , … , n

The m × r matrix A ( : , J ) represents the J 's columns of A

X is a r × n matrix that all its values are less than 2 in magnitude. X has a r × r identity sub-matrix.

Note that similar decomposition can be done using the rows of A .

Example

Let A be the 3 × 3 matrix of rank 2: A = [ 34 58 52 59 89 80 17 29 26 ]

If J = [ 2 1 3 ] , then

A = [ 58 34 89 59 29 17 ] [ 0 1 0.8788 1 0 0.0303 ]

References

Interpolative decomposition Wikipedia

(Text) CC BY-SA

Contents

Definition

Example

References