Information retrieval using sparse matrix sketching

Abstract

Embodiments of the invention include method of approximating a matrix of data using sparse matrices which includes receiving a first matrix and generating a second matrix based on the first matrix and a first sparse matrix. The method further includes generating a third matrix based on the first matrix and a second sparse matrix and generating a fourth matrix by generating a Moore-Penrose pseudo-inverse matrix based on the first matrix, the second matrix and the third matrix. The method also includes generating a fifth matrix based on a product of the second matrix, the third matrix, and a fourth matrix. The method further includes receiving, by a computer, a request to access at least one entry of the first matrix and responding to the request by accessing an entry of the fifth matrix.

1 . A method comprising:
 receiving a first matrix, A, having dimensions n×d;   generating a second matrix based on the first matrix, A, and a first sparse matrix, R, the second matrix having at least one dimension n;   generating a third matrix based on the first matrix, A, and a second sparse matrix, S, the third matrix having at least one dimension d;   generating a fourth matrix by generating a Moore-Penrose pseudo-inverse matrix based on the first matrix, the second matrix and the third matrix;   generating a fifth matrix, Â, based on a product of the second matrix, the third matrix, and the fourth matrix;   receiving a request to access at least one entry of the first matrix, A; and   responding to the request by accessing an entry of the fifth matrix, Â.   
     
     
         2 . The method of  claim 1 , wherein the second matrix is a matrix, RA, generated by multiplying the first matrix A by the first sparse matrix R, the second matrix, RA, having dimensions n×t, wherein t is defined as a polynomial of (k×ε −1 ×log n), k is a selected rank less than a rank of the first matrix A and ε is a small constant greater than zero. 
     
     
         3 . The method of  claim 2 , further comprising:
 receiving an input to select the selected rank k.   
     
     
         4 . The method of  claim 2 , wherein the fourth matrix has dimensions t×t′. 
     
     
         5 . The method of  claim 4 , wherein t′ is t 2 . 
     
     
         6 . The method of  claim 2 , wherein the third matrix is a matrix, AS T , generated by multiplying the first matrix, A, by the second sparse matrix S transposed, the third matrix, AS T , having dimensions d×t′. 
     
     
         7 . The method of  claim 6 , wherein the fourth matrix is a matrix, (SAR T ) − , generated by calculating a Moore-Penrose pseudo-inverse of a matrix (SAR T ). 
     
     
         8 . The method of  claim 2 , wherein at least one of the first sparse matrix, R, and the second sparse matrix, S, is configured to touch on each non-zero entry of the first matrix, A, a number of times greater than 1 and less than t. 
     
     
         9 . The method of  claim 1 , wherein at least one of the first sparse matrix, R, and the second sparse matrix, S, is configured to touch on each non-zero entry of the first matrix, A, exactly once. 
     
     
         10 . The method of  claim 1 , wherein the first matrix, A, is a term-document matrix and a sparse matrix. 
     
     
         11 . A computer program product for retrieving stored data, the computer program product comprising:
 a computer readable storage medium having program code embodied therein, the program code executable by a processor to:
 store a first matrix, A, having dimensions n×d, a first sparse matrix, R, and a second sparse matrix, S; 
 receive an input value, k, corresponding to a selected rank; 
 generate a second matrix, RA, by multiplying the first matrix, A, by the first sparse matrix, R, the second matrix, RA, having dimensions n×t, wherein t is defined as a polynomial of (k×ε −1 ×log n) and ε is a small constant greater than zero; 
 generate a third matrix, AS T , by multiplying the first matrix, A, by the second sparse matrix, S, transposed, the third matrix, AS T , having dimensions d×t′; 
 generate a fourth matrix, (SAR T ) − , by calculating a Moore-Penrose pseudo-inverse of a matrix, (SAR T ); 
 approximate the first matrix, A, by generating a fifth matrix, A, the fifth matrix defined as AS T ×(SAR T ) − ×RA; 
 receive a request to access at least one entry in the first matrix, A; and 
 generate a response to the request by accessing an entry in the fifth matrix, A. 
   
     
     
         12 . The computer program product of  claim 11 , wherein the processor is further configured to receive an input to select the selected rank, k. 
     
     
         13 . The computer program product of  claim 11 , wherein the first matrix, A, is a term-document matrix. 
     
     
         14 . The computer program product of  claim 11 , wherein the fourth matrix has dimensions t×t′. 
     
     
         15 . The computer program product of  claim 14 , wherein t′ is t 2 . 
     
     
         16 . The computer program product of  claim 11 , wherein at least one of the first sparse matrix, R, and the second sparse matrix, S, is configured to touch on each non-zero entry of the first matrix, A, exactly once. 
     
     
         17 . The computer program product of  claim 11 , wherein at least one of the first sparse matrix, R, and the second sparse matrix, S, is configured to touch on each non-zero entry of the first matrix, A, a number of times greater than 1 and less than t. 
     
     
         18 .- 20 . (canceled)