Интерполяционная декомпозиция - Interpolative decomposition

Эта статья включает Список ссылок, связанное чтение или внешняя ссылка, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Ноябрь 2016) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Определение

Позволять ${ displaystyle A}$ быть ${ Displaystyle м раз п}$ матрица классифицировать ${ displaystyle r}$. Матрица ${ displaystyle A}$ можно записать как

${ Displaystyle А = А _ {(:, J)} X, ,}$

куда

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

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

Пример

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

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

Если

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

тогда

${ displaystyle 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}} приблизительно { 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.