# Linearly dependent features

I have a matrix A of 1000 observations (rows) and 100 features (cols). I would like to find:

1. Linearly dependent features so that I can remove them and simplify the problem. rank(A) gives me 88, which I assume means that 12 of the features are linearly dependent. Am I right?
2. After the above step, how do I determine which 12 out of the 100 columns are linearly dependent? I know there is no unique answer. But does that mean I can choose any 12 columns?
3. Let's say I choose to remove the last 12 columns. But before removing them, I what to find the 12 linear combinations that compute to the last 12 columns. How do I get these?

So far I have tried using Matlab's PCA, QR and SVD, but each of them give different matrices and I don't know how to use these matrices to get what I want.

A little late but...

There's a measure called Pearson correlation that can be used to find linear correlation (dependence) between two variables X and Y. In short it is the covariance of the two variables divided by the product of their standard deviations:

The result is a value between +1 and −1 inclusive, where 1 is total positive correlation, 0 is no correlation, and −1 is total negative correlation.

Using it you can find which columns correlate and ignore (some of) them.

• This is incorrect. Linear dependency has nothing to do with correlation. Linear dependency occurs when one variable is linear function of one or more variables in your data. What you are talking about here is called multicollinearity. – Indrajit Nov 23 '17 at 12:34
• Agree with Indrajit that, mathematically, linear independence and correlation are not the same. However, in practice, high-correlated feature removal does a decent job on dimension reduction. – Diansheng Mar 21 at 9:37

One approach would be to use an incomplete Cholesky factorisation, I have some MATLAB code here, see the paper by Fine and Scheinberg mentioned on that page for details.

• I get the following error with your code: >> [L, p] = cholincsp(mydata, 10^-10); Index exceeds matrix dimensions. Error in cholincsp (line 78) L(diagonal(i:m)) = X(diagonal(p(i:m))) - sum(L(i:m,1:i-1).^2,2)'; – Prometheus Apr 4 '14 at 10:41
• It is a while since I last used it, I think you need to perform the CHolesky decomposition of A^TA rather than A. – Dikran Marsupial Apr 4 '14 at 11:14
1. Yes, rank roughly tells you how many column-vectors (features) are independent.

2. No, you can't remove arbitrary columns. You can try removing random columns and calculating the rank of a result — you'll see different numbers. You need to remove only those features that are dependent.

Or, suppose that you generated data in a way that only the last 12 columns depend on the first ones. Can you still delete any 12 columns?

What you can do, though, is to perform PCA with number of components equal to the rank. This will not only reduce the dimension of your space, but will also decorrelate your features. The drawback of such transformation is a (possible) loss of interpretability, but it's not a mathematical thing, if you want to preserve it, you should delete features based on your insight.

3. Suppose your data matrix is of form $(X; Y)$ where $X$ and $X$ are submatrices of form n_rows × (n_cols - 12) and n_rows × 12, respectively. That means, that $X$ and $Y$ are submatrices formed by slicing out last 12 columns. If you want to find 12 linear combinations of $X$ to get $Y$, you actually want to solve 12 systems of linear equations of the form

$$X b_i = Y_i$$

Where $Y_i$ is $i$th column of $Y$. Now unite all these equations into one by gluing together all the $b_i$ into a matrix $B$ of shape (n_cols - 12) × 12. The equations then become

$X B = Y$

Note that X is not square, thus is not invertible. Fortunately, the solution still exists, and is given by pseudoinversion:

$$B = (X^T X)^{-1} X Y$$

Note: now somebody thoughtful enough might notice that the way I provided the above formula looks like we can express any set of columns of original data matrix as the linear combination of the rest. How can it be? Does it mean that any set of columns is linear dependent on all others? This sounds crazy!

Of course, there is an important note about $X$ here. Notice $X^T X$ that is inverted. In order to invert a matrix it needs to be of a full rank. That means that $X$ has to have full column rank, that is, have rank equal to the number of columns.

Another interesting thing is a case when some of $Y_i$ are actually independent of $X$. Clearly, there's no place for the formula to break, but what's the meaning of a result, what have we got? In that case the result $b_i$ is a coefficient vector of an orthogonal projection of $Y_i$ onto space spawned by columns of $X$. In a sense it's a closest linear combination of $X$.