Interpolative decomposition

<h2 id="definition">Definition</h2>
<p>Let 
  
    
      
        A
      
    
    {\displaystyle A}
  
 be an 
  
    
      
        m
        ×
        n
      
    
    {\displaystyle m\times n}
  
 matrix of <a href="/facts/Rank_(linear_algebra)/Yp9b5LK3">rank</a> 
  
    
      
        r
      
    
    {\displaystyle r}
  
.  The matrix 
  
    
      
        A
      
    
    {\displaystyle A}
  
 can be written as
</p>

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

<p>where
</p>
<ul><li>
  
    
      
        J
      
    
    {\displaystyle J}
  
 is a subset of 
  
    
      
        r
      
    
    {\displaystyle r}
  
 indices from 
  
    
      
        {
        1
        ,
        …
        ,
        n
        }
        ;
      
    
    {\displaystyle \{1,\ldots ,n\};}
  
</li>
<li>The 
  
    
      
        m
        ×
        r
      
    
    {\displaystyle m\times r}
  
 matrix 
  
    
      
        
          A
          
            (
            :
            ,
            J
            )
          
        
      
    
    {\displaystyle A_{(:,J)}}
  
 represents 
  
    
      
        J
      
    
    {\displaystyle J}
  
's columns of 
  
    
      
        A
        ;
      
    
    {\displaystyle A;}
  
</li>
<li>
  
    
      
        X
      
    
    {\displaystyle X}
  
 is an 
  
    
      
        r
        ×
        n
      
    
    {\displaystyle r\times n}
  
 matrix, all of whose values are less than 2 in magnitude. 
  
    
      
        X
      
    
    {\displaystyle X}
  
  has an 
  
    
      
        r
        ×
        r
      
    
    {\displaystyle r\times r}
  
 identity submatrix.</li></ul>
<p>Note that a similar decomposition can be done using the rows of 
  
    
      
        A
      
    
    {\displaystyle A}
  
 instead of its columns.
</p>
<h2 id="example">Example</h2>
<p>Let 
  
    
      
        A
      
    
    {\displaystyle A}
  
 be the 
  
    
      
        3
        ×
        3
      
    
    {\displaystyle 3\times 3}
  
 matrix of rank 2:
</p>

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

J
        =
        
          
            [
            
              
                
                  2
                
                
                  1
                
              
            
            ]
          
        
        ,
      
    
    {\displaystyle J={\begin{bmatrix}2&1\end{bmatrix}},}

A
        =
        
          
            [
            
              
                
                  58
                
                
                  34
                
              
              
                
                  89
                
                
                  59
                
              
              
                
                  29
                
                
                  17
                
              
            
            ]
          
        
        
          
            [
            
              
                
                  0
                
                
                  1
                
                
                  
                    
                      29
                      33
                    
                  
                
              
              
                
                  1
                
                
                  0
                
                
                  
                    
                      1
                      33
                    
                  
                
              
            
            ]
          
        
        ≈
        
          
            [
            
              
                
                  58
                
                
                  34
                
              
              
                
                  89
                
                
                  59
                
              
              
                
                  29
                
                
                  17
                
              
            
            ]
          
        
        
          
            [
            
              
                
                  0
                
                
                  1
                
                
                  0.8788
                
              
              
                
                  1
                
                
                  0
                
                
                  0.0303
                
              
            
            ]
          
        
        .
      
    
    {\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}}\approx {\begin{bmatrix}58&34\\89&59\\29&17\end{bmatrix}}{\begin{bmatrix}0&1&0.8788\\1&0&0.0303\end{bmatrix}}.}

<h2 id="notes">Notes</h2>

<ul><li>Cheng, Hongwei, Zydrunas Gimbutas, Per-Gunnar Martinsson, and Vladimir Rokhlin. "<a href="https://amath.colorado.edu/faculty/martinss/Pubs/2004_skeletonization.pdf">On the compression of low rank matrices.</a>" SIAM Journal on Scientific Computing 26, no. 4 (2005): 1389–1404.</li>
<li>Liberty, E., Woolfe, F., Martinsson, P. G., Rokhlin, V., & Tygert, M. (2007). <a href="http://www.pnas.org/content/104/51/20167.full.pdf+html">Randomized algorithms for the low-rank approximation of matrices</a>. Proceedings of the National Academy of Sciences, 104(51), 20167–20172.</li></ul>

Interpolative decomposition open-in-new

Interpolative decomposition