Standard clustering algorithms rely heavily on Euclidean distance. This makes intuitive sense when data forms compact, spherical blobs. However, in many real-world applications—such as motion segmentation, computer vision, and high-fidelity physical simulations—data points do not cluster in blobs. Instead, they lie on low-dimensional linear subspaces or within directional cones that intersect near the origin.
In these scenarios, Euclidean distance fails fundamentally. Two data points can be spatially very close to each other near the intersection of two distinct subspaces, yet belong to entirely different categories. Conversely, two points can be far apart in space but lie along the exact same directional vector. To capture the true underlying structure of such data, we must prioritize orientation over magnitude.
By replacing Euclidean metrics with angular affinity measures—such as cosine similarity, sine distance, or the angles between principal directions—we can partition data based on its geometric subspace rather than its spatial proximity.
The Geometry of Subspaces and Cones
To understand why angular affinity works, consider the task of grouping data points that lie on different lines intersecting at the origin.
Subspace A
\ / Subspace B
\ /
\ / <-- Intersecting region (Euclidean distance fails)
X
/ \
/ \
/ \
Near the intersection point (the origin), a point on Subspace A is closer in Euclidean distance to a point on Subspace B than it is to a distant point on its own subspace. A Euclidean clustering algorithm will mistakenly group these intersecting points together.
If we instead measure the angle between the vectors, the distance between any two points on Subspace A is zero (or very small), while the distance between Subspace A and Subspace B remains large, regardless of how close they get to the origin.
This intuition extends naturally to higher-dimensional spaces and more complex matrix factorization problems:
- Matrix Decomposition: In Nonnegative Matrix Factorization (NMF), data can be modeled as clusters residing within circular cones. Tan et al. and Liu et al. leveraged this by partitioning data columns based on their angular proximity to central feature directions. This greedy angular clustering step allows complex global optimization problems to be broken down into localized, independent sub-problems, providing faster initialization and tighter error bounds.
- Tree-Based Search: When performing a Maximum Inner-Product Search (MIPS), Ram et al. demonstrated that grouping vectors into "cone trees" based on directional similarity provides a much tighter pruning criterion than standard Euclidean bounding boxes. This allows search algorithms to safely skip entire branches of irrelevant data.
Enhancing Subspace Clustering via Principal Directions
In subspace clustering, the goal is to find an affinity matrix that connects data points belonging to the same subspace while leaving points from different subspaces disconnected. A common strategy is to solve for a low-rank representation of the data and use the resulting coefficient matrix to build a graph. However, raw coefficients are often noisy and sensitive to data corruption.
To build cleaner, more robust affinity graphs, researchers look at the angular information of principal directions derived from these representation matrices.
Raw Data -> Low-Rank Representation -> SVD / Principal Directions -> Angular Affinity Matrix -> Spectral Clustering
Instead of using the raw coefficients directly, the authors of several papers propose performing a Singular Value Decomposition (SVD) on the representation matrix to extract its principal directions. Chen et al. and Chen et al. showed that computing the angles between these principal directions filters out magnitude noise and yields highly discriminative affinity matrices.
Because the geometric orientation of the learned features is far more stable than their raw values, this approach provides exceptional resilience to noise and outliers. For instance, Kang et al. combined this angular principal-direction mapping with a LogDet rank minimization technique, demonstrating that the resulting affinity graph preserves the true geometric relationships of the underlying subspaces even when the data is heavily corrupted.
For direct motion segmentation without explicit low-rank optimization, Lauer et al. showed that constructing an affinity matrix using the cosine of the angle between raw feature vectors—sharpened by an exponent to amplify the contrast between different subspaces—outperforms Euclidean alternatives while drastically reducing computational overhead.
Physics-Informed Model Reduction
The power of angular partitioning becomes uniquely apparent in computational physics. When engineers simulate complex phenomena like fluid dynamics or structural thermal stress, they rely on Model Order Reduction (MOR) to compress high-fidelity simulations into low-dimensional "reduced-order bases."
Standard reduction methods struggle when a simulation spans highly non-linear regimes; a single global basis cannot capture the entire behavior. The solution is to cluster simulation snapshots and build a dictionary of local bases. But how should we cluster these snapshots?
Simulation Snapshots -> Measure Subspace Angles (Sine Distance) -> Cluster Similar Orientations -> Local Bases
If you cluster snapshots using Euclidean distance, you group them by their instantaneous magnitude or physical scale. This is counterproductive because a physical wave or stress state retains the same underlying geometric structure whether its amplitude is small or large.
To solve this, Daniel et al. and Casenave introduced clustering based on sine dissimilarity. The sine of the angle between two subspaces directly quantifies how poorly one subspace can represent the data of another. By partitioning the solution space using sine distance, the authors ensure that all snapshots assigned to a given cluster share the same geometric orientation. As a result, every point in that cluster can be accurately represented by the exact same local linear basis, unlocking massive speedups for large-scale industrial physics applications.
Scaling Up with Cosine Trees
While angular affinity offers superior precision, computing pairwise angles across massive datasets can be computationally expensive. To scale these geometric insights, algorithms utilize hierarchical spatial partitioning trees built on angular metrics.
Holmes et al. developed the "cosine tree," a data structure that recursively splits data points based on their cosine similarity to a chosen pivot vector. This mechanism automatically groups vectors pointing in similar directions.
By representing an entire cluster of directionally aligned rows by a single centroid, the algorithm rapidly identifies and eliminates redundant data directions. This allows for fast, approximate SVD calculations that achieve orders-of-magnitude speedups while maintaining strict, user-defined error bounds.
Key Foundational Work
Spectral clustering of linear subspaces for motion segmentation (2009) — contributed 2 concept elements to this direction.
QUIC-SVD: Fast SVD Using Cosine Trees (2008) — contributed 2 concept elements to this direction.