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

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

A=A(:,J)X,

where

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

Example

Let A be the 3×3 matrix of rank 2:

A=[345852598980172926].

If

J=[21],

then

A=[583489592917][01293310133]≈[583489592917][010.8788100.0303].