# Maximally reducing the rank of a matrix by removing some rows or columns

I have a $N \times M$ matrix, and the rank of matrix, $r$, is near $\min(M,N)$.

I want to minimize the rank by removing some of the rows or columns to get $r \ll \min(M,N)$. The goal is to achieve least rank for the least number of removals.

Any approach for above challenge would be really appreciated.

• Assuming your matrix $X$ is not full rank (as $r < min(M,N)$) are you simply asking to find a way to keep only your dependent columns/rows? Loosely speaking dependent columns "do not contribute" to $X$'s rank. So you could detect those dependent rows, keep them and probably have a matrix with a very small $r$ (maybe even 1). – usεr11852 says Reinstate Monic Jan 21 '15 at 22:20
• Removing one row or one column can reduce the rank at most by $1$. Therefore it's not clear what you want to optimize: making $k$ removals, you can at best reduce the rank to $r-k$, which is going to be close to $\min(M_\mathrm{reduced},N_\mathrm{reduced})$. Doesn't look like you can gain much. – amoeba says Reinstate Monica Feb 12 '15 at 22:42
• One might perhaps be able to remove some rows and columns that leaves a matrix which is well approximated by a lower-ranked matrix – Glen_b Aug 3 '17 at 4:04

I would look at singular value decomposition.

In MatLab notation:

[U,S,V]=svd(A)


The matrix of eigenvalues, "S", has only the diagonal populated and in descending order. The first element of the diagonal should be the largest. This progresses down to the last element of the diagonal which should be the smallest.

You can substitute the elements in "S" with zeros and re-create your data. If 98% of the norm of the S matrix is due to the first two elements, then it is considered reasonable to set the remainder to zero. If you were bold, you could rotate the system into the eigenvector system and reduce your data to 2-element vectors.

In using this approach you can reduce the dimension of your data to the number of relevant elements in the "S" matrix. If you are willing to rotate the data then it may allow you to reduce the dimensionality of your data to substantially below the rank. I see this as "addressing the question behind the question" of the OP.

This is going to depend on what the data lets you do. Mileage is going to vary.

EDIT:

If I just wanted to delete columns, then I would use a random forest to determine variable importance. (Example)

If I wanted to delete rows, then I would use bootstrap experiment to draw some random number of rows and compute a measure of interest, then increase the number of samples and recompute. At the level where my measure of interest stops changing is the number of rows that are informative. Cross-validation can help determine this with lower noise in exchange for more compute time. When you determine the number of rows that gives sufficient information, then you can uniformly randomly select that number of rows from the data and throw the rest away.

These are textbook ways to amputate lower value data. The rotation would allow you to retain information while reducing the dimension - it isn't as much of an amputation as it is a more dense packing.

• I don't see how this answers the question. Your procedure will not result in removing "some of the rows or columns", as asked by the OP. – amoeba says Reinstate Monica Feb 12 '15 at 15:36
• That's some interesting suggestions in your edit. +1. However, even though I am not sure what exactly OP was asking about, it seems that he/she had yet another thing in mind... – amoeba says Reinstate Monica Feb 12 '15 at 22:01
• The problem statement treats rows and columns perfectly symmetrically. The appearance of different recommendations for processing them is therefore quite surprising. – whuber Feb 12 '15 at 22:10
• @whuber, the OP wants rank less than M or N. If they were to reduce through both setting low magnitude eigenvalues to zero and then rotating to whatever was left - the rank of the column-space would be the number of non-zero elements in the diagonal of the eigenvalue matrix. – EngrStudent - Reinstate Monica Feb 12 '15 at 23:37

I'm not sure what the form of the matrix is, but if for example you have "m" variables with "n" corresponding observations, you could do a PCA to potentially reduce the size of the matrix but only in "m".

• matrix values are 1 or 0 , a(i,j)=1 when entity 'i' interacts with entity 'j' and a(i,j)=0 when there is no interaction between them. – user2466699 Dec 8 '14 at 11:47
• This does not provide a solution, because doing PCA is not equivalent to removing some rows or columns, as asked by the OP. – amoeba says Reinstate Monica Feb 12 '15 at 15:48