Information retrieval using sparse matrix sketching

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, AST, by multiplying the first matrix, A, by the second sparse matrix, S, transposed, the third matrix, AST, having dimensions d×t′;
• generate a fourth matrix, (SART)−, by calculating a Moore-Penrose pseudo-inverse of a matrix, (SART);
• approximate the first matrix, A, by generating a fifth matrix, A, the fifth matrix defined as AST×(SART)−×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.