## 4 Concisely Indexed Multi-Keyword Rank Search
### Index Size Reduction
Note that projecting the data point \(\mathbf{x}_{j}\), i.e., the \(j\)th column of \(X\), onto \(\mathbf{u}\), is equal to \(\mathbf{u}^{T}\mathbf{x}_{j}\), which is the magnitude of the projection of \(\mathbf{x}_{j}\) on the coordinate \(\mathbf{u}\). Analogously, the \(k\)th principal component can be found by subtracting the first \(k-1\) principal components from \(X\). Denote \(\mathbf{u}_{j}\) as the eigenvector in the order of the principal components and \(\lambda_{i}\) as the corresponding eigenvalue. The resulting eigenvalues have the relation \(\lambda_{1}>\lambda_{2}>\cdots>\lambda_{m}\). It is noted that for square matrix, the eigenvectors of the matrix are orthogonal. Since \(XX^{T}\) is square, the eigenvectors form the basis for a new space. Consequently, PCA transforms the original data set to the new space. One can write the projection in matrix form as follows:  
\[T=U^{T}X, \tag{9}\]  
where \(U=[\mathbf{u}_{1}\quad\mathbf{u}_{2}\ldots\mathbf{u}_{m}]\) and \(T\) contain the coordinates of the data points in the new space. As mentioned before, since the former principal components preserve more information of the data, one can eliminate some later principal components with only a small amount of information loss. Suppose that only the first \(r\) principal components are preserved. One can project a high dimensional data set to a lower dimensional space, i.e.,  
\[T_{r}=U_{r}^{T}X, \tag{10}\]  
where \(U_{r}=[\mathbf{u}_{1}\quad\mathbf{u}_{2}\ldots\mathbf{u}_{r}]\) and \(1\leq r\leq\min\{m,n\}\). In general, \(r\) would be much smaller than \(m\) or \(n\), where \(m\) is the number of words in the dictionary and \(n\) is the number of documents. In fact, the transformation preserves the maximum variance of the data points for the case of projecting the data points in a \(r\) dimensional space and the reconstruction error, i.e., \(\left\|UT-U_{r}T_{r}\right\|^{2}\), is minimized. Actually, the new space basis can be obtained from the singular value decomposition (SVD) of \(X\). Suppose that the SVD of \(X\) is  
\[X=U\Sigma W^{T}, \tag{11}\]  
where \(U\) is a \(m\times m\) matrix in which the column vectors are orthonormal, \(\Sigma\) is a diagonal matrix and \(W\) is a \(n\times n\) matrix, in which the column vectors are also orthonormal. From Equation (7), the eigenvalue decomposition of \(XX^{T}\) can be derived as  
\[\max_{\mathbf{u}} G(\mathbf{u})=\mathbf{u}^{T}XX^{T}\mathbf{u}\]0  
where \(\Lambda\) is a diagonal matrix with the eigenvalues on the diagonal and \(\Lambda=\Sigma\Sigma^{T}\). Note that \(\Lambda\) and \(\Sigma\) are diagonal matrices. Denote \(\lambda_{i}\) and \(\sigma_{i}\) as the \(i\)th term on the diagonal of matrix \(\Lambda\) and \(\Sigma\), respectively. Thus, \(\lambda_{i}=\sigma_{i}^{2}\) and the eigenvectors of \(XX^{T}\) are the left singular vectors of \(X\). Rearrange the SVD of \(X\) as  
\[\max_{\mathbf{u}} G(\mathbf{u})=\mathbf{u}^{T}XX^{T}\mathbf{u}\]1Obviously, the coordinates of the data points after projecting to the new space can be obtained by \(\Sigma W^{T}\) from the SVD of \(X\). Analogously to reducing the dimensions of the index, the coordinates in the low dimensional space are given by  
\[\max_{\mathbf{u}} G(\mathbf{u})=\mathbf{u}^{T}XX^{T}\mathbf{u}\]2  
Note that \(\Sigma_{r}\) is a \(r\times r\) diagonal matrix with the first \(r\) singular values in \(\Sigma\) and \(W_{r}\) is a \(n\times r\) matrix, which is composed of the first \(r\) columns of \(W\).