## 4 Concisely Indexed Multi-Keyword Rank Search
### Index Size Reduction  
It is trivial that using a small document index can increase the search efficiency, since the comparison of the query vector to the document indexes could be faster. One possible solution of reducing the size of document indexes is performing principal component analysis (PCA), which is one of the technologies to simplify data in multivariate statistical analysis, on the document indexes. To facilitate computation, put \(\mathbf{a}_{j}\) in a matrix \(A\), which is shown as follows:  
\[\mathbf{F}\] \[\mathbf{W}\rightarrow\ \ \begin{bmatrix}a_{1,1}&\dots&a_{1,n}\\ \vdots&\ddots&\vdots\\ a_{m,1}&\dots&a_{m,n}\end{bmatrix} \]  
The \(j\)th column of \(A\) is the document index of \(f_{j}\), i.e., \(\mathbf{a}_{j}\). Matrix \(A\) characterizes the relation between the words in the dictionary and the documents. Note that \(A\) is a sparse matrix in which most of the elements are zero. Suppose that each column of \(A\) is used as a data point in a high dimensional space. PCA is an orthogonal linear transformation that transforms the data points to a new coordinate system such that the projection of the data points onto the first coordinate has the largest variance, onto the second coordinate has the second largest variance, and so on so forth. Essentially, higher variance indicates that the corresponding dimension preserves more information about the original data set. In contrast, if the projection of the data points to some coordinate has low variance, less information of the data points is preserved in that dimension since the distance among the data points may be small and make it difficult to differentiate the data points. Therefore, it is possible to reduce the dimensions of a high dimensional data set to a low dimensional data set by eliminating those dimensions with low variance, such that only a commensurately small amount of information is lost. Specifically, PCA of the matrix \(A\) can be derived as follows. Let \(X\) be the matrix which is obtained by shifting \(A\) to its column mean, i.e.,  
\[X=\left[ \begin{array}{cccc}\mathbf{a}_{1}-\bar{\mathbf{a}}&\mathbf{a}_{2}- \bar{\mathbf{a}}&\cdots&\mathbf{a}_{n}-\bar{\mathbf{a}}\end{array} \right], \tag{3}\]  
where \(\bar{\mathbf{a}}=\frac{1}{n}\sum_{j=1}^{n}\mathbf{a}_{j}\). PCA wants to find the axis which maximizes the variance of the data points after projecting the data points to that axis. Formally, the projection of \(X\) onto a certain axis \(\mathbf{u}\) can be derived by \(\mathbf{p}=\left(X^{T}\mathbf{u}\right)\). The variance after the projection is given by  
\[\frac{1}{n}\|\mathbf{p}\|^{2}=\frac{1}{n}\Big{(}X^{T}\mathbf{u}\Big{)}^{T} \Big{(}X^{T}\mathbf{u}\Big{)}=\frac{1}{n}\mathbf{u}^{T}XX^{T}\mathbf{u}, \tag{4}\]  
where \(\mathbf{u}\) is a unit vector. To maximize the variance after projection to a certain coordinate, the problem can be formulated as  
\[\max_{\mathbf{u}} G(\mathbf{u})=\mathbf{u}^{T}XX^{T}\mathbf{u}\] s.t. \[\mathbf{u}^{T}\mathbf{u}=1\]  
The problem can be transformed to a nonconstraint problem using the Lagrange multiplier as follows:  
\[\max_{\mathbf{u}} \tilde{G}(\mathbf{u},\lambda)=\mathbf{u}^{T}XX^{T}\mathbf{u}+ \lambda\Big{(}1-\mathbf{u}^{T}\mathbf{u}\Big{)}. \tag{5}\]Taking the gradient of Equation (5), one can have  
\[\
abla_{\mathbf{u}}\tilde{G}(\mathbf{u},\lambda)=2 XX^{T}\mathbf{u}-2\lambda \mathbf{u}=0 \tag{6}\]  
\[\Rightarrow\quad XX^{T}\mathbf{u}=\lambda\mathbf{u} \tag{7}\]  
Thus, \(\mathbf{u}\) is the eigenvector of \(XX^{T}\), and the maximum \(G(\mathbf{u})\) is given by  
\[G(\mathbf{u})=\mathbf{u}^{T}XX^{T}\mathbf{u}=\mathbf{u}^{T}\lambda\mathbf{u}=\lambda, \tag{8}\]  
where \(\lambda\) is the corresponding eigenvalue. Consequently, \(\mathbf{u}\) is the coordinate which preserves the most variance when projecting the data points onto it, and it is the first principal component.