# A Generic Block-Level Error Confinement Technique for Memory Based on Principal Component Analysis
## 3 PCA-Based Error Confinement Technique
### Modularization for Reducing Computation and Extracting Local Features  
The computational cost of PCA heavily depends on the size of covariance matrix calculation and the dimension of Eigen vectors. For generic data, it is beneficial to preprocess the original data by dividing them into sub data blocks. Such procedure is named as modularization in data compression. Furthermore, data modularization assists in the extraction of local features of the original data. Consequently, modularization before PCA is applied offers less lost in data quality upon reconstruction and achieves significant speedup in both PCA and data reconstruction. The method of  
Figure 1: The overall block diagram of error confinement technique based on PCA. Feature extraction and reconstruction of original data with modular PCA is shown in Figure 2. For the data X to store, we first divide it into multiple sub-blocks X\({}_{i}\) ( i from 1 to N\({}_{sub}\), and N\({}_{sub}\) is the total number of sub data blocks), then we respectively extract the features of those sub-blocks based on PCA. Finally, each sub block data is reconstructed from the corresponding feature. After getting the reconstructed data of each sub block, the reconstructed data X\({}^{\prime}\) of the original data X is reassembled with the reconstruction data of sub-block according to the original data block structure. It is important to analyse how modularization strategies affect the execution time of PCA. Besides, the analysis on the effect of modularization to the quality of reconstructed images is discussed in detail in Section 3.2. The main operations of PCA are matrix multiplication and Eigen decomposition. The modularization strategy needs to be analysed from two dimensions: horizontal and vertical. Assume the dimension of matrix X is \(m\times n\), and the size of sub block is a\(\times\)b, then the row can be divided into \(\frac{m}{a}\) groups, and the column can be divided into \(\frac{n}{b}\) groups. This gives the total number of sub-blocks as \(N_{sub}=\left(\frac{m}{a}\right)*\left(\frac{n}{b}\right)\). According to the operational steps of PCA, the time complexity is analysed as follows:  
1. Subtracting the mean from the element of matrix X as shown in Equation (4). The time complexity for each sub-block is O(\(a\times b\)), then the total time complexity of this step for all sub-blocks \(T_{1}\) is: \[T_{1}=N_{sub}\times\text{O}(a\times b)=\text{O}(m\times n)\] (7)
2. Calculating the covariance matrix S and normalizing the covariance as shown in Equation (5). We can get a covariance matrix of \(b\times b\) dimension for each sub block. The time complexity for each sub-block is O ( \(b^{2}\times a\)), then the total time complexity of this step for all sub-blocks \(T_{2}\) is: \[T_{2}=N_{sub}\times\text{O}(\text{ }b^{2}\times a)=b\times\text{O}(m\times n)\] (8)
3. Computing eigenvalues and eigenvectors by Eigen decomposition. According to [26], The time complexity of calculating eigenvectors for a b\(\times\)b matrix need O \(\left(b^{3}\right)\), so the total time complexity of this step for all sub-blocks \(T_{3}\) is: \[T_{3}=N_{sub}\times\left(b^{3}\right)=\left(\frac{b^{2}}{a}\right)\times\text{ O}(n\times m)\] (9)  
Figure 2: Feature extraction and reconstruction of original data with modular PCA. 4. Projecting the data X to the orthogonal space defined by the matrix composed of eigenvectors according to Equation (6). If the largest k principal elements are retained, the dimension of the matrix composed of eigenvectors is \(b\times k\), (\(k<b\)).