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.
 A: 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.  
A: 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".
