Given a matrix $A$ I need to select a "representative" subset of its columns so that the each non-selected column is as close as possible to a selected one.


Formally:



> 
> Given $A \in \mathbb{R}^{d \times n}$ and $0<k<n$, find a subset of
> column indices $S=\{i\_1,i\_2,\ldots,i\_k\}$, so that $$
>  \sum\_{j \notin S}{\min\_{r=1,\ldots,k}\angle(A\_j, A\_{i\_r})} $$ is minimized.
> 
> 
> 


If instead of taking the minimum angle between $A\_{i\_r}$ and a *single* column in $S$ we were looking at minimizing the projection of $A\_{i\_r}$ on $Span(S)$, it would have been a straightforward CSSP (Column Subset Selection Problem). As it is, it seems more of a coreset-like problem but I am failing to find a ready-made solution.


Even a decent approximation would be great.



Column subset selection with least angle optimization
You can solve this as a $k$-median (also known as $p$-median) problem. Each column is both a customer and a candidate facility location. Let $d\_{c,f}$ denote the cost of assigning customer $c$ to facility $f$. Let binary decision variable $x\_{c,f}$ indicate whether customer $c$ is assigned to facility $f$, and let binary decision variable $y\_f$ indicate whether a facility is built at location $f$. The problem is to minimize $\sum\_{c,f} d\_{c,f} x\_{c,f}$ subject to linear constraints
\begin{align}
\sum\_f x\_{c,f} &= 1 &&\text{for all $c$} \tag1 \\
x\_{c,f} &\le y\_f &&\text{for all $c$ and $f$} \tag2 \\
\sum\_f y\_f &= k \tag3 \\
\end{align}
Constraint $(1)$ assigns each customer to exactly one facility.
Constraint $(2)$ forces facility $f$ to be built if any customer is assigned to it.
Constraint $(3)$ selects exactly $k$ facilities to be built.


