Many kinds of high-dimensional data lie on a few flat, low-dimensional pieces. Tracked points on each rigidly moving object in a video span their own small subspace, and so do photos of one face under changing light. Subspace clustering is the task of recovering those pieces from unlabeled points. Its hardest cases are points near the place where two subspaces cross, the "crease." There a point can be equally well explained by either piece. Fast sequential methods make this worse: they find one subspace, remove its points, and repeat on what is left. One wrong call at the crease in the first step corrupts the data handed to every later step.
We propose to give a sequential subspace clustering method an explicit "I don't know" option. At each step, every point is sorted into one of three groups: clearly belongs to the subspace just found, clearly does not, or ambiguous. Ambiguous points are set aside. They are not used to estimate the current subspace, and they are not passed on to later steps. They return only at the end, once all subspaces have been estimated from clean cores. The thresholds come from a single abstain-versus-error cost ratio applied to an unsupervised posterior. They do not come from labels.
The claim is narrow and testable. Buffering helps in proportion to how much error the sequential pipeline propagates, so the gains should appear in three-subspace problems and at small angles between subspaces. They should be negligible where existing methods are already near zero error.
Where this sits
The mechanism is borrowed from regression. Imbalanced Mixed Linear Regression recovers several regression lines one at a time with robust reweighting. At each step it splits the data into good-fit, poor-fit and moderate-fit points, and withholds the moderate-fit points until a final joint refinement. In high-dimensional synthetic tests this handled up to 9% outliers, whereas simultaneous solvers failed above 2%. That work needs an explicit response variable, and its guarantees cover only two components. Our proposal moves the withholding idea to subspaces of arbitrary dimension that have no response variable.
The method we modify is Innovation Pursuit (iPursuit). It looks for a direction inside the data's span that is orthogonal to as many points as possible. Such a direction is unique to one subspace, so the points with a large projection onto it can be peeled off, and the process repeats. iPursuit scales well: it clustered 30,000 points in 10.6 seconds, while SSC and LRR did not finish within two hours. Its authors name error propagation from early boundary assignments as its main weakness. That weakness is exactly what this proposal targets.
Two other lines treat crease ambiguity without abstaining. The first relaxes hard labels. Discriminative Transformation Learning for Fuzzy Sparse Subspace Clustering (DTL-FSSC) uses fuzzy memberships to avoid a "domino effect" of early hard mistakes, at $O(n^3)$ cost. Under that scheme every ambiguous point keeps feeding fractional weight into estimation. The second relaxes the affinity matrix, the table of how strongly each pair of points is linked. Structured Sparse Subspace Clustering (S³C) couples learning that table with segmentation, but forces a hard partition at every iteration. Understanding Doubly Stochastic Clustering (DS-D) projects the table so that every row and every column sums to one, which zeroes leaked connections. Its guarantees assume points are spread uniformly within each subspace. None of these three isolates crease points from estimation.
The abstention logic comes from three-way decision theory. Risk Decision Making Based on Decision-theoretic Rough Set derives accept and reject thresholds from a cost matrix and shows that a single risk-attitude parameter can set them. We use that idea to answer the obvious objection that unsupervised clustering has no labels from which to compute costs.
The closest structural cousin is A Data-Centric Approach for Improving Ambiguous Labels (DC3). It routes ambiguous images to an overclustering head, but its ambiguity comes from annotator disagreement rather than geometry. It motivates the design; it does not supply the method.
Core mechanism
At extraction step $t$, iPursuit produces a direction $c_t$. Each remaining point $x_j$ then receives a scale-free membership score $s_j = |c_t^\top x_j| / \|x_j\|$. Clear non-members score near zero, clear members score high, and points near the crease fall in between.
We fit a two-component mixture to the scores $\{s_j\}$: a component concentrated near zero and a member component. This gives each point an unsupervised posterior $p_j$, the probability that it belongs to the subspace extracted at step $t$.
Thresholds then follow from decision-theoretic costs. Assume correct decisions cost 0, a wrong commitment costs 1, and abstaining costs $a < 1/2$. The standard three-way result then reduces to
$$ \alpha = 1 - a, \qquad \beta = a . $$
A point is a core member if $p_j \ge \alpha$, a non-member if $p_j \le \beta$, and buffered otherwise. The single knob $a$ plays the role of Li and Zhou's risk-attitude parameter. We will report results across a grid of $a$ values rather than tune it per dataset.
The pipeline proceeds in four stages. First, core members define subspace $t$. Second, non-members alone go forward to step $t+1$. Third, buffered points wait. Fourth, after all $K$ subspaces are estimated from their cores, each by principal component analysis, buffered points are assigned by smallest projection residual to each subspace. Optionally, the assignment is polished with a few rounds of joint residual reassignment over all points, mirroring Mix-IRLS's final stage.
The buffered set is also a useful output in its own right. It is an explicit, geometrically grounded list of crease points that a downstream user can inspect or defer.
Research program
The work has three parts.
Engineering. We will build the buffered variant of iPursuit and verify that it keeps iPursuit's near-linear runtime. The only additions are a one-dimensional mixture fit per step and a residual pass at the end.
Analysis. We will study a population model of two or three subspaces with a controlled smallest angle between them, the principal angle, and controlled noise. The aim is to characterize how much buffer mass is needed to keep the second-step innovation direction uncorrupted. We expect this to scale with the probability mass of points within noise distance of the intersection. That is the quantity Mix-IRLS controls in the regression case.
Measurement. Empirically, we will separate two quantities that existing evaluations merge. One is the final clustering error. The other is the error of subspaces extracted at steps two and later, where propagation shows up.
Baselines
The naive reference point is iPursuit exactly as published, with forced assignment at every step. On Hopkins 155 two-motion sequences it reports a median error of 0.27% (Innovation Pursuit). That leaves essentially no headroom, so two-motion Hopkins serves as a do-no-harm check, not a target. We found no reported result on Lacuna for iPursuit on Hopkins three-motion sequences or on Extended Yale B, so we will run it ourselves.
The strongest published competitors differ by benchmark:
- Hopkins 155, overall: Sparse subspace clustering (SSC) reports 1.24% total misclassification error.
- Hopkins 155, three motions: Spectral Curvature Clustering reports a 4.85% average error.
- Extended Yale B, 10 subjects: S³C reports 5.16% error, against 7.29% for SSC on that subset.
- Extended Yale B, 3 classes: DTL-FSSC reports 1.93%. This is a different subset, so the two Yale B figures are not directly comparable.
DS-D is the strongest "just clean the affinity matrix" competitor. Its reported result is synthetic (1.0 accuracy on a weighted block model), so we will run it on SSC affinities ourselves.
For fairness, all methods receive the true $K$ and the same preprocessing. Each method's hyperparameters get the same tuning budget, chosen on held-out synthetic sequences and then frozen before the real benchmarks. Published numbers will be quoted alongside our reruns, and we compare only within one evaluation protocol.
Beating the baselines means two things. On Hopkins three-motion sequences and Yale B, the buffered method should be below unbuffered iPursuit and at or below the published SCC and S³C figures. On synthetic data, its error at small principal angles should be lower than every baseline's.
Two ablations isolate the key ingredient. The first, keep-but-don't-use, excludes buffered points from estimating the current subspace but still passes them on to the next step. This tests whether removing them from the downstream pool is what matters. The second, buffer-without-posterior, sets the thresholds directly on raw scores, as quantiles. This tests whether the mixture-plus-cost step adds anything beyond a heuristic.
Why not just…?
Why not just run plain iPursuit and then reassign every point by residual to the final subspaces? This is the most serious threat, because reassignment fixes final labels cheaply. It cannot fix subspaces whose estimates were already distorted, because earlier mistakes changed the data they were computed from. Our synthetic study measures the angle between each estimated subspace and the truth at every step, with and without buffering, with the same final reassignment applied to both. If buffering does not reduce the error of subspaces extracted at step two and later, the proposal reduces to this baseline and we will say so.
Why not just use a stricter membership threshold in iPursuit? A stricter threshold leaves crease points in the pool for the next step. There they contaminate the next innovation search, which is the failure we target. The keep-but-don't-use ablation is exactly this variant and tests the claim directly.
Why not just use fuzzy memberships, as DTL-FSSC does? Fuzzy weights keep every ambiguous point in estimation throughout. Mix-IRLS's comparison of 9% versus 2% outlier tolerance suggests that withholding beats down-weighting in the sequential setting. DTL-FSSC also costs $O(n^3)$, which rules it out at the 30,000-point scale where iPursuit runs. It remains a strong competitor on small Yale B subsets, and we will compare against it there honestly.
Why not just apply DS-D to the SSC affinity matrix? DS-D is a global projection whose guarantees assume uniform sampling. Its required separation angle grows with subspace dimension. It also inherits SSC's cost, which fails at large $n$. Our synthetic sweep will include non-uniform densities concentrated near the crease. That is where we expect DS-D to degrade and buffering not to. If DS-D matches us there, the advantage of buffering is speed only.
Proposed experiments
Synthetic sweep. We generate two or three subspaces in ambient dimension 30–100, each of dimension 3–9. We sweep the smallest principal angle from near zero upward, the noise level, and the sampling density near the intersection, both uniform and crease-concentrated. We record final error, error of subspaces extracted at step two and later, buffer size, and runtime up to 30,000 points.
The decisive check is whether the gap between buffered and unbuffered iPursuit widens as the angle shrinks and as $K$ grows. If it stays flat, the propagation story is wrong.
Real benchmarks. We use Hopkins 155, split by two and three motions and by the checkerboard, traffic and other categories, and Extended Yale B on its standard subject subsets. Final error is reported against the baselines above.
Value of abstention. We plot selective error against coverage, sweeping $a$. For comparison, we rank points by the margin of their spectral embedding under SSC and S³C at matched coverage. If our buffered points carry no more error than an equal number of low-margin spectral points, the geometric buffer adds nothing as an uncertainty signal.
References
- Imbalanced Mixed Linear Regression
- Innovation Pursuit: A New Approach to the Subspace Clustering Problem
- Discriminative Transformation Learning for Fuzzy Sparse Subspace Clustering
- Structured Sparse Subspace Clustering: A unified optimization framework
- Understanding Doubly Stochastic Clustering
- Risk Decision Making Based on Decision-theoretic Rough Set: A Three-way View Decision Model
- A Data-Centric Approach for Improving Ambiguous Labels with Combined Semi-supervised Classification and Clustering
- Sparse subspace clustering
- Motion Segmentation by SCC on the Hopkins 155 Database