4
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – usεr11852
    Commented Jan 21, 2015 at 22:20
  • 9
    $\begingroup$ 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. $\endgroup$
    – amoeba
    Commented Feb 12, 2015 at 22:42
  • $\begingroup$ One might perhaps be able to remove some rows and columns that leaves a matrix which is well approximated by a lower-ranked matrix $\endgroup$
    – Glen_b
    Commented Aug 3, 2017 at 4:04

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – amoeba
    Commented Feb 12, 2015 at 15:36
  • $\begingroup$ 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... $\endgroup$
    – amoeba
    Commented Feb 12, 2015 at 22:01
  • 3
    $\begingroup$ The problem statement treats rows and columns perfectly symmetrically. The appearance of different recommendations for processing them is therefore quite surprising. $\endgroup$
    – whuber ♦
    Commented Feb 12, 2015 at 22:10
  • $\begingroup$ @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. $\endgroup$
    – EngrStudent
    Commented Feb 12, 2015 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.