Treelets as feature transformation tool for block diagonal linear discrimination

The main novelty of this paper is to apply treelets as a feature transformation tool prior to using block diagonal linear discriminant analysis (BDLDA). Using pairwise feature transformations, treelets seek to approximate the decorrelation behavior of principal component analysis (PCA) without requiring identifying the eigenvectors of the full covariance matrix. Instead, PCA is successively applied to pairs of features, which makes it possible to reduce the magnitude of off-diagonal terms of the resulting covariance matrix, even in scenarios where the number of available training samples is small relative to the feature vector dimension. BDLDA seeks to find a block diagonal approximation to the covariance matrix that can capture the most discriminant sets of features and their correlations. Treelet-based preprocessing facilitates the BDLDA search primarily because each treelet coefficient is a linear combination of several original features. Blocks obtained after applying BDLDA to treelet coefficients are in effect larger (a larger number of original features are used). Thus treelets combined with BDLDA makes it possible to find block diagonal structures with larger effective blocks, so that the correlations between a larger number of features can be taken into account. Our experiments demonstrate that this leads to better classification performance for real DNA expression data than state of the art LDA-based techniques.