פירוק אינטרפולטיבי

באנליזה נומרית פירוק אינטרפולטיבי (Interpolative decomposition) מציג מטריצה כמכפלה של שתי מטריצות; האחת בנויה מחלק מהעמודות של המטריצה המקורית, והשנייה מכילה תת-מטריצת יחידה וכל שאר האיברים שלה קטנים מ-2 בגודלם.

הרעיון של הפירוק, ומכאן גם שמו, הוא להציג מטריצה עם יתירות בעמודות (היתירות מתבטאת בדרגה נמוכה יותר ממספר העמודות) כהרחבה (או אינטרפולציה) של עמודות נבחרות מתוך המטריצה.

באנליזה נומרית משתמשים בפירוק לא רק עבור המקרה שבו הדרגה נמוכה, אלא גם עבור המקרה שבו הדרגה הנומרית נמוכה, ואז הפירוק המתקבל מקרב את המטריצה המקורית בדיוק החישוב.

את הפירוק אפשר באופן דומה לבצע על שורות במקום עמודות.

הגדרה

תהי $A$ מטריצה בגודל $m\times n$ מדרגה $r$, אז ניתן להציג את $A$ כ:

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

כאשר:

• $J$ היא תת-קבוצה של אינדקסים בגודל $r$ מתוך $1,\ldots ,n$.
• המטריצה $A_{(:,J)}$ היא מטריצה בגודל $m\times r$ שמכילה את העמודות באינדקס $J$ של $A$.
• $X$ היא מטריצה בגודל $r\times n$ שכל ערכיה בעלי נורמה קטנה מ-2. ל $X$ יש תת-מטריצת יחידה בגודל $r\times r$ .

דוגמה

אם $A$ היא מטריצה בגודל $3\times 3$ מדרגה 2 : $A={\begin{bmatrix}34&58&52\\59&89&80\\17&29&26\\\end{bmatrix}}$

אז הפירוק האינטרפולטיבי שלה ע"פ עמודות הוא:

$A={\begin{bmatrix}58&34\\89&59\\29&17\\\end{bmatrix}}{\begin{bmatrix}0&1&0.8788\\1&0&0.0303\\\end{bmatrix}}$

ולפי שורות:

$A={\begin{bmatrix}0&1\\1&0\\0&0.5\\\end{bmatrix}}{\begin{bmatrix}59&89&80\\34&58&52\end{bmatrix}}$

אלגוריתם לחישוב הפירוק

עבור מטריצה $A$ בגודל $m\times n$, נחשב באופן הבא את הפירוק האינטרפולטיבי שלה מסדר $k$:

נחשב פירוק QR של A עם פרמוטצית עמודות: AP=QR
נסמן: $R=\left[{\begin{array}{c|c}R_{11}&R_{12}\\\hline 0&R_{22}\end{array}}\right]$ כאשר $R_{11}$ היא מטריצה $k\times k$, $R_{12}$  היא מטריצה בגודל$k\times (n-k)$, ו $R_{22}$ היא מטריצה $(m-k)\times (n-k)$
נסמן: $Q=\left[{\begin{array}{c|c}Q_{1}&Q_{2}\end{array}}\right]$ כאשר $Q_{1}$ היא מטריצה $m\times k$ ו $Q_{2}$ היא מטריצה $m\times (m-k)$
נחשב: $B=Q_{1}R_{11}$ ונשים לב שקיימים $K$ אינדקסים $J$ כך ש $B=A_{(:,J)}$
נחשב: $X=\left[{\begin{array}{c|c}I_{k}&R_{11}^{-1}R_{12}\end{array}}\right]P^{T}$ כאשר $I_{k}$ היא מטריצת היחידה בגודל $k\times k$
ונקבל: $A=BX$

לקריאה נוספת

• Cheng, Hongwei, Zydrunas Gimbutas, Per-Gunnar Martinsson, and Vladimir Rokhlin. "On the compression of low rank matrices." SIAM Journal on Scientific Computing 26, no. 4 (2005): 1389-1404.
• Liberty, E., Woolfe, F., Martinsson, P. G., Rokhlin, V., & Tygert, M. (2007). Randomized algorithms for the low-rank approximation of matrices. Proceedings of the National Academy of Sciences, 104(51), 20167-20172.