Patent ID: 8255401

Claim:
A method comprising: computer information retrieval using latent semantic structure via sketches, the retrieval comprising: receiving an input n×d matrix A with a computer; receiving an input parameter k; receiving a small constant eps, where eps is greater than zero; generating a random d×(k/eps) sign matrix R; generating a random n×(k/eps^2) sign matrix S; computing a matrix product A*R; computing a matrix product S^T*A, where S^T is (k/eps^2)×n matrix, and where S^T_{i,j}=S_{j,i}); computing S^T*A*R; computing the Moore-Penrose pseudoinverse C of S^T*A*R; computing the singular value decomposition U*Sigma*V^T of C, where U is (k/eps)×(k/eps), Sigma is dimensional matrix (k/eps) by (k/eps), and V is (k/eps^2)×(k/eps); and outputting the three matrices ARU, Sigma, and V^TS^TA as factorization in applications.