Interpolative Decomposition
Chapter 9: Matrix Decompositions and Beyond — Interpolative Decomp (ID)
From the book
Chapter 9: Matrix Decompositions and Beyond. In the chapter mind map this icon labels Interpolative Decomp (ID): Submatrix Selection. The discussion below is excerpted and lightly edited from § Theorem: Interpolative Decomposition in Mathematics for AI and Machine Learning.
For a matrix $A \in \mathbb{R}^{M \times N}$ with $\mathrm{rank}(A) = r$, there exists a decomposition
where $\mathcal{J} \subset \{0, 1, \ldots, N-1\}$ is a set of $r$ column indices (the "skeleton" columns), $A(:, \mathcal{J}) \in \mathbb{R}^{M \times r}$ consists of $r$ selected columns of $A$, and $C \in \mathbb{R}^{r \times N}$ is an interpolation matrix with $||C|| \le \sqrt{r(N-r)+1}$.
What this drawing shows
What you see. Shows selected representative columns reconstructing the remaining columns through interpolation coefficients.
In the mind map. Chapter 9 — Interpolative Decomp (ID): Submatrix Selection. See From the book above for definitions, figures, and worked examples.
Where to read next
Read the full definitions, figures, and worked examples in Chapter 9: Matrix Decompositions and Beyond — see the mind-map node Interpolative Decomp (ID): Submatrix Selection.