Clustering data for compression with PCA
(Not really an answer, more like a suggestion)
Since it's almost surely NP-hard, we need some heuristics. The idea is, for each point, to build the cluster it's contained in:
def clustering(P):  # P is the set of points
    for each p in P:
        build a somewhat-optimal cluster C containing p
        remove C from P

Now, for each point we will build a cluster, one dimension at a time. We will build vectors $(v_1, \ldots, v_k)$, until the objective doesn't improve:
def build_cluster(p, P, t):  # t is a projection distance threshold
    S = ()  # current span
    for k = 1, 2, ...:  # cluster dimension
        sample m vectors v_1, ..., v_m
        for each v_i:
            compute the number of points in P within a distance t to p + span(S, v_i)
        select the best such v_i
        if adding v_i to S is not beneficial:
            break
        S = union(S, v_i)

Now, there is a lot of engineering which can be done, except for defining stop conditions. E.g. we can sample vectors, and then iteratively improve them (minimizing the loss, I.e. the distance to the span from vertices within distance t) (and we can also decrease t in the process of improvement).
Also, maybe we should do something better than sampling random vectors since we are unlikely to hit the right one. We may try to compute some candidates based on our data.
Hope it helps.