Projection-based techniques for updating singular value decomposition in evolving data sets

A method, comprising:

• by a data processing component of a computer system, carrying out vector space modeling of an evolving dataset for a latent analysis component of the computer system, wherein the evolving dataset is stored as a matrix in a memory subspace of the computer system, and wherein the evolving dataset comprises a first set of data as an initial matrix B with a truncated singular value decomposition (SVD) Bk written as:
• Bk=UkΣkVkH, wherein Uk represents k leading left singular vectors of the initial matrix B, Σk represents k leading singular values of the initial matrix B, and Vk represents k leading right singular vectors of the initial matrix B, and wherein the carrying out the vector space modeling comprises:
• receiving new data from at least one data source as an update to the evolving dataset;
• and
• in response to the receiving the new data, generating an updated truncated SVD of the evolving dataset, wherein the generating comprises, by an update module of the computer system:
• loading a second set of data from the at least one data source into the evolving dataset as a new matrix E;
• combining the initial matrix B and the new matrix E to form an updated matrix A, wherein a rank-k truncated SVD Ak of the updated matrix A is written as:
• Ak=Ûk{circumflex over (Σ)}k{circumflex over (V)}kH, wherein Ûk represents k leading left singular vectors of the updated matrix A, {circumflex over (Σ)}k represents k leading singular values of the updated matrix A, and {circumflex over (V)}kH represents k leading right singular vectors of the updated matrix A;
• generating a first projection matrix Z, wherein range(Z) approximates range(Ûk);
• generating a second projection matrix W, wherein range(WH) approximates range({circumflex over (V)}kH);
• and
• determining an approximate truncated SVD of the updated matrix A written as Ak≈(ZFk)Θk(WGk)H, wherein Θk represents k leading singular eigenvalues of a matrix ZHAW, Fk represents k leading left singular eigenvectors of the matrix ZHAW, and Gk represents k leading right singular eigenvectors of the matrix ZHAW, and wherein the determining comprises:
• setting the second projection matrix W equal to an identity matrix so that ZHAW=ZHA;
• and
• by carrying out 2k steps of a Lanczos algorithm on ZHAAHZ, determining the k leading left singular eigenvectors Fk and the k leading singular eigenvalues Θk;
• receiving a query at the latent semantic analysis component;
• in response to the receiving the query, identifying, by an indexing module of the computer system, relationships between the query and terms in the updated evolving dataset, wherein the identifying comprises finding latent factor associations in the updated evolving dataset based on the updated truncated SVD;
• and
• returning, by the indexing module, a result of the query based on the identified relationships.

A computer program product, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause a device to perform a method, the method comprising:

• carrying out, by the processor, vector space modeling of an evolving dataset for a latent analysis system, wherein the evolving dataset is stored as a matrix in a memory subspace of the computer readable storage medium, and wherein the evolving dataset comprises a first set of data as an initial matrix B with a truncated singular value decomposition (SVD) Bk written as:
• Bk=UkΣkVkH, wherein Uk represents k leading left singular vectors of the initial matrix B, Σk represents k leading singular values of the initial matrix B, and Vk represents k leading right singular vectors of the initial matrix B, and wherein the carrying out the vector space modeling comprises:
• receiving new data from at least one data source as an update to the evolving dataset;
• and
• in response to the receiving the new data, generating an updated truncated SVD of the evolving dataset, wherein the generating comprises:
• loading a second set of data from the data source into the evolving dataset as a new matrix E;
• combining the initial matrix B and the new matrix E to form an updated matrix A, wherein a rank-k truncated SVD Ak of the updated matrix A is written as:
• Ak=Ûk{circumflex over (Σ)}k{circumflex over (V)}kH, wherein Ûk represents k leading left singular vectors of the updated matrix A, {circumflex over (Σ)}k represents k leading singular values of the updated matrix A, and {circumflex over (V)}kH represents k leading right singular vectors of the updated matrix A;
• generating a first projection matrix Z, wherein range(Z) approximates range(Ûk);
• generating a second projection matrix W, wherein range(W) approximates range({circumflex over (V)}kH);
• and
• determining an approximate truncated SVD of the updated matrix A written as Ak≈(ZFk)Θk(WGk)H, wherein Θk represents k leading singular eigenvalues of a matrix ZHAW, Fk represents k leading left singular eigenvectors of the matrix ZHAW, and Gk represents k leading right singular eigenvectors of the matrix ZHAW, and wherein the determining comprises:
• setting the second projection matrix W equal to an identity matrix so that ZHAW=ZHA;
• and
• by carrying out 2k steps of a Lanczos algorithm on ZHAAHZ, determining the k leading left singular eigenvectors Fk and the k leading singular eigenvalues Θk;
• receiving a query at the latent semantic analysis system;
• in response to the receiving the query, identifying relationships between the query and terms in the updated evolving dataset, wherein the identifying comprises, by the processor, finding latent factor associations in the updated evolving dataset based on the updated truncated SVD;
• and
• returning, by the processor, a result of the query based on the identified relationships.