Maximal subset with rank $k$

I'm trying to solve the following problem for an algorithm I'm trying to develop and I couldn't find anything helpful in scholar google. Here is the question:

Suppose I have a set of $N$ vectors $V=\{x_1,...,x_N\}$ and a positive integer $k$. I would like to find the largest subset from V (as many vectors as possible) that has dimension $k$ (the rank of the matrix of those vectors will be $k$).

Any ideas on how to solve this redundancy problem? I was thinking about pivoted QR or Interpolative Decomposition, but I got a dead end.

If this helps, I don't mind that instead of rank smaller than $k$ I will obtain a solution that gives nuclear norm smaller than some given positive number (i.e. the sum of singular values).

Thanks, Gil

-
You should specify whether by "largest" subset from $V$, you mean "maximum in cardinality" or "maximal with respect to inclusion." In the latter case, there could feasibly be multiple solutions. Also, the title of this poset should really be "maximal subset with rank $k$" or something similar. – goblin Feb 4 '13 at 10:46

This is a Thought: First of all, lets put all your vectors into a $M \times N$ matrix $A$ whose columns are the given vectors (assuming, they lie in $N$ dimensions).

There are several aspects to any algorithm you come up with. Broadly speaking, the algorithm can be split into two parts

• $k$-rank basis: First you have to select a $k$-rank basis. There are $nC_k$ (combinatorial) possibilities for this. This can be prohibitively expensive in computation.
• Enlarging the Set: In general, for each of the above mentioned possible basis, you need to select some of the vectors from the remaining ones and see the maximum cardinality possible. It is easy to see that there should be $2^{n-k}$ possibilities for that for each basis chosen.

If you can't do it via the brute-force approach (which is most possibly the case), you will have to resort to some kind of heuristic approach. I don't have a strict formal argument to prove how good it is (or to check for that matter).

• $k$-rank basis: Take the best $k$-rank approximation to the matrix $A$, call it $A_K$. Now form the projection matrix $P_K=A_K A_K^{\dagger}$ ($\dagger$ denotes pseudo-inverse). Now, find $A_P=P_KA$. Calculate the norm of each column of $A_P$ and choose the indices of the first $k-$vectors with the highest norm. Corresponding to the same indices of this columns, choose the corresponding ones in $A$. This will be $\textit{most probably}$ a set with $k$-rank. Now, form the basis matrix $B_K$ with this vectors as columns.

• Enlarging the set: Form the orthogonal projection matrix $P_B=I-B_KB_K^{\dagger}$. Multiply all the remaining $n-k$ vectors in $A$ with $P_B$, choose all those vectors which are zeroed out when multiplied by $P_B$ (they are zeroed out, because they doesn't lie in span of $B_K$ and thus adding them to our set will increase the rank).

-
Thanks. Some of your tips were helpful. A good way for choosing the first k-rank base can be done using QR decomposition. epubs.siam.org/action/…; – Gil Feb 7 '13 at 9:59