fbreuer / analytic-feature-selection Goto Github PK

To calculate the dimension of the affine hull, we need to check whether the origin is in the affine hull of the rows. This is currently implemented in zero_vector_present in

https://github.com/stambizzle/thesis/blob/master/thesis_code/general_feature_selection.py

However zero_vector_present checks only if one of the rows is zero. I will fix this.

Two questions about the implementation of matrix rank, i.e., my_matrix_rank:

1. What does the argument values of my_matrix_rank mean?
2. An alternative to using the SVD for computing the rank would be to use the QR decomposition. An advantage would be that numerical convergence is no longer an issue. How do SVD and QR compare performance-wise?

There are two ways to check whether a vector is in the affine hull of a set of points:

1. Via ranks

The dimension of the affine hull of vectors v_1,...,v_n can be calculated via get_poly_dim, i.e. dim(aff(v_1,...,v_n)) = get_poly_dim(M) where M is the matrix with the v_1,...,v_n as rows. Using this notation, we can check whether a vector w is contained in the affine hull of v_1,...,v_n as follows:

If dim(aff(v_1,...,v_n,w)) > dim(aff(v_1,...,v_n)), then w is not contained in the affine hull. Otherwise w is contained in the affine hull.

So we need only use get_poly_dim twice to check this. (Checking whether the zero vector is in the matrix will do us no good.)

Note that the dimensions will differ only by 1! So small numerical errors in the rank computation may lead to a wrong result here.

2. By solving linear systems

To check if w is contained in the affine hull of the vectors v_1,...,v_n one can simply check if the linear system Mx=(w-v_n) has a solution, where M is the matrix with columns (!!!) v_1-v_n, v_2-v_n, ..., v_{n-1}-v_n.

If Mx = (w-v_n) has a solution, w is contained in the affine hull. Otherwise w is not contained in the affine hull.

If there is only one w that has to be check, we only need to solve one linear system here, whereas with the previous method, we needed to compute two ranks. However, if we need to do this check for many w, then there is no significant difference in theoretical complexity.

We have different spellings for

"dataset" <-> "data set"
"pointset" <-> "point set"
"featureset" <-> "feature set"

floating around the text. We need to settle on one convention and stick to it.

Preferences?

For this we essentially need to convert a V-description of an affine space into an H-description. I will think about how best to do this with what we have in numpy.linalg.