# Data Analysis for Information Discovery
## 6 SPQR Algorithm  
Many data applications deal with the necessity to represent \(m\) objects characterized by \(n\) features. One of the most often used representations of this kind of data is a matrix **A** composed of \(m\) rows and \(n\) columns. In modern applications of data analysis, such as image analysis and environmental datasets, these matrices often have high dimensionalities. This fact leads to a series of difficulties in the processes of data mining, representation, communication, and storage. In the latest years, many works in the field of feature selection [41] have demonstrated that, through analyzing a dataset, it is possible to identify and eliminate some redundant and/or irrelevant features. By applying feature selection methods, it is possible to achieve a series of advantages in data analysis processes, such as a decrease in the amount of data, an improvement in the prediction accuracy, pulling out important features, understanding the attributes or variables easily, and finally reducing the execution time [41]. An interesting overview on feature section methods can be found in [41]. Many of these methods aim to approximate the matrix A by means of a \"smaller\" matrix obtained by combining its columns and rows. The drawback of these methods is that they usually yield dense factorizations, and more seriously, these terms are often much harder to interpret than the original ones. For example, truncating the SVD at \(k\) terms is one of the most common ways to obtain the \"best\" rank-\(k\) approximation of \(A\) when measured with respect to any unitarily invariant matrix norm. The drawback of this method is that it produces a representation of the dataset that is difficult to relate to the original dataset and to the processes that generated it. The same drawbacks are present in another widely used method for feature selection: principal component analysis (PCA). Starting from these considerations, many methods to solve the column subset selection problem have been developed [42]. These methods try to find a subset of k actual columns of A, with \(k\) less than \(n\), which \"captures\" most of the information of A with respect to the spectral or the Frobenius norm. Essentially two classes of methods may be defined:  
1. Randomized methods: these methods select the most representative columns in a matrix using probability distributions;
2. Deterministic methods: these methods select the columns in a deterministic way. An effective deterministic method to reduce the matrix A to its more important columns is \"semi-pivoted QR approximation\" (SPQR) by [PERSON] [5; 27; 43]. As its name suggests, the key approach is the QR decomposition of A into an orthogonal matrix Q and a triangular matrix R. These factors are computed by the Gram-Schmidt algorithm for orthonormalizing the columns of A, one at a time, from first to last. In many situations _pivoted_ QR is preferred: in practice, columns are exchanged at the start of each new stage to take the largest remaining column. In this way a permutation matrix P is built such that:  
\[\text{A}\cdot\text{P}=\text{Q}\cdot\text{R} \tag{8}\]  
When A is rank deficient, the column pivoting A\(\cdot\)P is applied to improve the numerical accuracy. Moreover, the choice of P usually guarantees that R does not have increasing diagonal entries, a specific feature which is useful in the following. More in detail, we may partition the expression above as:  
\[[\text{ }B_{1}\text{ }B_{2}]=[\text{ }Q_{1}\text{ }Q_{2}] \begin{bmatrix}\text{R}_{11} &\text{R}_{12}\\ 0&\text{R}_{22}\end{bmatrix}  \tag{9}\]  
The following properties hold:  
1. \(\text{B}_{1}=\text{Q}_{1}\cdot\text{R}_{11}\)
2.