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?