# Find "nearly" linearly dependent columns of matrix

For practical reasons I need to eliminate some columns of a matrix based on how close they are to being a linear combination of other columns (Not looking for a regularizing method like LASSO or anything here -- the constraints are related to hardware capabilities). I feel like this should be a standard test of some kind as opposed to a custom for-loop over the columns in which I fit a linear model of the other variables to get an L2 distance (or similar metric) to sort by. Ideally it could be done in an iterative fashion down to a certain number of columns (features) that I preset. Is there some standard method for this?

Note #1: I did try iterative elimination of columns based on the column which caused the largest decrease in matrix condition number as recommended by some (I standardized all the columns first). I found the pattern very interesting in that it wasn't a smooth curve (after logrithmic transformation) but had "intervals" if you will of decaying change with a sort of discontinuous jump between them. Is this expected behavior?

Note #2: I also took another look at PCA in terms of the Eigenvectors associated with the smallest eigenvalue, but the process of sequential elimination wasn't as obvious as the matrix condition number.

• reduced row echelon form or PCA? stats.stackexchange.com/questions/16327/… Aug 4, 2017 at 20:32
• hmm don't think so -- those are for determination of linear dependence and/or dimensional reduction but offer no insight into a quantification/degree of "closeness" by which one feature/column can be approximated by the rest of the features/columns.
– JPJ
Aug 4, 2017 at 21:17
• PCA's eigenvalue tells the cost for dropping the eigenvector in reconstructing the original matrix from the eigenvalue and eigenvector. So that tells the "degree" of linear dependence. The question is if doing a full diagonalization of your data is too costly. Actually you can try to find just the few smallest eigenvalues and corresponding eigenvectors for your matrix. that should be better for the computer. Probably there are still some details to fix. Aug 4, 2017 at 21:32
• I believe the question should be reopen, it is enough statistical. Aug 5, 2017 at 14:50
• The answer about PCA in that link says if eigenvalues are close to zero, the corresponding eigenvectors have non-zero entries correspond to the columns that are nearly linearly dependent to each other. Usually PCA just keep eigenvectors for large eigenvalues. In your case, you should find eigenvectors for eigenvalues that are closest to zero. Aug 5, 2017 at 16:17

One way I can think of is using matrix condition number. According to Wikipedia:

In the field of numerical analysis, the condition number of a function with respect to an argument measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the input, and how much error in the output results from an error in the input.

...

In linear regression the condition number can be used as a diagnostic for multicollinearity.[1][2]

[1] Belsley, David A.; Kuh, Edwin; Welsch, Roy E. (1980). "The Condition Number". Regression Diagnostics: Identifying Influential Data and Sources of Collinearity. New York: John Wiley & Sons. pp. 100–104. ISBN 0-471-05856-4.

[2] Pesaran, M. Hashem (2015). "The Multicollinearity Problem". Time Series and Panel Data Econometrics. New York: Oxford University Press. pp. 67–72 [p. 70]. ISBN 978-0-19-875998-0.

Here is a toy example:

> set.seed(0)
> x=runif(100)
> A1=cbind(x,x+runif(100)*1e-8)
> A2=cbind(x,2*x)
> kappa(A1)
[1] 329716417
> kappa(A2)
[1] 5.742016e+15

• Could you elaborate on your answer to help the OP use this approach to remove specific columns selectively?
– EdM
Aug 4, 2017 at 18:02
• I didn't know about this, but seems to have potential. As mentioned by Edm I would also like the answer expanded more though if possible.
– JPJ
Aug 4, 2017 at 18:12
• So after searching around a bit it is still unclear to me if it is a good idea to standardize columns prior to calculating the matrix condition number. It seems I would want to since this is based on a Norm calculation, but a confirmation would be nice.
– JPJ
Aug 4, 2017 at 21:15
• Although a large condition number detects collinearity, it does not find the basis of it as requested here.
– whuber
Aug 16, 2017 at 16:15