# LDA - solving singularity problem of within classes matrix

I would like to solve the problem in LDA where the within classes matrix is singular if the number of samples is lower than the number of dimensions (which is true in my case, used on images of faces).

I've seen suggestions that say that I should find a non-degenerated subspace on the data with PCA, but I don't really know how to begin. I have already implemented the LDA and it works good on other data, but with images of faces I am faced with this problem. Any guidelines, some pseudocode or an example would be really helpful.

LDA tries to maximise the ratio of between-class-scatter to within-class-scatter. That is - it seeks to find a projection where there is a big gap between the classes and small variance within one class.

The problem with scenarios where there are more features than samples is that there often is an infinite number of projections where within-class-scatter is 0. Hence there are infinite number of solutions with seemingly infinite gap between the classes.

A typical way to deal with this problem is to regularize the within-class-scatter matrix. And there are many different ways to go about it.

The simplest way to do this is by adding additional variance in all directions. To achieve this: add a small constant number to all the diagonal elements of the within-class-scatter matrix.

In order to use principal component analysis in combination with LDA you would do the following:

1. Compute the principal axes of PCA using your "training set" of faces.
2. Determine the number ($$n$$) of principal components you want to retain.
3. Project both the training and testing sets using the chosen number ($$n$$) of axes estimated from the training set. This will reduce the feature size of your samples to ($$n$$)
4. Apply LDA on top of the projected samples.

A closely related solution is using the Moore–Penrose pseudoinverse instead of inverse of the within-class-scatter matrix. And there are many more different tricks and types of regularizations that can be applied, depending on context and assumptions.

A not well-known observation is that a two-stage PCA is equivalent to an LDA if the W (within group covariance) matrix is full-rank.

This means it is an easy "trick" to do LDA if W is not full-rank (from 25 year old memory so check original paper!)

1. Compute the eigenvectors (E) and eigenvalues (L) of W

2. Using only the vectors of E with positive L, project the data onto this subspace (pca-1 scores)

3. Standardize the pca-1 scores

4. Do a PCA of the B (among covariance) matrix of the standardized pca-1 scores

5. The scores in this PCA-2 space are your LD scores

As has already been mentioned by Karolis Koncevičius, in general you should either regularize within-class covariance or find a non-degenerated subspace.

for the former, an easy way to do it is to toggle the "shrinkage" option in LDA or Matlab LDA package. Giving it a close-to-zero value will make it equivalent to applying Moore-Penrose pseudo inverse. Another option is to use "auto" shrinkage, of which the optimality is given by Ledoit-Wolf estimation.

for the latter, besides applying PCA before LDA, you can also select features by their Variational Inflation Factor, which excludes multicollinearity/singularity.

But to be honest, for the case where sample size is smaller than the number of features, you should better use Naive Bayes rather than LDA.

if the number of samples is lower than the number of variables, then you run highly in danger that the LDA will perform overlearning.

I also suggest to find a non degenerated subspace.

You write: "... images of faces"...

What about using a convolutional neural network (CNN)? They can be used for classification problems.