Finding the best subset in terms of Frobenius norm

Let us have $n$ vectors in $\mathbb{R}^m$ and let $P \in \mathbb{R}^{m\times n}$ be the matrix involving them in columns.

We aim to select $r$ columns and generate the remaining ones as linear combinations of them. Let $S \in \{1,\ldots,n\}$ be the index set showing which columns are selected and $P_S$ be the submatrix involving the selected columns. Then, the approximation will be written as

\begin{align} P\approx P_S R \end{align} where $R\in \mathbb{R}^{r\times n}$.

We aim to determine the set $S^*$ satisfying

\begin{align} \min_{S} \|P - P_SR\|_F^2 \end{align}

How can we determine this set without an exhaustive search over all combinations?

-

The number $r$ has a role to play in this (obviously). Let us say rank of your $m\times n$ matrix $A$ is $k$. If $r>k$, the answer is obvious, take ANY $k$ independent columns, add to that some other columns you like to make the total number columns of $r$, and above frobenius norm will be minimized to zero which is its optimal value, and you will have your $P_S$. Now if $k<r$, it becomes very much involved. There are $nC_r$ (combinatorially) possible subsets. Out of this subsets, you have to avoid the ones which are linearly dependent and then the search among others becomes exhaustive. One intuitive way to approach this problem is to take the best $r-$rank approximation of your matrix, say $P$. Clearly $PP^{\dagger}$ (pseudo-inverse) is the projection matrix to the columns of $P$. Let us assume (w.l.o.g) that the columns of $A$ are normalized. Then pick the $r$ columns which has the maximum projection in the column space of $P$, i.e. for each $a_i$ of $A$, calculate $p_i=PP^{\dagger}a_i$. Found out the $r$ columns in the decreasing order of $p_i$. The idea is to that by having $P$, the best $r-rank$ approximation, you have the best $r-rank$ approximation of range space of $A$ in some sense. So the vectors which have maximum inner-product in this space should be in some sense give the best representation for all vectors. The problem here is that to find the best $r-rank$ approximation one needs to find the SVD, and this can be a daunting problem if it is a very large matrix. Surprisingly there are recent results that multiplying by random matrices in a certain way, does give the best $r-rank$ approximation. Read on such low-rank approximations in this beautiful paper. Ofcourse, this is just one idea that might work intuitively. I can't think any else right now. Any ways I will think about it.

-
Thank you very much for the valuable comment. I've tried Randomized PCA for huge matrices and tried ColumnSelect algorithm of Mahoney and Drines which is a very similar approach to yours. But my concern is more about the problem's nature and I want to understand how difficult it is to find the global solution. I wonder if there exists such a method to find the best solution without exploring all the search space. – Helen Nov 25 '12 at 18:20
If such a method exists, then i believe it should be a greedy algorithm and also the data matrix should have some desirable properties. Because the original problem itself looks NP-hard (am not sure). – dineshdileep Nov 26 '12 at 5:02
I agree, it looks like NP-hard. – Helen Nov 26 '12 at 7:42