Spectral analysis of data

Spectral Analysis of Data Yossi Azar


Amos Fiat


Anna R. Karlin


            
                    
    

    
               !  "   

ABSTRACT
                                                         

                               !   "   
            

         "              !                     #     $                
 

        ! 1.

INTRODUCTION %          

            &' () ((* #         

            + 
               

       
   

    
  (     

 

,        -%+ "./010'1      2%"  3  %   +  3%+
4  5 %   #  2 #  6..0/ " 

 4  5 %   2  7   %  

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. STOC’01 July 6-8, 2001, Hersonissos, Crete, Greece. Copyright 2001 ACM 1-58113-349-9/01/0007 ...85.00.

Frank McSherry

Jared Saia

     1  7              
             #  
               
$        
   $    &  *     
            $  % 
        

        &  *           !    9                     &  *   

          !     "                        ! 7                           ! 7                  !       

        

 $    

       !    $        ! 7      !           

    :     

                    #                     $    
 #       + (                       ; (


         7     
                 $  

           

 

   ·½ 

 

7  %          C       C     

  &'      Æ C        Æ       ( 
     

7 

    ) 

   +

    
   

           7     $                      C     THE STABILITY OF SINGULAR SUBSPACES #   !                  
                

          &(' (1* 5       

    %     > 

      ( 
                         Æ 

 7 

  # )  C

1






1   C + %  ))      



 




  



1








1




       >           %                 C    # )

  

    

¾

3.



C    
 C  
 

  



1




     !"#     >               

  




C

 




>

 




           

 7                                     
$                   
 7 

           

    


 '     C >      )
         * ( 

C   

 

C   



!

C    

     

   "  



!    

     



   

 

 



       



 7 

  5

 =        C

      (     "    !   

 



 

,

      

 C      C     >      C   >    > !  C     > !       > !        

 

 

 

 

 

#                                -     

                 !      
                     

  

 



 C      C     >    C             >        >           























# '  I    &(' (1*         !    
    !           !  
               

 

   
       7 

              E # $        #  $    
    
    


       

 



 J      + 
                , 

    



!

    

     (



      





 

      (

"        $    

4. STABILITY UNDER RANDOM PERTURBATION +        

   

    I # '                
                I      4     

 

  # '

 6

       





 




 > 

  C  >            

        -        C      +     
    .   
   ! C      *     
       "    ! 

                
  !   /

               &%*   &%*  (  
  
  %  











0       
    
       
      1 ! 

          (               ( 





 



 

  
  
  
          

 # 

  :             

        
              >  

 
       
         >  # 
    >       

     >  5.

DATA MINING 7 
   5

 6                    5.1 Information Retrieval 7              %  () "  
  !  C    
 &  *    
                              
 E     
 &  *&   

                    :            
    
 # 

        
                     5

 6      !  

      ;

( 4      




 C    >  ) 5     ! 
    = +                  #                    

 


 0        (             
    (   2 3 )
            
                  >         ( (     
    &%*  &%*  (

 
  
  % 0     
    1

                         (  

 



 

 



 

)
      7    

          #     

              

    



 5          

          
 C               &  * C 
 
  #     
              I +     !
 5

 6        C   >   

        &  *     

   5

 6                      

       "                     
      1             5.1.1 Discussion of Latent Semantic Indexing

#     # 0        E%"            

  #         

                          3

         
   &  * 4      

 

                     

       -                                                   # 0                         

           %                              

 

               ?A                    

    #            E%"        

    
                                       # 

      


    !   
      !            
                     

                '    '      
  %             %           
 %              % # 0    
   F   E%"                       5.1.2 Discussion of Kleinberg’s Link Analysis

7    %  ()       !                       !         C (        "     
    !   
 # 0 

               N 



     



                 5.2 Collaborative Filtering 7 
                
         

       A Model for Collaborative Filtering

7    

       

  E             
  :  &  *                  7        
     ;

&  *     &  * C @  (    ?@A            ,               @ A Collaborative Filtering Algorithm

7   

 

 (       @         ( (    
 $ % ( (        
           (

 :            
     
 -           C               


  &  *    
  &  * C &  *  (   #   
                 I          ( 
&  * #       M(   &  *  ( 5

 6      

Estimating The Omission Probabilities

#  $                       

!    %        !                               K               
                 

        
     
         %  J(  

;

 E     
    !   


  

@  1 

   (  5      


 

 C    >            

 5    2  &  *   
      



    

%            
C    

  ? A 
      # 0          "                 (                   !             (  !       
        ,     !    5.3 The General Data Mining Model "                                   

              

O             

                  7         

                  : !    $          

     F              
  $      

     G   !                            #          

              + 
    

                        !

     $  " ?  A        #H         #H , 

          #H ,         
      ! ) #       P             E
.                   >  #  
       (
  
   >         >    #         

 

 

 #               E .          (  

  5        +      ,

 

  
C 








  !      
               >      
  >             
  



   
C  


                   >  #      

 M(   >