Interpolační rozklad - Interpolative decomposition

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Listopad 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v numerická analýza, interpolativní rozklad (ID) faktory a matice jako produkt dvou matic, z nichž jedna obsahuje vybrané sloupce z původní matice a druhá má podmnožinu sloupců skládající se z matice identity a všechny jeho hodnoty nejsou větší než 2 v absolutní hodnotě.

Definice

Nechat ${ displaystyle A}$ být ${ displaystyle m krát n}$ matice hodnost ${ displaystyle r}$. Matice ${ displaystyle A}$ lze psát jako

${ displaystyle A = A _ {(:, J)} X, ,}$

kde

• ${ displaystyle J}$ je podmnožinou ${ displaystyle r}$ indexy z ${ displaystyle {1, ldots, n };}$
• The ${ displaystyle m krát r}$ matice ${ displaystyle A _ {(:, J)}}$ představuje ${ displaystyle J}$sloupce z ${ displaystyle A;}$
• ${ displaystyle X}$ je ${ displaystyle r times n}$ matice, jejíž všechny hodnoty jsou menší než 2. ${ displaystyle X}$ má ${ displaystyle r times r}$ submatice identity.

Podobný rozklad lze provést pomocí řádků ${ displaystyle A}$ místo jeho sloupců.

Příklad

Nechat ${ displaystyle A}$ být ${ displaystyle 3 krát 3}$ matice pořadí 2:

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

Li

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

pak

${ 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}} přibližně { begin {bmatrix} 58 a 34 89 & 59 29 a 17 end {bmatrix}} { begin {bmatrix} 0 a 1 & 0,8788 1 & 0 a 0,0303 end {bmatrix} }.}$

Poznámky

Reference

• Cheng, Hongwei, Zydrunas Gimbutas, Per-Gunnar Martinsson a Vladimir Rokhlin. "Na kompresi matic s nízkým hodnocením. „SIAM Journal on Scientific Computing 26, no. 4 (2005): 1389–1404.
• Liberty, E., Woolfe, F., Martinsson, P. G., Rokhlin, V., & Tygert, M. (2007). Randomizované algoritmy pro nízkořadou aproximaci matic. Sborník Národní akademie věd, 104 (51), 20167–20172.