# Data Quality Measures and Efficient Evaluation Algorithms for Large-Scale High-Dimensional Data
## 3 Methods
### Proposed Data Quality Measures
#### 3.2.1 Class Separability  
Our first data quality measure tries to capture the class separability of a dataset by combining the within-class variance and between-class variance, similarly to [PERSON]'s LDA (1) but more efficiently for large-scale and high-dimensional data and comparable with other datasets.  
We start from creating the normalized versions of the matrices \(S_{w}\) and \(S_{b}\) in [PERSON]'s LDA (1) so that they will not be affected by the different numbers of examples in classes (\(m_{i}\) is the number of examples in the \(i\)-th class) across different datasets. The normalized versions are denoted by \(\hat{S}_{w}\) and \(\hat{S}_{b}\):  
\[\hat{S}_{w}:=\sum_{i=1}^{c}\frac{1}{m_{i}}\sum_{j=1}^{m_{i}}(x_{i,j}-\overline {x}_{i})(x_{i,j}-\overline{x}_{i})^{T},\qquad\hat{S}_{b}:=\sum_{i=1}^{c}\frac{ m_{i}}{\sum_{j=1}^{c}m_{j}}(\overline{x}_{i}-\overline{x})(\overline{x}_{i}- \overline{x})^{T}. \tag{2}\]  
Considering the determinants of these \(n\times n\) matrices as in the original [PERSON]'s LDA will be too costly for a high-dimensional data where \(n\) is large, since the time complexity to compute the determinants will be proportional nearly to \(n^{3}\). Instead, we consider the direction of maximum linear separation \(v\in\mathbb{R}^{n}\) that maximizes the ratio of between-class variance to the within-class variance being projected onto the vector. Using the vector, we define our first data quality measure \(M_{sep}\) for class separability as follows:  
\[M_{sep}:=\max_{v\in\mathbb{R}^{n}:\|v\|=1}\frac{|v^{T}\hat{S}_{v}v|}{|v^{T} \hat{S}_{w}v|}. \tag{3}\]  
This formulation is almost the same as (1) in [PERSON]'s LDA except that (1) finds the projection matrix \(\phi_{lla}\) which maximizes the [PERSON]'s criterion, while, in (3), we will focus on finding the maximum value of [PERSON]'s criterion itself. Unlike [PERSON]'s criterion, our measure \(M_{sep}\) is comparable across datasets with different numbers of classes and examples due to normalization, to check the relative difficulty of linear classification.  
Solving (3) directly will be preventive for a large \(n\) as in the original LDA. If \(\hat{S}_{w}\) is invertible, we can calculate the vector which maximizes \(M_{sep}\) as follows using simple linear algebra. To find the vector \(v\) which maximizes the equation in (3), first differentiate it with respect to \(v\) to get:  
\[(v^{T}\hat{S}_{b}v)\hat{S}_{w}v=(v^{T}\hat{S}_{w}v)\hat{S}_{b}v.\]  
This leads us to the following generalized eigenvalue problem in the form of:  
\[\hat{S}_{w}^{-1}\hat{S}_{b}v=\lambda v, \tag{4}\]  
where \(\lambda=\frac{v^{T}\hat{S}_{w}v}{v^{T}\hat{S}_{w}v}\) can be thought as an eigenvalue of the matrix \(\hat{S}_{w}^{-1}\hat{S}_{b}\). The maximizer \(v\) is the eigenvector corresponding to the largest eigenvalue of \(\hat{S}_{w}^{-1}\hat{S}_{b}\) which can be found rather efficiently by the Lanczos algorithm Lanczos (1966). However, the overall time complexity for computation can be up to \(\mathcal{O}(n^{3})\), which makes it difficult to calculate the optimal vector for high-dimensional data, such as images. In Section 3.3, we provide an efficient algorithm to compute \(M_{sep}\) using random projection.