Abstract:
Non-negative matrix factorization, NMF, is combined with identification of a maximum margin classifier by minimizing a cost function that contains a generative component and the discriminative component. The relative weighting between the generative component and the discriminative component are adjusting during subsequent iterations such that initially, when confidence is low, the generative model is favored. But as the iterations proceed, confidence increases and the weight of the discriminative component is steadily increased until it is of equal weight as the generative model. Preferably, the cost function to be minimized is: 
     
       
         
           
             
               
                 min 
                 
                   F 
                   , 
                   
                     G 
                     ≥ 
                     0 
                   
                 
               
                
               
                 
                    
                   
                     X 
                     - 
                     FG 
                   
                    
                 
                 2 
               
             
             + 
             
               
                 γ 
                  
                 
                   ( 
                   
                     
                       
                          
                         w 
                          
                       
                       2 
                     
                     + 
                     
                       C 
                        
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             1 
                           
                           n 
                         
                          
                         
                           L 
                            
                           
                             ( 
                             
                               
                                 y 
                                 i 
                               
                               , 
                               
                                 
                                   w 
                                   · 
                                   
                                     g 
                                     i 
                                   
                                 
                                 + 
                                 b 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                   ) 
                 
               
               .

Description:
CONTINUING APPLICATION DATA 
       [0001]    This application claims the benefit of U.S. Provisional Application No. 61/179,854 filed May 20, 2009 under 35 U.S.C. §119(e) and is hereby incorporated by reference in its entirety. 
     
    
     BACKGROUND 
       [0002]    1. Field of Invention 
         [0003]    The present invention relates to the field of identifying a maximum margin classifier for classification of data, and is specifically directed to a method of optimizing the identifying of such a maximum margin classifier when analyzing a large set of data points. 
         [0004]    2. Description of Related Art 
         [0005]    Non-negative matrix factorization (NMF) is generally a group of algorithms in multivariate analysis (i.e. having more than one variable) and linear algebra where a matrix, X, is factorized into (usually) two matrices, W and H such that NMF (X)→WH. 
         [0006]    Non-negative matrix factorization (NMF) has been shown to be a useful decomposition for multivariate data, and NMF permits additive combinations of non-negative basis components. 
         [0007]    Factorization of matrices is generally non-unique, and a number of different methods of doing so have been developed (e.g. principle component analysis and singular value decomposition) by incorporating different constraints. Non-negative matrix factorization differs from these methods in that it enforces an additional constraint of having the factors W and H be non-negative, i.e., all elements in matrices W and H must be equal to or greater than zero. 
         [0008]    In approximating non-negative matrix factorization, usually the number of columns of W and the number of rows of H are selected so that their product, WH, will be an approximation of X, since a residual error U may remain. The full decomposition of X, therefore, may more generally be defined as the two non-negative matrices W and H plus a residual error, U, such that: X=WH+U. 
         [0009]    One of the reasons for factoring a matrix X is that when W and H are smaller than X, it can be easier to store and manipulate W and H, rather than X. Non-negative matrix factorization (NMF) has further been shown recently to be useful for many applications in pattern recognition, multimedia, text mining, and DNA gene expressions. 
         [0010]    NMF can be traced back to the 1970s, and is described in “Positive Matrix Factorization: A Non-Negative Factor Model With Optimal Utilization of Error Estimates of Data Values”,  Environmetrics , volume 5, pages 111-126, 1994, by P. Paatero and U. Tapper (hereby incorporated in its entirety by reference). NMF is further described in “Learning the Parts of Objects By Non-negative Matrix Factorization”,  Nature , volume 401, pages 788-791, 1999 by Lee and Seung, which is hereby incorporated in its entirety by reference, and in “Algorithms for Non-negative Matrix Factorization”,  NIPS , pages 556-562, 2000, also by Lee and Seung and also hereby incorporated in its entirety by reference. The work of Lee and Seung, in particular, brought much attention to NMF in machine learning and data mining fields. 
         [0011]    Support vector machines are a set of related supervised learning methods used for data classification and regression. A support vector machine constructs a hyperplane in a high-dimensional space, which can be used for data classification, data regression or other tasks. 
         [0012]    A hyperplane is a concept in geometry, and it is a generalization of the concept of a plane into higher dimensions. Analogous with a plane which defines a two-dimensional subspace in a three-dimensional space, a hyperplane defines an m-dimensional subspace within a q-dimensional space, where m&lt;q. A line, for example, is a one-dimensional hyperplane in a higher dimension space. 
         [0013]    High dimensional hyperplanes share many mathematical properties in common with regular lines and planes. The main idea in using a hyperplane in data analysis is to construct a divide (i.e. a hyperplane) that separates clusters of data points, or vectors, (i.e. separates data points into different classes). These separated data point clusters can then be used for data classification purposes. Intuitively, a good separation is achieved by the hyperplane that has the largest distance (i.e. functional margin) to the nearest training data points of the different classes, since in general, the larger the functional margin, the lower the generalization error of the classifier. 
         [0014]    Classifying data is a common task in machine learning. For example, if each data point in an existing sample of data points can be designated as belonging to one of two classes, a goal may be to decide to which class a newly received data point will belong. In the case of support vector machines, each data point may be viewed as a p-dimensional vector (i.e., a list of p numbers), and the goal is to determine whether such points can be separated with a (p−1)-dimensional hyperplane. This may be termed linear classification. In general, there are many hyperplanes that might classify the data (i.e. may separate the data into classifications, or data clusters), but one hyperplane may offer optimal separation. 
         [0015]    For example,  FIG. 1  shows a 2-dimensional space with eighteen data points (or vectors) separated into two clusters of nine data points, each. A first data cluster of nine data points is shown as darkened data points, and a second data cluster of nine data points is shown as lightened data points. Three candidate hyperplanes  11 ,  13 , and  15  (i.e. three lines in the present 2-dimensional example) separate the eighteen data points into two groups, or classes, of data points, but one of the three candidate hyperplanes offers the best data-point separation. 
         [0016]    In the present example, hyperplane  13  separates four darken data points on its left (side A) from five darken data points and nine lightened data points on its right (side B). In order to obtain meaningful information, however, it is helpful to divide the data points into data clusters since the data points in each data cluster is likely to have some similar attributes. In the present case, it is relatively self-apparent that hyperplane  13  does not provide useful information regarding similarities or differences between the data points since it does not accurately differentiate between the two data clusters. 
         [0017]    Hyperplane  11  does separate the first data cluster (consisting of nine darkened data points) on its upper side (side C) from the second data cluster (consisting of nine lightened data points) on its lower side (side D), but does not provide an optimal separation between the first and second data clusters. 
         [0018]    In order to provide meaningful information, it is preferable that the hyperplane that separates the two data clusters provide a maximum separation between the two data clusters. The objective is to choose the hyperplane in which the functional margin (i.e. the distance from the hyperplane to the nearest data point along a line normal to the hyperplane) on each side is maximized. If such a hyperplane exists, it is known as the maximum-margin hyperplane, and such a linear classifier is known as a maximum margin classifier. 
         [0019]    In the present example of  FIG. 1 , margin line  16  defines the border of the first data cluster of darken data points with reference to hyperplane  15 , and margin line  18  defines the border of the second data cluster of lightened data points with reference to hyperplane  15 . The data points (or vectors) along margin lines  16  or  18  are typically called support vectors. The bias from the origin to hyperplane  15  is shown as bias term b. Hyperplane  15 &#39;s functional margin w to margin lines  16  and  18  is likewise shown. In the present case, hyperplane  15  would be the maximum margin classifier since it has the largest functional margin among the three candidate hyperplanes  11 ,  13 ,  15 . 
         [0020]    It should be noted that the topics of non-negative matrix factorization and identification of a maximum margin classifier are separate and distinct. NMF aims to facilitate the storage and manipulation of data by factorizing a large matrix X into two smaller matrices W and H, although one still needs to combine the individual entries in W and H to recover an approximation to the original entries in X. By contrast, identifying a maximum margin classifier for X would entail analyzing the original, individual data entries in X and identifying a hyperplane that provides a maximum margin between data clusters. 
       SUMMARY OF INVENTION 
       [0021]    An objective of the present invention is to exploit the NMF decomposition in an expressive fashion by coupling the decomposition with a maximum margin classifier. 
         [0022]    It is a further object of the present invention to formulate the joint update equations and propose a new method that identifies the decomposition as well as the parameters of the maximum margin classifier. 
         [0023]    Preferably, the present objects are achieved by decomposing a given matrix vector X into two matrix vectors, F and G. This decomposing process includes minimizing a cost function that combine a non-negative matrix factorization, NMF and maximum margin classifier satisfying the following relationship: 
         [0000]    
       
         
           
             
               
                 min 
                 
                   F 
                   , 
                   
                     G 
                     ≥ 
                     0 
                   
                 
               
                
               
                 
                    
                   
                     X 
                     - 
                     FG 
                   
                    
                 
                 2 
               
             
             + 
             
               γ 
                
               
                 ( 
                 
                   
                     
                        
                       w 
                        
                     
                     2 
                   
                   + 
                   
                     C 
                      
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         n 
                       
                        
                       
                         L 
                          
                         
                           ( 
                           
                             
                               y 
                               i 
                             
                             , 
                             
                               
                                 w 
                                 · 
                                 
                                   g 
                                   i 
                                 
                               
                               + 
                               b 
                             
                           
                           ) 
                         
                       
                     
                   
                 
                 ) 
               
             
           
         
       
     
         [0000]    wherein: X∈         ; F∈         ; G∈         ; w∈         ; y i ∈{−1,1}∀i; g i ∈          is the i th  column of G; symbol (.) represents the dot product of the two vectors; L(y,t) is a loss function where t=(w·g i +b), and L(y,t)=max(0, 1−yt) p  and γ is a constant that distributes the relative importance of the two terms in the optimization. 
         [0024]    In this approach, minimizing the cost function is achieved by successive iterations, and γ is the relative weighting between the generative component and the discriminative component of the cost function, and γ is increased incrementally from 0 to 1 during each iteration. Preferably during each iteration, F is updated by the following relationship: 
         [0000]    
       
         
           
             
               F 
               
                 n 
                 + 
                 1 
               
             
             = 
             
               
                 F 
                 n 
               
               · 
               
                 
                   
                     XG 
                     T 
                   
                   
                     
                       ( 
                       FG 
                       ) 
                     
                      
                     
                       G 
                       T 
                     
                   
                 
                 . 
               
             
           
         
       
     
         [0025]    In this approach, updating G includes replacing w with a functional form that is dependent on a kernel and on a new vector that resides in          . Preferably, w is replaced with the following functional form 
         [0000]    
       
         
           
             
               
                 f 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
               = 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                   
                     β 
                     i 
                   
                    
                   
                     k 
                      
                     
                       ( 
                       
                         
                           x 
                           i 
                         
                         , 
                         x 
                       
                       ) 
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where function k(_,_) is the kernel. 
         [0026]    Further for updating G, bias term β 0  may be temporarily suppressed to yield the following modified cost function: 
         [0000]    
       
         
           
             
               G 
               
                 k 
                 + 
                 1 
               
             
             = 
             
               
                 G 
                 k 
               
               · 
               
                 
                   
                     
                       F 
                       T 
                     
                      
                     X 
                   
                   + 
                   
                     γ 
                      
                     
                       ( 
                       
                         
                           
                             
                               
                                 
                                   G 
                                   k 
                                 
                                  
                                 
                                   diag 
                                    
                                   
                                     ( 
                                     
                                       
                                         
                                           ( 
                                           
                                             1 
                                             + 
                                             λ 
                                           
                                           ) 
                                         
                                          
                                         
                                           β 
                                           2 
                                         
                                       
                                       + 
                                       
                                         L 
                                         2 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               - 
                             
                           
                         
                         
                           
                             
                               
                                 
                                   
                                     G 
                                     k 
                                   
                                    
                                   
                                     [ 
                                     
                                       β 
                                       · 
                                       
                                         ( 
                                         
                                           
                                             β 
                                              
                                             
                                               λ 
                                               2 
                                             
                                           
                                           + 
                                           L 
                                         
                                         ) 
                                       
                                     
                                     ] 
                                   
                                 
                                  
                                 
                                   1 
                                   T 
                                 
                               
                               - 
                               
                                 
                                   
                                     ( 
                                     
                                       
                                         G 
                                         k 
                                       
                                        
                                       β 
                                     
                                     ) 
                                   
                                    
                                   
                                     [ 
                                     
                                       L 
                                       + 
                                       
                                         
                                           λ 
                                           2 
                                         
                                          
                                         β 
                                       
                                     
                                     ] 
                                   
                                 
                                 T 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
                 
                   
                     
                       ( 
                       
                         
                           F 
                           T 
                         
                          
                         F 
                       
                       ) 
                     
                      
                     
                       g 
                       k 
                       i 
                     
                   
                   + 
                   
                     γ 
                      
                     
                       ( 
                       
                         
                           G 
                           k 
                         
                          
                         
                           diag 
                            
                           
                             ( 
                             
                               
                                 
                                   ( 
                                   
                                     1 
                                     + 
                                     λ 
                                   
                                   ) 
                                 
                                  
                                 
                                   β 
                                   2 
                                 
                               
                               + 
                               
                                 L 
                                 2 
                               
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
             
           
         
       
     
         [0000]    where L is the vector with l i  as the i th  element, β 2 =β·β and L 2 =L·L. In this case, updating β includes 
         [0000]    
       
         
           
             
               
                 
                   β 
                   = 
                   
                     
                       
                         ( 
                         
                           
                             λ 
                              
                             
                                 
                             
                              
                             K 
                           
                           + 
                           
                             
                               KI 
                               0 
                             
                              
                             K 
                           
                         
                         ) 
                       
                       
                         - 
                         1 
                       
                     
                      
                     
                       KI 
                       0 
                     
                      
                     Y 
                   
                 
               
             
             
               
                 
                   = 
                   
                     
                       
                         ( 
                         
                           
                             λ 
                              
                             
                                 
                             
                              
                             
                               I 
                               n 
                             
                           
                           + 
                           
                             
                               I 
                               0 
                             
                              
                             K 
                           
                         
                         ) 
                       
                       
                         - 
                         1 
                       
                     
                      
                     
                       I 
                       0 
                     
                      
                     Y 
                   
                 
               
             
             
               
                 
                   = 
                   
                     ( 
                     
                       
                         
                           
                             
                               
                                 ( 
                                 
                                   
                                     λ 
                                      
                                     
                                         
                                     
                                      
                                     
                                       I 
                                       
                                         n 
                                         sv 
                                       
                                     
                                   
                                   + 
                                   
                                     K 
                                     sv 
                                   
                                 
                                 ) 
                               
                               
                                 - 
                                 1 
                               
                             
                              
                             
                               Y 
                               sv 
                             
                           
                         
                       
                       
                         
                           0 
                         
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0000]    where I n  is the identity matrix of size n, n sv  is the number of support vectors, and K sv , Y sv  contain only the indices pertaining to the support vectors. 
         [0027]    To incorporte bias term β 0 , the following system of linear equations is solved: 
         [0000]    
       
         
           
             
               
                 ( 
                 
                   
                     
                       M 
                     
                     
                       c 
                     
                   
                   
                     
                       c 
                     
                     
                       0 
                     
                   
                 
                 ) 
               
                
               
                 ( 
                 
                   
                     
                       β 
                     
                   
                   
                     
                       
                         β 
                         0 
                       
                     
                   
                 
                 ) 
               
             
             = 
             
               ( 
               
                 
                   
                     
                       Y 
                       sv 
                     
                   
                 
                 
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
     
         [0000]    where M=(λI n     sv   +K sv ) and c is a constant that is of the order of a kernel statistic. 
         [0028]    Following the above-described approach, F, G, β, β 0  may be determined by applying the following algorithm: 
         [0000]    
       
         
               
             
           
               
                   
               
             
             
               
                  Require: X ≧ 0; threshold, MAXITER 
               
               
                  while (err &gt; threshold) OR MAXITER reached do 
               
               
                   
               
               
                  
         update                 F     ,         where                   F     n   +   1         =       F   n     ·       XG   T         (   FG   )          G   T             ;         
 
               
               
                   
               
               
                  update G, where 
               
               
                   
               
               
                 
                   
                     
                       
                         
                           
                             G 
                             
                               k 
                               + 
                               1 
                             
                           
                           = 
                           
                             
                               G 
                               k 
                             
                             · 
                             
                               
                                 
                                   
                                     F 
                                     T 
                                   
                                    
                                   X 
                                 
                                 + 
                                 
                                   γ 
                                    
                                   
                                     ( 
                                     
                                       
                                         
                                           
                                             
                                               
                                                 G 
                                                 k 
                                               
                                                
                                               
                                                 diag 
                                                  
                                                 
                                                   ( 
                                                   
                                                     
                                                       
                                                         ( 
                                                         
                                                           1 
                                                           + 
                                                           λ 
                                                         
                                                         ) 
                                                       
                                                        
                                                       
                                                         β 
                                                         2 
                                                       
                                                     
                                                     + 
                                                     
                                                       L 
                                                       2 
                                                     
                                                   
                                                   ) 
                                                 
                                               
                                             
                                             - 
                                           
                                         
                                       
                                       
                                         
                                           
                                             
                                               
                                                 
                                                   G 
                                                   k 
                                                 
                                                  
                                                 
                                                   [ 
                                                   
                                                     β 
                                                     · 
                                                     
                                                       ( 
                                                       
                                                         
                                                           β 
                                                            
                                                           
                                                             λ 
                                                             2 
                                                           
                                                         
                                                         + 
                                                         L 
                                                       
                                                       ) 
                                                     
                                                   
                                                   ] 
                                                 
                                               
                                                
                                               
                                                 1 
                                                 T 
                                               
                                             
                                             - 
                                             
                                               
                                                 
                                                   ( 
                                                   
                                                     
                                                       G 
                                                       k 
                                                     
                                                      
                                                     β 
                                                   
                                                   ) 
                                                 
                                                  
                                                 
                                                   [ 
                                                   
                                                     L 
                                                     + 
                                                     
                                                       
                                                         λ 
                                                         2 
                                                       
                                                        
                                                       β 
                                                     
                                                   
                                                   ] 
                                                 
                                               
                                               T 
                                             
                                           
                                         
                                       
                                     
                                     ) 
                                   
                                 
                               
                               
                                 
                                   
                                     ( 
                                     
                                       
                                         F 
                                         T 
                                       
                                        
                                       F 
                                     
                                     ) 
                                   
                                    
                                   
                                     g 
                                     k 
                                     i 
                                   
                                 
                                 + 
                                 
                                   γ 
                                    
                                   
                                     ( 
                                     
                                       
                                         G 
                                         k 
                                       
                                        
                                       
                                         diag 
                                          
                                         
                                           ( 
                                           
                                             
                                               
                                                 ( 
                                                 
                                                   1 
                                                   + 
                                                   λ 
                                                 
                                                 ) 
                                               
                                                
                                               
                                                 β 
                                                 2 
                                               
                                             
                                             + 
                                             
                                               L 
                                               2 
                                             
                                           
                                           ) 
                                         
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                         
                         ; 
                       
                     
                   
                 
               
               
                   
               
               
                  K ← G′G; 
               
               
                  new_sv ← {1, 2, . . . , n}; where new_sv will hold the set of indices of 
               
               
                 the support vectors, and since the support vectors are not yet  
               
               
                 determined, new_sv initially contains all the data point indices; 
               
               
                  old_sv ←{ } 
               
               
                  while (is different (old sv, new sv)) do 
               
               
                   old sv ← new sv; 
               
               
                   
               
               
                   
           [           B   T           B   0           ]     ←         M     -   1            [           Y       old   -        sv     T         0         ]       T       ,         wh      ere                     (         M       c           c       0         )          (         β             β   0           )       =     (           Y   SV             0         )       ,       
 
               
               
                   
               
               
                 preferably using line search; 
               
               
                   set other components of β to zero; 
               
               
                   new_sv ← indices i such that y i (Kβ) i  &lt; 1; support vectors are identified 
               
               
                 here, and new_sv is updated with the indices of the currently  
               
               
                 identified support vectors 
               
               
                   end while 
               
               
                   err ← ∥X − FG∥ Frobenius ; 
               
               
                  end while 
               
               
                  return F, G, β, β 0 . 
               
               
                   
               
             
          
         
       
     
         [0029]    In an alternate embodiment, non-negative matrix factorization, NMF, decomposition to a given matrix X to produce factorizing matrices F and G, may include the following steps: (a) updating F, where 
         [0000]    
       
         
           
             
               
                 F 
                 
                   n 
                   + 
                   1 
                 
               
               = 
               
                 
                   F 
                   n 
                 
                 · 
                 
                   
                     XG 
                     T 
                   
                   
                     
                       ( 
                       FG 
                       ) 
                     
                      
                     
                       G 
                       T 
                     
                   
                 
               
             
             ; 
           
         
       
     
         [0000]    (b) updating G, where 
         [0000]    
       
         
           
             
               
                 G 
                 
                   k 
                   + 
                   1 
                 
               
               = 
               
                 
                   G 
                   k 
                 
                 · 
                 
                   
                     
                       
                         F 
                         T 
                       
                        
                       X 
                     
                     + 
                     
                       γ 
                        
                       
                         ( 
                         
                           
                             
                               
                                 
                                   
                                     G 
                                     k 
                                   
                                    
                                   
                                     diag 
                                      
                                     
                                       ( 
                                       
                                         
                                           
                                             ( 
                                             
                                               1 
                                               + 
                                               λ 
                                             
                                             ) 
                                           
                                            
                                           
                                             β 
                                             2 
                                           
                                         
                                         + 
                                         
                                           L 
                                           2 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 - 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     
                                       G 
                                       k 
                                     
                                      
                                     
                                       [ 
                                       
                                         β 
                                         · 
                                         
                                           ( 
                                           
                                             
                                               β 
                                                
                                               
                                                 λ 
                                                 2 
                                               
                                             
                                             + 
                                             L 
                                           
                                           ) 
                                         
                                       
                                       ] 
                                     
                                   
                                    
                                   
                                     1 
                                     T 
                                   
                                 
                                 - 
                                 
                                   
                                     
                                       ( 
                                       
                                         
                                           G 
                                           k 
                                         
                                          
                                         β 
                                       
                                       ) 
                                     
                                      
                                     
                                       [ 
                                       
                                         L 
                                         + 
                                         
                                           
                                             λ 
                                             2 
                                           
                                            
                                           β 
                                         
                                       
                                       ] 
                                     
                                   
                                   T 
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   
                     
                       
                         ( 
                         
                           
                             F 
                             T 
                           
                            
                           F 
                         
                         ) 
                       
                        
                       
                         g 
                         k 
                         i 
                       
                     
                     + 
                     
                       γ 
                        
                       
                         ( 
                         
                           
                             G 
                             k 
                           
                            
                           
                             diag 
                              
                             
                               ( 
                               
                                 
                                   
                                     ( 
                                     
                                       1 
                                       + 
                                       λ 
                                     
                                     ) 
                                   
                                    
                                   
                                     β 
                                     2 
                                   
                                 
                                 + 
                                 
                                   L 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             ; 
           
         
       
     
         [0030]    (c) updating a matrix K such that K←G′G; (d) updating first memory location old_sv, using the following relation: new_sv←{1, 2, . . . , n}, where new_sv initially contain the indices of all datapoints since the support vectors have not yet been identified; e) updating second memory location old_sv, using the following relation: old_sv←new_sv; (f) updating a vector β, where [βT β 0 ]←M −1 [Y old      —     sv   T  0] T ; (g) updating first memory location new_sv, using the following relation: new_sv←indices i, where y i (Kβ) i &lt;1, which identifieds the support vectors and their indices are stored in new_sv; and (h) repeating steps (e) and (g) until old_sv=new_sv; wherein the above steps incorporate identification of a maximum margin classifier to the NMF decomposition process. 
         [0031]    Further within step (f) of this embodiment, the relation: [β T  β 0 ]←M −1 [Y old     —     sv   T  0] T  is preferably applied using a line search, and all other components of β are set to 0. 
         [0032]    Preferably the present alternate embodiment further includes the following steps: (i) determining an error value, err, between X and FG; and (j) repeating steps (a) through (i) until a predefined condition is met. Preferably within step (i), the error value err is determined using a Frobenius norm method such that: err←∥X−FG∥ Frobenius . In this case, the predefined condition is that err is lower than a predefined error threshold. Alternatively, the predefined condition is that either err is lower than a predefined error threshold or that steps (a) through (i) have been repeated a predefined number of repetitions. 
         [0033]    Alternatively, steps (a) through (h) may be repeated until a predefined number of repetitions is achieved. 
         [0034]    Finally, this alternate embodiment may also include providing F, G, β, and β 0  as outputs. 
         [0035]    Other objects and attainments together with a fuller understanding of the invention will become apparent and appreciated by referring to the following description and claims taken in conjunction with the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0036]    In the drawings wherein like reference symbols refer to like parts. 
           [0037]      FIG. 1  shows an example a maximum margin classifier in a 2-dimensional space. 
           [0038]      FIG. 2  is a flowchart of the present process for NMF incorporating a function for identifiying a maximum margin classifier. 
           [0039]      FIG. 3  shows a synthesized matrix F test  for test purposes. 
           [0040]      FIG. 4  shows a synthesized matrix G test  for test purposes, with datapoints  1  to  100  in one class and datapoints  101  to  200  in a second class denoted by magnitude. 
           [0041]      FIG. 5  shows a recovered matrix F recovered  next to F test , for comparison purposes. 
           [0042]      FIG. 6  shows a recovered matrix G recovered  next to G test , for comparison purposes. 
           [0043]      FIG. 7  show recovered vector β recovered . 
       
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0044]    Various extensions and variations of non-negative matrix factorization (NMF) have been proposed, but NMF, in a general form, can be described by the following factorization: 
         [0000]      X d×N =W d×r H r×N   (1) 
         [0000]    where d is the dimension of the data, N is the number of data points (usually more than d) and r&lt;d. Generally, this factorization has been compared with data decomposition techniques. In this sense W is called the set of basis functions and the set H is the data specific weights. It has been claimed by some researchers that such a decomposition has some favorable properties over other similar decompositions, such as PCA etc. 
         [0045]    Most of the work in this field, to date, has dealt with NMF decomposition as a unary operation. Penalties such as sparseness constraint, have been proposed, but the motivation still remains largely experimental. A non-smooth NMF that distributes the sparseness constraint to both the basis as well as feature matrices has also been proposed. More recently, a graph laplacian based penalty to incorporate a geometric constraint into the NMF cost function has also been proposed. For example, “Nonsmooth Nonnegative Matrix Factorization (NSNMF)”,  IEEE Trans. Pattern Analysis and Machine Intelligence , volume 28, pages 403-415, 2006, by Pascual-Montano et al. (hereby incorporated by reference), proposes that non-smooth NMF may distribute the sparseness constraint to both the basis as well as feature matrices. Additionally, “Non-Negative Matrix Factorization on Manifold”,  ICDM &#39; 08:  Proceedings of the  2008  Eighth IEEE International Conference on Data Mining , pages 63-72, by Cai et al (hereby incorporated by reference) proposes a graph Laplacian based penalty to incorporate a geometric constraint into the NMF cost. 
         [0046]    Unlike this prior work, the present invention seeks to combine a process for identifying a maximum margin classifier with a process for non-negative matrix factorization (NMF) decomposition. This is motivated by the observance that NMF tries to find the additive components that generate the data, and Applicants suggest that a maximum margin classifier that respects this decomposition may be made a part of the NMF decomposition scheme itself. 
         [0047]    Before moving forward, the multiplicative updates whose sub-optimal convergence have been presented by Lee and Seung are briefly described. A more detail discussion of these multiplicative updates may be found in “Algorithms for Non-Negative Matrix Factorization”,  NIPS , pages 556-562, 2000, by Daniel D. Lee and H. Sebastian Seung, which is herein incorporated in its entirety, by reference. 
         [0048]    Lee Seung multiplicative updates may be defined as: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       H 
                       
                         n 
                         + 
                         1 
                       
                     
                     = 
                     
                       
                         H 
                         n 
                       
                       · 
                       
                         
                           
                             W 
                             T 
                           
                            
                           X 
                         
                         
                           
                             W 
                             T 
                           
                            
                           
                             ( 
                             WH 
                             ) 
                           
                         
                       
                     
                   
                   , 
                   
                     
                       W 
                       
                         n 
                         + 
                         1 
                       
                     
                     = 
                     
                       
                         W 
                         n 
                       
                       · 
                       
                         
                           XH 
                           T 
                         
                         
                           
                             ( 
                             WH 
                             ) 
                           
                            
                           
                             H 
                             T 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where the dot, “·”, represents element wise multiplication, and the division is also element wise. 
         [0049]    The present invention proposes to combine the cost function of NMF decomposition with the primal formulation for the maximum margin classifier. The focus of this work is to identify a common update scheme that appreciates both the decomposition task as well as the classification task. Traditionally, these two aspects of data handling have been dealt separately. 
         [0050]    Generally, generative models (which randomly generate observable data given some hidden parameters) are used to formulate a data generation process. Conversely, discriminative models (which model the dependence of an unobserved variable “c” on an observed variable “d” to statistically predict “c” from “d”) are preferred for data separation or clustering. A joint development of both schemes into a coherent optimization framework is presently proposed. 
         [0051]    First, a derivation of the main update equations for the present formulation is presented. Writing the weighted combination of NMF and maximum margin classifier, the combined cost function that should preferably be minimized is 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       min 
                       
                         F 
                         , 
                         
                           G 
                           ≥ 
                           0 
                         
                       
                     
                      
                     
                       
                          
                         
                           X 
                           - 
                           FG 
                         
                          
                       
                       2 
                     
                   
                   + 
                   
                     γ 
                      
                     
                       ( 
                       
                         
                           
                              
                             w 
                              
                           
                           2 
                         
                         + 
                         
                           C 
                            
                           
                             
                               ∑ 
                               
                                 i 
                                 = 
                                 1 
                               
                               n 
                             
                              
                             
                               L 
                                
                               
                                 ( 
                                 
                                   
                                     y 
                                     i 
                                   
                                   , 
                                   
                                     
                                       w 
                                       · 
                                       
                                         g 
                                         i 
                                       
                                     
                                     + 
                                     b 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    such that:
       X∈         , F∈         , G∈         , w∈             y i ∈{−1,1}∀i
 
where vector g i ∈          is the i th  column of G, and symbol (.) represents the dot product of the two vectors, w and g i . The loss function, L(y,t), is L(y,t)=max(0, 1−yt) p , where t=(w·g i +b).
       
 
         [0054]    Furthermore, γ is a constant that distributes the relative importance of the two terms in the optimization. This can be identified as the relative weighting between the generative component and the discriminative component of the cost function. Preferably γ is increased incrementally from 0 to 1. Initially, when confidence is low, values of γ are kept low, thereby favoring the generative model. But as the iterations proceed, confidence increases and values of γ are steadily increased such that more and more weight is put onto the discriminative component of the optimization cost. When γ reaches a value of 1, both components are weighed equally. A preferred relationship between the number of iterations and the increase in γ is 1+ε, where ε is a user-defined quantity and 0&lt;ε&lt;0.1. 
         [0055]    The cost function is not jointly convex for all the unknowns. However, for any one unknown, with all the other unknowns held constant, the cost function is a convex quadratic function. It is advantageous to point out that the optimization for F is similar to simple NMF, and Applicants have found that the multiplicative update suggested by Lee and Seung are suitable. Hence, updates for the generative component, F, in each iteration may be defined as: 
         [0000]    
       
         
           
             
               
                 
                   
                     F 
                     
                       n 
                       + 
                       1 
                     
                   
                   = 
                   
                     
                       F 
                       n 
                     
                     · 
                     
                       
                         XG 
                         T 
                       
                       
                         
                           ( 
                           FG 
                           ) 
                         
                          
                         
                           G 
                           T 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Finding iteration updates for the discriminative component, G, however, is more involved. It is necessary to joinly find update equations for G as well as for the weight vector w∈         . 
         [0056]    To obtain a classifier solution similar to that of a support vector machine, it is presently preferred that a primal form be applied by replacing w with a functional form that is dependent on a kernel (i.e. a weighting function), as well as on a new vector that resides in          . Building on the teachings found in “Training a Support Vector Machine In the Primal”,  Neural Comput.,  19(5):1155-1178, 2007, by O. Chapelle, which is hereby incorporated in its entirety by reference, w is replaced with a functional form 
         [0000]    
       
         
           
             
               
                 
                   
                     f 
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       n 
                     
                      
                     
                       
                         β 
                         i 
                       
                        
                       
                         k 
                          
                         
                           ( 
                           
                             
                               x 
                               i 
                             
                             , 
                             x 
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where function k(_,_) is the kernel. Introducing this formulation into the present cost function, with a temporary suppression of the bias term β 0 , yields the modified cost function: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       min 
                       
                         F 
                         , 
                         
                           G 
                           ≥ 
                           0 
                         
                       
                     
                      
                     
                       
                          
                         
                           X 
                           - 
                           FG 
                         
                          
                       
                       2 
                     
                   
                   + 
                   
                     γ 
                      
                     
                       ( 
                       
                         
                           
                             
                               
                                 λ 
                                  
                                 
                                   
                                     ∑ 
                                     
                                       i 
                                       , 
                                       
                                         j 
                                         = 
                                         1 
                                       
                                     
                                     n 
                                   
                                    
                                   
                                     
                                       β 
                                       i 
                                     
                                      
                                     
                                       β 
                                       j 
                                     
                                      
                                     
                                       k 
                                        
                                       
                                         ( 
                                         
                                           
                                             g 
                                             i 
                                           
                                           , 
                                           
                                             g 
                                             j 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                               
                               + 
                             
                           
                         
                         
                           
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 n 
                               
                                
                               
                                 L 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       i 
                                     
                                     , 
                                     
                                       
                                         ∑ 
                                         
                                           j 
                                           = 
                                           1 
                                         
                                         n 
                                       
                                        
                                       
                                         
                                           k 
                                            
                                           
                                             ( 
                                             
                                               
                                                 g 
                                                 i 
                                               
                                               , 
                                               
                                                 g 
                                                 j 
                                               
                                             
                                             ) 
                                           
                                         
                                          
                                         
                                           β 
                                           j 
                                         
                                       
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where λ=1/C is the relative weighting between the loss function and the margin. Defining a kernel matrix K, such a that K ij =k(x i ,x j ), and k i  is the i th  column in K, one gets: 
         [0000]    
       
         
           
             
               
                 
                   
                     F 
                      
                     
                       ( 
                       
                         F 
                         , 
                         G 
                         , 
                         β 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         min 
                         
                           F 
                           , 
                           
                             G 
                             ≥ 
                             0 
                           
                         
                       
                        
                       
                         
                            
                           
                             X 
                             - 
                             FG 
                           
                            
                         
                         2 
                       
                     
                     + 
                     
                       γ 
                        
                       
                         ( 
                         
                           
                             
                               λβ 
                               T 
                             
                              
                             
                               
                                 ∂ 
                                 K 
                               
                               
                                 ∂ 
                                 gi 
                               
                             
                              
                             β 
                           
                           + 
                           
                             
                               ∑ 
                               j 
                               n 
                             
                              
                             
                               L 
                                
                               
                                 ( 
                                 
                                   yi 
                                   , 
                                   
                                     
                                       k 
                                       i 
                                       T 
                                     
                                      
                                     β 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Writing the first order gradients, one gets: 
         [0000]    
       
         
           
             
               
                 
                   
                     ∇ 
                     
                       g 
                       i 
                     
                   
                    
                   
                     = 
                     
                       
                         
                           - 
                           2 
                         
                          
                         
                           F 
                           T 
                         
                          
                         
                           x 
                           i 
                         
                       
                       + 
                       
                         2 
                          
                         
                           ( 
                           
                             
                               F 
                               T 
                             
                              
                             F 
                           
                           ) 
                         
                          
                         
                           g 
                           i 
                         
                       
                       + 
                       
                         
                           
                             γ 
                             ( 
                             
                               
                                 
                                   λβ 
                                   T 
                                 
                                  
                                 
                                   
                                     ∂ 
                                     K 
                                   
                                   
                                     ∂ 
                                     
                                       g 
                                       i 
                                     
                                   
                                 
                                  
                                 β 
                               
                               + 
                               
                                 
                                   ∑ 
                                   
                                     j 
                                     = 
                                     1 
                                   
                                   n 
                                 
                                  
                                 
                                   
                                     ∂ 
                                     L 
                                   
                                   
                                     ∂ 
                                     t 
                                   
                                 
                               
                             
                              
                           
                           
                             t 
                             = 
                             
                               
                                 k 
                                 j 
                                 T 
                               
                                
                               β 
                             
                           
                         
                          
                         
                           
                             
                               ∂ 
                               
                                 k 
                                 j 
                                 T 
                               
                             
                              
                             β 
                           
                           
                             ∂ 
                             
                               g 
                               i 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       ∇ 
                       β 
                     
                      
                     
                       = 
                       
                         
                           γ 
                           ( 
                           
                             
                               2 
                                
                               λ 
                                
                               
                                   
                               
                                
                               K 
                                
                               
                                   
                               
                                
                               β 
                             
                             + 
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 n 
                               
                                
                               
                                 
                                   k 
                                   i 
                                 
                                  
                                 
                                   
                                     ∂ 
                                     L 
                                   
                                   
                                     ∂ 
                                     t 
                                   
                                 
                               
                             
                           
                            
                         
                         
                           t 
                           = 
                           
                             
                               k 
                               i 
                               T 
                             
                              
                             β 
                           
                         
                       
                     
                   
                   ) 
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0057]    Returning to the definition of the loss function and using more concrete first order conditions, one may choose the L 2  penalization for the loss, namely, 
         [0000]        L ( y,f ( x   i ))=max(0,1 −yf ( x   i ) 2   (10) 
         [0000]    A point g i  is called a support vector when y i f(g i )&lt;1, i.e. a non-zero loss for this point is encountered. After a re-ordering of the training points such that the first n sv  points are the support vectors, the gradient with respect to β can be written as 
         [0000]      ∇ β =2γ(λ Kβ+KI   0 ( Kβ−Y ))  (11) 
       and the Hessian as 
       [0058]        H   β =2γ(λ K+KI   0   K ).  (12) 
         [0000]    The Newton step for β can now be written as 
         [0000]      β←β−η H   β   −1 ∇ β   (13) 
         [0000]    where 
         [0000]    
       
         
           
             
               I 
               0 
             
             = 
             
               ( 
               
                 
                   
                     
                       I 
                       sv 
                     
                   
                   
                     0 
                   
                 
                 
                   
                     0 
                   
                   
                     0 
                   
                 
               
               ) 
             
           
         
       
     
         [0000]    and η is the Newton step size. 
         [0059]    At this junction, it should be stressed that the functional representation mentioned in equation (5) usually has a bias term β 0  that is also learned with the other terms. The introduction of such a term can be handled with minimum modification to the above equations, without altering the form of the update equations for F, G or β. 
         [0060]    Next, one needs to identify a multiplicative update for G such that the non-negativity criteria is fulfilled. It should be noted that since the kernel takes g i &#39;s as its input, the optimization for G depends on the form of the kernel. Therefore, the subsequent analysis is presented for the inner product kernel, specifically k(g i ,g j )=g i   T g j . Assuming that all g k &#39;s other than g i  are held constant, one wants to minimize F(g i ). Writing the second order Taylor expansion around a point g i′ , one gets 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       F 
                        
                       
                         ( 
                         
                           g 
                           i 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         F 
                          
                         
                           ( 
                           
                             g 
                             
                               i 
                               ′ 
                             
                           
                           ) 
                         
                       
                       + 
                       
                         
                           
                             ( 
                             
                               
                                 g 
                                 i 
                               
                               - 
                               
                                 g 
                                 
                                   i 
                                   ′ 
                                 
                               
                             
                             ) 
                           
                           T 
                         
                          
                         
                           
                             ∇ 
                             
                               g 
                               
                                 i 
                                 ′ 
                               
                             
                           
                            
                           
                             + 
                             
                               
                                 ( 
                                 
                                   
                                     g 
                                     i 
                                   
                                   - 
                                   
                                     g 
                                     
                                       i 
                                       ′ 
                                     
                                   
                                 
                                 ) 
                               
                               T 
                             
                           
                         
                          
                         
                           
                             H 
                             
                               g 
                               
                                 i 
                                 ′ 
                               
                             
                           
                            
                           
                             ( 
                             
                               
                                 g 
                                 i 
                               
                               - 
                               
                                 g 
                                 
                                   i 
                                   ′ 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   where 
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           ∇ 
                           
                             g 
                             i 
                           
                         
                          
                         
                           = 
                             
                            
                           
                             
                               
                                 - 
                                 2 
                               
                                
                               
                                 F 
                                 T 
                               
                                
                               
                                 x 
                                 i 
                               
                             
                             + 
                             
                               2 
                                
                               
                                 ( 
                                 
                                   
                                     F 
                                     T 
                                   
                                    
                                   F 
                                 
                                 ) 
                               
                                
                               
                                 g 
                                 i 
                               
                             
                             + 
                             
                               γλ 
                                
                               
                                 ( 
                                 
                                   
                                     
                                       ∑ 
                                       
                                         j 
                                         = 
                                         1 
                                       
                                       n 
                                     
                                      
                                     
                                       
                                         β 
                                         j 
                                         2 
                                       
                                        
                                       
                                         g 
                                         j 
                                       
                                     
                                   
                                   + 
                                   
                                     
                                       β 
                                       i 
                                     
                                      
                                     
                                       
                                         ∑ 
                                         
                                           j 
                                           = 
                                           1 
                                         
                                         n 
                                       
                                        
                                       
                                         
                                           β 
                                           j 
                                         
                                          
                                         
                                           g 
                                           j 
                                         
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                             + 
                           
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           2 
                            
                           
                             γ 
                              
                             
                               ( 
                               
                                 
                                   
                                     ∑ 
                                     
                                       j 
                                       = 
                                       1 
                                     
                                     n 
                                   
                                    
                                   
                                     
                                       l 
                                       j 
                                     
                                      
                                     
                                       β 
                                       j 
                                     
                                      
                                     
                                       g 
                                       j 
                                     
                                   
                                 
                                 + 
                                 
                                   
                                     l 
                                     i 
                                   
                                    
                                   
                                     
                                       ∑ 
                                       
                                         j 
                                         = 
                                         1 
                                       
                                       n 
                                     
                                      
                                     
                                       
                                         β 
                                         j 
                                       
                                        
                                       
                                         g 
                                         j 
                                       
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             
                               - 
                               2 
                             
                              
                             
                               F 
                               T 
                             
                              
                             
                               x 
                               i 
                             
                           
                           + 
                           
                             2 
                              
                             
                               ( 
                               
                                 
                                   F 
                                   T 
                                 
                                  
                                 F 
                               
                               ) 
                             
                              
                             
                               g 
                               i 
                             
                           
                           + 
                           
                             2 
                              
                             
                               γ 
                                
                               
                                 ( 
                                 
                                   
                                     
                                       
                                         
                                           
                                             ∑ 
                                             
                                               j 
                                               = 
                                               1 
                                             
                                             n 
                                           
                                            
                                           
                                             
                                               ( 
                                               
                                                 
                                                   l 
                                                   j 
                                                 
                                                 + 
                                                 
                                                   
                                                     λ 
                                                     2 
                                                   
                                                    
                                                   
                                                     β 
                                                     j 
                                                   
                                                 
                                               
                                               ) 
                                             
                                              
                                             
                                               β 
                                               j 
                                             
                                              
                                             
                                               g 
                                               j 
                                             
                                           
                                         
                                         + 
                                       
                                     
                                   
                                   
                                     
                                       
                                         
                                           ( 
                                           
                                             
                                               l 
                                               i 
                                             
                                             + 
                                             
                                               
                                                 λ 
                                                 2 
                                               
                                                
                                               
                                                 β 
                                                 i 
                                               
                                             
                                           
                                           ) 
                                         
                                          
                                         
                                           
                                             ∑ 
                                             
                                               j 
                                               = 
                                               1 
                                             
                                             n 
                                           
                                            
                                           
                                             
                                               β 
                                               j 
                                             
                                              
                                             
                                               g 
                                               j 
                                             
                                           
                                         
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
             
               
                 
                   
                     H 
                     
                       g 
                       i 
                     
                   
                   = 
                   
                     
                       2 
                        
                       
                         ( 
                         
                           
                             F 
                             T 
                           
                            
                           F 
                         
                         ) 
                       
                     
                     + 
                     
                       
                         γ 
                          
                         
                           ( 
                           
                             
                               2 
                                
                               
                                 λβ 
                                 i 
                                 2 
                               
                             
                             + 
                             
                               4 
                                
                               
                                 l 
                                 i 
                               
                                
                               
                                 β 
                                 i 
                               
                             
                           
                           ) 
                         
                       
                        
                       
                         I 
                         n 
                       
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where l i =y i (y i k i   T β−1) and I n  is the identity matrix of size n. 
         [0061]    At this point, the present development moves towards identifying an auxiliary function such that the minimization of the auxiliary function leads to a guaranteed minimization of the original cost function. This property is guaranteed by the construction of the auxiliary function G(ν,ν′), which should fulfill two properties, first, that F(ν′)≦G(ν,ν′) and second, that F(ν)=G(ν,ν) for all non-negative ν, where F(ν) is the function we want to minimize. Having identified such properties of auxiliary functions, the basic idea for handling quadratic costs similar to F (g i ) in Eq. (14), is to identify a matrix H′, such that the difference between the second order terms H′−H≧0 (semi-positive definite). 
         [0062]    Consequently, an upper bound for the Hessian (Eq. (16)) needs to be found, noting that the last term 4l i β i  is unbounded, both in sign and magnitude. Using the triangle inequality one can bound 4l i β i ≦(l i +β i ) 2 ≦2(l i   2 +β i   2 ). Using this, the auxiliary function can be written as: 
         [0000]    
       
         
           
             
               
                 
                   
                     G 
                      
                     
                       ( 
                       
                         
                           g 
                           i 
                         
                         , 
                         
                           g 
                           i 
                           ′ 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       F 
                        
                       
                         ( 
                         
                           g 
                           i 
                           ′ 
                         
                         ) 
                       
                     
                     + 
                     
                       
                         
                           ( 
                           
                             
                               g 
                               i 
                             
                             - 
                             
                               g 
                               i 
                               ′ 
                             
                           
                           ) 
                         
                         T 
                       
                        
                       
                         
                           D 
                           
                             g 
                             
                               i 
                               ′ 
                             
                           
                         
                          
                         
                           ( 
                           
                             
                               g 
                               i 
                             
                             - 
                             
                               g 
                               i 
                               ′ 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       D 
                       
                         g 
                         i 
                       
                       ′ 
                     
                     = 
                     
                       diag 
                        
                       
                         ( 
                         
                           
                             
                               H 
                               ′ 
                             
                              
                             
                               g 
                               i 
                               ′ 
                             
                           
                           
                             g 
                             i 
                             ′ 
                           
                         
                         ) 
                       
                     
                   
                    
                   
                     
 
                   
                    
                   where 
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
             
               
                 
                   
                     H 
                     ′ 
                   
                   = 
                   
                     
                       2 
                        
                       
                         ( 
                         
                           
                             F 
                             T 
                           
                            
                           F 
                         
                         ) 
                       
                     
                     + 
                     
                       2 
                        
                       
                         γ 
                          
                         
                           ( 
                           
                             
                               
                                 ( 
                                 
                                   1 
                                   + 
                                   λ 
                                 
                                 ) 
                               
                                
                               
                                 β 
                                 i 
                                 2 
                               
                             
                             + 
                             
                               l 
                               i 
                               2 
                             
                           
                           ) 
                         
                       
                        
                       
                         I 
                         n 
                       
                     
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
         [0000]    which leads to the following lemma: 
         [0063]    Lemma 1 The choice of the function G(g i ,g i′ ) in Eq. (17) is a valid auxiliary function for F(g i ) in Eq. (14). 
         [0064]    Proof. The first condition G(g i ′,g i ′)=F(g i ′) is obvious by simple substitution. The second condition can be obtained by proving that D g     i′   −H g     i′   ≧0. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       D 
                       
                         g 
                         
                           i 
                           ′ 
                         
                       
                     
                     - 
                     
                       H 
                       
                         g 
                         
                           i 
                           ′ 
                         
                       
                     
                   
                   = 
                   
                     
                       D 
                       
                         g 
                         
                           i 
                           ′ 
                         
                       
                     
                     - 
                     
                       H 
                       ′ 
                     
                     + 
                     
                       H 
                       ′ 
                     
                     - 
                     
                       H 
                       
                         g 
                         
                           i 
                           ′ 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     
                       D 
                       
                         g 
                         
                           i 
                           ′ 
                         
                       
                     
                     - 
                     
                       H 
                       ′ 
                     
                     + 
                     
                       
                         γ 
                          
                         
                           ( 
                           
                             
                               2 
                                
                               
                                 β 
                                 i 
                                 2 
                               
                             
                             + 
                             
                               2 
                                
                               
                                 l 
                                 i 
                                 2 
                               
                             
                             - 
                             
                               4 
                                
                               
                                 l 
                                 i 
                               
                                
                               
                                 β 
                                 i 
                               
                             
                           
                           ) 
                         
                       
                        
                       
                         I 
                         n 
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                   
                     
                       
                         
                           
                             D 
                             
                               g 
                               
                                 i 
                                 ′ 
                               
                             
                           
                           - 
                           
                             H 
                             ′ 
                           
                         
                         
                            
                           A 
                         
                       
                       + 
                       
                         
                           2 
                            
                           
                             
                               γ 
                                
                               
                                 ( 
                                 
                                   
                                     β 
                                     i 
                                   
                                   - 
                                   
                                     l 
                                     i 
                                   
                                 
                                 ) 
                               
                             
                             2 
                           
                            
                           
                             I 
                             n 
                           
                         
                         
                            
                           B 
                         
                       
                     
                      
                     0 
                   
                 
               
             
           
         
       
     
         [0065]    The last condition above is satisfied since the second matrix B is a non-negative diagonal matrix which is added to A, and matrix A≧0, as Lee and Seung show in “Algorithms for Non-Negative Matrix Factorization”,  NIPS , pages 556-562, 2000. 
         [0066]    Finally the update for g i  can be found by evaluating 
         [0000]    
       
         
           
             
               
                 
                   ∂ 
                   
                     G 
                      
                     
                       ( 
                       
                         
                           g 
                           i 
                         
                         , 
                         
                           g 
                           i 
                           ′ 
                         
                       
                       ) 
                     
                   
                 
                 
                   ∂ 
                   
                     g 
                     i 
                   
                 
               
               = 
               0 
             
             , 
           
         
       
     
         [0000]    which gives: 
         [0000]    
       
         
           
             
               
                 
                   
                     g 
                     i 
                     
                       k 
                       + 
                       1 
                     
                   
                   = 
                   
                     
                       g 
                       i 
                       k 
                     
                     · 
                     
                       
                         
                           
                             
                               
                                 
                                   F 
                                   T 
                                 
                                  
                                 
                                   x 
                                   i 
                                 
                               
                               + 
                               
                                 
                                   γ 
                                    
                                   
                                     ( 
                                     
                                       
                                         
                                           ( 
                                           
                                             1 
                                             + 
                                             λ 
                                           
                                           ) 
                                         
                                          
                                         
                                           β 
                                           i 
                                           2 
                                         
                                       
                                       + 
                                       
                                         l 
                                         i 
                                         2 
                                       
                                     
                                     ) 
                                   
                                 
                                  
                                 
                                   g 
                                   i 
                                   k 
                                 
                               
                               - 
                             
                           
                         
                         
                           
                             
                               γ 
                                
                               
                                 ( 
                                 
                                   
                                     
                                       ∑ 
                                       
                                         j 
                                         = 
                                         1 
                                       
                                       n 
                                     
                                      
                                     
                                       
                                         ( 
                                         
                                           
                                             l 
                                             j 
                                           
                                           + 
                                           
                                             
                                               λ 
                                               2 
                                             
                                              
                                             
                                               β 
                                               j 
                                             
                                           
                                         
                                         ) 
                                       
                                        
                                       
                                         β 
                                         j 
                                       
                                        
                                       
                                         g 
                                         j 
                                         k 
                                       
                                     
                                   
                                   + 
                                   
                                     
                                       ( 
                                       
                                         
                                           l 
                                           i 
                                         
                                         + 
                                         
                                           
                                             λ 
                                             2 
                                           
                                            
                                           
                                             β 
                                             i 
                                           
                                         
                                       
                                       ) 
                                     
                                      
                                     
                                       
                                         ∑ 
                                         
                                           j 
                                           = 
                                           1 
                                         
                                         n 
                                       
                                        
                                       
                                         
                                           β 
                                           j 
                                         
                                          
                                         
                                           g 
                                           j 
                                           k 
                                         
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                       
                         
                           
                             ( 
                             
                               
                                 F 
                                 T 
                               
                                
                               F 
                             
                             ) 
                           
                            
                           
                             g 
                             i 
                             k 
                           
                         
                         + 
                         
                           
                             γ 
                              
                             
                               ( 
                               
                                 
                                   
                                     ( 
                                     
                                       1 
                                       + 
                                       λ 
                                     
                                     ) 
                                   
                                    
                                   
                                     β 
                                     i 
                                     2 
                                   
                                 
                                 + 
                                 
                                   l 
                                   i 
                                   2 
                                 
                               
                               ) 
                             
                           
                            
                           
                             g 
                             i 
                             k 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Putting all the column updates in a matrix form, one gets: 
         [0000]    
       
         
           
             
               
                 
                   
                     G 
                     
                       k 
                       + 
                       1 
                     
                   
                   = 
                   
                     
                       G 
                       k 
                     
                     · 
                     
                       
                         
                           
                             F 
                             T 
                           
                            
                           X 
                         
                         + 
                         
                           γ 
                            
                           
                             ( 
                             
                               
                                 
                                   
                                     
                                       
                                         G 
                                         k 
                                       
                                        
                                       
                                         diag 
                                          
                                         
                                           ( 
                                           
                                             
                                               
                                                 ( 
                                                 
                                                   1 
                                                   + 
                                                   λ 
                                                 
                                                 ) 
                                               
                                                
                                               
                                                 β 
                                                 2 
                                               
                                             
                                             + 
                                             
                                               L 
                                               2 
                                             
                                           
                                           ) 
                                         
                                       
                                     
                                     - 
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       
                                         
                                           G 
                                           k 
                                         
                                          
                                         
                                           [ 
                                           
                                             β 
                                             · 
                                             
                                               ( 
                                               
                                                 
                                                   β 
                                                    
                                                   
                                                     λ 
                                                     2 
                                                   
                                                 
                                                 + 
                                                 L 
                                               
                                               ) 
                                             
                                           
                                           ] 
                                         
                                       
                                        
                                       
                                         1 
                                         T 
                                       
                                     
                                     - 
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       
                                         ( 
                                         
                                           
                                             G 
                                             k 
                                           
                                            
                                           β 
                                         
                                         ) 
                                       
                                        
                                       
                                         [ 
                                         
                                           L 
                                           + 
                                           
                                             
                                               λ 
                                               2 
                                             
                                              
                                             β 
                                           
                                         
                                         ] 
                                       
                                     
                                     T 
                                   
                                 
                               
                             
                             ) 
                           
                         
                       
                       
                         
                           
                             ( 
                             
                               
                                 F 
                                 T 
                               
                                
                               F 
                             
                             ) 
                           
                            
                           
                             g 
                             k 
                             i 
                           
                         
                         + 
                         
                           γ 
                            
                           
                             ( 
                             
                               
                                 G 
                                 k 
                               
                                
                               
                                 diag 
                                  
                                 
                                   ( 
                                   
                                     
                                       
                                         ( 
                                         
                                           1 
                                           + 
                                           λ 
                                         
                                         ) 
                                       
                                        
                                       
                                         β 
                                         2 
                                       
                                     
                                     + 
                                     
                                       L 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   21 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where L is the vector with l i  as the i th  element, β 2 =β·β and L 2 =L·L, where as is explained above, dot “·” represents element wise multiplication. 
         [0067]    The following are implementation details. For the update of vector β, it is noted that by combining equations (11) and (12), one can write the update vector as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         β 
                         = 
                         
                           
                             
                               ( 
                               
                                 
                                   λ 
                                    
                                   
                                       
                                   
                                    
                                   K 
                                 
                                 + 
                                 
                                   
                                     KI 
                                     0 
                                   
                                    
                                   K 
                                 
                               
                               ) 
                             
                             
                               - 
                               1 
                             
                           
                            
                           
                             KI 
                             0 
                           
                            
                           Y 
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           
                             
                               ( 
                               
                                 
                                   λ 
                                    
                                   
                                       
                                   
                                    
                                   
                                     I 
                                     n 
                                   
                                 
                                 + 
                                 
                                   
                                     I 
                                     0 
                                   
                                    
                                   K 
                                 
                               
                               ) 
                             
                             
                               - 
                               1 
                             
                           
                            
                           
                             I 
                             0 
                           
                            
                           Y 
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           ( 
                           
                             
                               
                                 
                                   
                                     
                                       ( 
                                       
                                         
                                           λ 
                                            
                                           
                                               
                                           
                                            
                                           
                                             I 
                                             
                                               n 
                                               sv 
                                             
                                           
                                         
                                         + 
                                         
                                           K 
                                           sv 
                                         
                                       
                                       ) 
                                     
                                     
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                     Y 
                                     sv 
                                   
                                 
                               
                             
                             
                               
                                 0 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where I n  is the identity matrix of size n, n sv  is the number of support vectors, and K sv , Y sv  contain only the indices pertaining to the support vectors. To incorporate the bias term β 0 , the following system of linear equations is solved: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ( 
                       
                         
                           
                             M 
                           
                           
                             c 
                           
                         
                         
                           
                             c 
                           
                           
                             0 
                           
                         
                       
                       ) 
                     
                      
                     
                       ( 
                       
                         
                           
                             β 
                           
                         
                         
                           
                             
                               β 
                               0 
                             
                           
                         
                       
                       ) 
                     
                   
                   = 
                   
                     ( 
                     
                       
                         
                           
                             Y 
                             sv 
                           
                         
                       
                       
                         
                           0 
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where M=(λI n     sv   +K sv ) and c is a constant that is of the order of a kernel statistic, such as the mean (diag(k(x 1 , x 2 ))). The only limiting assumption in this formulation is that the kernel matrix is invertible. For the inner product kernel this assumption is not a problem, but for other kernels, it is advisable to add a small ridge to the kernel matrix. 
         [0068]    As mentioned earlier, for the present joint optimization scheme, one starts with small values of the weighting term and progressively increases its value as the iterations proceed. As with any other iterative scheme, the iterations terminate when either the maximum iterations are reached, or when the error reaches below a certain threshold. For testing, the simple decomposition of the test data may be performed, with constant F obtained from the training phase. The update equation (Eqn. 2) is used for G test . Once G test  is obtained, the kernel matrix K test =G T G test  is generated. This kernel is now inserted into the loss function (Eqn. 10), to obtain the classification results for the test data. 
         [0069]    An algorithm of this process may be expressed as follows: 
         [0000]    
       
         
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                   
               
             
             
               
                 Require: X ≧ 0; threshold, MAXITER 
               
               
                   while (err &gt; threshold) OR MAXITER reached do 
               
             
          
           
               
                    update F; 
                 (Eqn. (4)) 
               
               
                    update G; 
                 (Eqn. (21)) 
               
               
                    K ← G′G 
               
             
          
           
               
                    new_sv ← {1,2,...n}; 
                 Where new_sv will hold the indices of all the 
               
             
          
           
               
                   
                 identified support vectors, but since the support 
               
               
                   
                 vectors are not yet determined, new_sv initially 
               
               
                   
                 contains the indices of all the data points, and the 
               
               
                   
                 indices will be refined in the following while-loop; 
               
             
          
           
               
                   
                 Each cycle of the while-loop will attempt to 
               
             
          
           
               
                   
                 identify new support vectors, and multiple cycles 
               
               
                   
                 may be needed to identify all the support vectors. 
               
               
                   
                 The while-loop will continue cycling until the same 
               
               
                   
                 support vectors are consistently identified, i.e. 
               
               
                   
                 preferably until the indices of the identified 
               
               
                   
                 support vectors remain unchanged in two 
               
               
                   
                 consecutive cycles. 
               
             
          
           
               
                   
                 new_sv is updated with the indices of the newly 
               
             
          
           
               
                   
                 identified support vectors in each current cycle; 
               
               
                    old_sv ← { }; 
                 old_sv may be initially empty, but is updated with 
               
               
                   
                 the support vector indices identified in each 
               
               
                   
                 previous cycle of the following while-loop. 
               
             
          
           
               
                    while (is different (old_sv, new_sv)) do; 
                 Check if the indices of the 
               
               
                   
                 identified support vectors 
               
               
                   
                 remained unchanged during 
               
               
                   
                 the previous two cycles. 
               
               
                     old_sv ← new_sv; 
                 old_sv stores the indices of 
               
               
                   
                 the previous cycle 
               
               
                     [β T  β 0 ] ← M −1 [Y old _sv T  0] T ; 
                 (Eqn. (23)) preferably using 
               
               
                   
                 line search 
               
               
                     Other components of β ← 0 
               
             
          
           
               
                     new_sv ← indices i such that y i (Kβ) i  &lt; 1; 
                 new_sv is updated with the 
               
             
          
           
               
                   
                 indices of the support vectors 
               
               
                   
                 identified in the current cycle 
               
               
                    end while 
               
               
                    err ← ||X − FG|| Frobenius   
               
               
                   end while 
               
               
                 Return F, G, β, β 0   
               
               
                   
               
             
          
         
       
     
         [0070]    A similar implementation is shown as a flowchart in  FIG. 2 . One starts by receiving the matrix X (step  21 ) that is to be factorized by non-negative matrix factorization (NMF). If desired, a maximum error (i.e. Threshold_Err) and maximum number or permissible iterations (MAXITOR) may also be provided. As is explained above, matrix X will preferably be factorized into two matrices, F and G, and because in the present invention a maximum margin classifier is simultaneously identified during the NMF process, a corresponding bias vector β and an initial bias term β 0  will also be identified. 
         [0071]    The following iterations are repeated until the factorization error is below the stated maximum error (Threshold_Err) or until the specified maximum number of permissible iterations has been eached (step  35 ), which ever comes first. When either condition is reached, the resultant matrices F and G, bias vector β, and bias term β 0  are complete (step  39 ). 
         [0072]    Each eteration includes the following steps. First, an update for matrix F is obtained by 
         [0000]    
       
         
           
             
               F 
               
                 n 
                 + 
                 1 
               
             
             = 
             
               
                 F 
                 n 
               
               · 
               
                 
                   XG 
                   T 
                 
                 
                   
                     ( 
                     FG 
                     ) 
                   
                    
                   
                     G 
                     T 
                   
                 
               
             
           
         
       
     
         [0000]    (step  23 ). An update for G is then obtained in step  25  by: 
         [0000]    
       
         
           
             
               G 
               
                 k 
                 + 
                 1 
               
             
             = 
             
               
                 G 
                 k 
               
               · 
               
                 
                   
                     
                       
                         F 
                         T 
                       
                        
                       X 
                     
                     + 
                     
                       γ 
                        
                       
                         ( 
                         
                           
                             
                               
                                 
                                   
                                     G 
                                     k 
                                   
                                    
                                   
                                     diag 
                                      
                                     
                                       ( 
                                       
                                         
                                           
                                             ( 
                                             
                                               1 
                                               + 
                                               λ 
                                             
                                             ) 
                                           
                                            
                                           
                                             β 
                                             2 
                                           
                                         
                                         + 
                                         
                                           L 
                                           2 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 - 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     
                                       G 
                                       k 
                                     
                                      
                                     
                                       [ 
                                       
                                         β 
                                         · 
                                         
                                           ( 
                                           
                                             
                                               β 
                                                
                                               
                                                 λ 
                                                 2 
                                               
                                             
                                             + 
                                             L 
                                           
                                           ) 
                                         
                                       
                                       ] 
                                     
                                   
                                    
                                   
                                     1 
                                     T 
                                   
                                 
                                 - 
                                 
                                   
                                     
                                       ( 
                                       
                                         
                                           G 
                                           k 
                                         
                                          
                                         β 
                                       
                                       ) 
                                     
                                      
                                     
                                       [ 
                                       
                                         L 
                                         + 
                                         
                                           
                                             λ 
                                             2 
                                           
                                            
                                           β 
                                         
                                       
                                       ] 
                                     
                                   
                                   T 
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                   
                     
                       
                         ( 
                         
                           
                             F 
                             T 
                           
                            
                           F 
                         
                         ) 
                       
                        
                       
                         g 
                         k 
                         i 
                       
                     
                     + 
                     
                       γ 
                        
                       
                         ( 
                         
                           
                             G 
                             k 
                           
                            
                           
                             diag 
                              
                             
                               ( 
                               
                                 
                                   
                                     ( 
                                     
                                       1 
                                       + 
                                       λ 
                                     
                                     ) 
                                   
                                    
                                   
                                     β 
                                     2 
                                   
                                 
                                 + 
                                 
                                   L 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
                 . 
               
             
           
         
       
     
         [0000]    A matrix K is populated with G′G, and new_sv receives the indices of all the datapoints since the support vectors have not yet been identied (step  27 ). 
         [0073]    Step  29  is then repeated until new_sv (i.e. the support vectors identified during each iteration of step  29 ) remain constant, i.e. until the support vectors identified during a current iteration of step  29  match the support vectors identified in the immediately previous iteration of step  29  (as indicated in step  31 ). In this step  29 , vector β and bias term β 0  are determined by relation equations 23 or by [β T  β 0 ]←M −1 [Y old     —     sv   T  0] T  or, where old_sv is substituted for sv in the formulas, and all other components of β are set to 0. Variable new_sv is then updated with indices i such that y i (Kβ) is less than 1, and new_sv can now be compared with old_sv (step  31 ) to determine if step  29  should be repeated. 
         [0074]    Finally, the error in the current factorizing matrices F and G is determined, preferably by the Frobenius norm method (step  33 ). 
         [0075]    The following example illustrates the underlying properties of the penalized decomposition mentioned above. The efficacy of the method on a synthetic dataset, which is generated as follows, is demonstrated. For testing, instead of decomposing an initial matrix X into two factorizing matrices F and G, the present approach begins by first creating two test data set, matrices F test  and G test , and then combining them with some additional noise to synthesize a test matrix X test . The above process for NMF with incorporated function for identifying a maximum margin classifier is then applied to the synthesized test matrix X test  to determine if the relevant information from the starting matrices F test  and G test  can be successfully recovered. 
         [0076]    With reference to  FIG. 3 , three orthogonal bases  43 ,  43 , and  45  of seven dimensions are generated to form matrix F test  such that F test ∈          is first generated. In the present example, dimensions  3 ,  4  and  5  are in basis  41 ; dimensions  1  and  2  are in basis  43 ; and dimensions  6  and  7  are in basis  45 . 
         [0077]    With reference to  FIG. 4 , matrix G test , where G test ∈         , is drawn from two Gaussian distributions N(0; 0) and N(5; 5). In the present example, G test  consists of datapoints  1  to  100  in one class and datapoints  101  to  200  in a second class denoted by magnitude. 
         [0078]    Finally, the data test matrix X test  is synthesized by X test =(F test +α)G test , where α is some white Gaussian noise. Given such a data test matrix X test , the objective is now to decompose X test  into F recovered ∈          and G recovered ∈          where the r≧3 is chosen to provide enough dimensions against the random initialization of the matrices. Basically, since r is lost when F recovered  and G recovered  are combined, r is purposely choses greater than the original basis number in order to assure recovery of all bases. In other words, the decomposition into more dimensions than the actual rank, can be thought of as an over-complete dictionary, as described by Olshausen et al. in “Emergence of Simple-Cell Receptive Field Properties by Learning a Sparse Code for Natural Images”,  Nature , volume 381, pages 607-609, June 1996, which is herein incorporated in its entirety by reference. Owing to the sub-optimal properties of NMF, under random initialization, the basis vectors can be linear combinations of the actual basis. The results are shown in  FIGS. 5 and 6 . 
         [0079]    Specifically,  FIG. 5  shows the original and the learned basis vectors. The learned F recovered  matrix has 8 bases  51   a - 51   h  with seven dimensions. The original three bases  41 ,  43 , and  45  of F test  are also shown lined up with their corresponding, recovered bases  51   e ,  51   a , and  51   c , respectively. The remaining bases  51   b ,  51   d ,  51   f - 51   h  may be considered superfluous. 
         [0080]      FIG. 6  shows that the learned G recovered  matrix next to original test marix G test , for comparison purposes. For this data-set 200 new points were generated for testing. The misclassification error for training is around 3% and for testing is around 12% after 20 independent trials. As shown, the data separation is similar between G recovered  and G test , though G recovered  shows a few extranious point due to the added white noise. 
         [0081]      FIG. 7  shows the recovered vector β recovered . Only 8 entries of β recovered  contain non-zero values, as identified by spikes  1 - 8 , denoting the support vectors for the maximum margin classifier. 
         [0082]    Although the present experiment is synthetic, it brings out the important features of the present decomposition scheme. It identifies the correct basis, generates the feature matrices which are intuitive and also obtains the support vectors needed for classification of unseen data. 
         [0083]    The development presented above is an instantiation of the joint solution of the problem of feature decomposition as well as margin based classification. An inner product kernel has been shown to be useful for linearly separable data. For more complex data non-linear kernels such as radial basis functions may be needed. Though examples of such kernels are not shown above, it would certainly be worthwhile to obtain update rules for such kernels to make the present work more applicable to a wider array of problems. The update for the classifier parameter β is obtained by solving a Newton system. It remains as a future problem to impose non-negative constraints on β and derive a multiplicative update. 
         [0084]    Some work for multiplicative updates for svm&#39;s has already been reported in “Multiplicative updates for nonnegative quadratic programming in support vector machines”,  Advances in Neural Information Processing Systems  15, pages 1065-1073, 2003, by F. Sha, L. Saul, and D. Lee, hereby incorporated in its entirety by reference. The presentation in this work largely denotes a first step which is in no way complete. The cost function mentioned in Eqn. 7, is generic enough to allow additional constraints, such as orthogonality constraints, as well as sparsity of the basis vectors. All the recent developments within the NMF community, which modify the update equations, can still be applied without varying the classifier loop. Hopefully, this will lead to development of more useful tools in the future. 
         [0085]    While the invention has been described in conjunction with several specific embodiments, it is evident to those skilled in the art that many further alternatives, modifications and variations will be apparent in light of the foregoing description. Thus, the invention described herein is intended to embrace all such alternatives, modifications, applications and variations as may fall within the spirit and scope of the appended claims.