Интерполяционное разложение

В численном анализе интерполяционная декомпозиция (ID) факторизует матрицу как произведение двух матриц, одна из которых содержит выбранные столбцы из исходной матрицы, а другая имеет подмножество столбцов, состоящее из единичной матрицы , и все ее значения равны не более 2 по абсолютной величине.

Определение

Позволять $A$ быть $m\times n$ матрица рангов $r$. Матрица $A$ можно записать как

$A=A_{(:,J)}X,\,$

где

• $J$ является подмножеством $r$ индексы из $\{1,\ldots ,n\};$
• The $m\times r$ матрица $A_{(:,J)}$ представляет $J$столбцы $A;$
• $X$ это $r\times n$ матрица, все значения которой по величине меньше 2. $X$ имеет $r\times r$ идентификационная подматрица.

Обратите внимание, что аналогичное разложение можно выполнить, используя строки $A$ вместо его столбцов.

Пример

Позволять $A$ быть $3\times 3$ матрица ранга 2:

$A={\begin{bmatrix}34&58&52\\59&89&80\\17&29&26\end{bmatrix}}.$

Если

$J={\begin{bmatrix}2&1\end{bmatrix}},$

затем

$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}}.$

Ссылки

• Ченг, Хунвэй, Жидрунас Гимбутас, Пер-Гуннар Мартинссон и Владимир Рохлин. « О сжатии матриц низкого ранга ». SIAM Journal on Scientific Computing 26, вып. 4 (2005): 1389–1404.
• Либерти Э., Вульф Ф., Мартинссон П.Г., Рохлин В. и Тайгерт М. (2007). Рандомизированные алгоритмы низкоранговой аппроксимации матриц . Труды Национальной академии наук, 104 (51), 20167–20172.