🤖 machine learning

Fitting Unknown Number of Hyperplanes with Manifold Optimization

This paper proposes a novel two-stage manifold optimization framework that reformulates the problem of fitting an unknown number of hyperplanes as an unsupervised learning task on a unit sphere, utilizing a Riemannian Expectation-Maximization process with heavy-tailed kernels and a projected density estimation initialization to achieve robust, geometrically consistent solutions that outperform state-of-the-art methods.

Original authors: Zhiqin Cheng, Yu Zhan, Mingjin Zhang, Lingbo Liu, Liang Lin

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhiqin Cheng, Yu Zhan, Mingjin Zhang, Lingbo Liu, Liang Lin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are standing in a large, foggy room filled with thousands of floating marbles. Some of these marbles are floating in neat, flat sheets (like invisible walls), while others are just scattered randomly. Your job is to figure out: How many invisible walls are there, and exactly where are they?

This is the problem the paper tackles: fitting an unknown number of flat surfaces (hyperplanes) to a messy cloud of data points.

Here is a simple breakdown of their solution, using everyday analogies.

The Problem: A Messy Puzzle

Usually, when computers try to sort things, they look for "clusters" (like grouping red marbles separate from blue ones). But here, the "clusters" are flat sheets that can cross each other, like the floor and a wall intersecting.

The Trap: If you try to solve this with standard math, the computer gets stuck in a "local optimum." Imagine you are trying to find the lowest point in a mountain range. If you just walk downhill, you might get stuck in a small valley and think you've reached the bottom, not realizing there is a much deeper valley nearby.
The Difficulty: The math involved is "non-convex" (bumpy and tricky) and "non-differentiable" (it has sharp corners where standard calculus breaks down). It's like trying to roll a ball down a staircase; the ball doesn't roll smoothly, it gets stuck on the edges.

The Solution: A Two-Stage "Manifold" Strategy

The authors propose a new way to look at the problem using something called Manifold Optimization. Think of this as changing the rules of the game so the computer can roll smoothly again.

1. The Map Change (Manifold Optimization)

Instead of trying to describe a flat wall using standard coordinates (which creates those tricky "sharp corners" in the math), they describe the walls using unit normal vectors.

The Analogy: Imagine every flat wall has a "compass needle" pointing straight out from it. Instead of trying to calculate the wall's position in a messy grid, they only care about the direction the needle is pointing.
The Trick: They force these compass needles to live on the surface of a sphere (a "manifold"). This turns a bumpy, broken math problem into a smooth, rolling one. Now, the computer can "roll downhill" (gradient descent) without getting stuck on sharp edges.

2. The Two-Stage Algorithm

Once they have this smooth map, they use a two-step process to find the walls:

Phase I: The "Soft" Guess (Riemannian EM)

What happens: The computer doesn't decide immediately which marble belongs to which wall. Instead, it assigns a "probability" or a "soft weight."
The Analogy: Imagine the marbles are wearing fuzzy coats. A marble near the intersection of two walls might be 60% "Wall A" and 40% "Wall B."
The Secret Weapon: They use a special "heavy-tailed" kernel (a mathematical filter). Think of this as a magnet that is very gentle on marbles far away but very strict on marbles that are right on the line. This helps the computer ignore noise and figure out the general shape of the walls without getting confused by the messy intersections.

Phase II: The "Hard" Decision

What happens: Once the computer has a good "soft" guess, it makes a final, hard decision.
The Analogy: The fuzzy coats are ripped off. Now, every marble is strictly assigned to one wall. The computer then fine-tunes the position of the walls to fit these specific marbles perfectly.
The Result: This gives a precise, geometrically perfect answer that strictly follows the rules of the wall's shape.

Finding the Starting Point (Initialization)

A big problem with these puzzles is: How many walls are there to begin with? The computer doesn't know if it's looking for 3 walls or 10.

The Strategy: The authors created a "density estimation" trick. They scan the room looking for areas where marbles are packed tightly together in a flat pattern.
The Analogy: It's like a detective scanning a crime scene. Instead of guessing randomly, they look for the most obvious "clumps" of evidence first, set up a temporary wall there, remove those marbles, and then look for the next clump. This gives them a great starting lineup of walls to refine later.

The Results

When they tested this method against other famous algorithms (like K-Means or RANSAC):

Accuracy: Their method found the walls with much higher precision (lower error).
Robustness: It handled the messy intersections and noise much better than others.
Speed: It was efficient enough to handle large datasets without getting stuck in local "valleys."

Summary

In short, the authors took a messy, broken math problem (fitting unknown flat surfaces to data) and:

Smoothed it out by changing how they represented the walls (using compass needles on a sphere).
Solved it in two steps: First, a fuzzy, flexible guess to avoid getting stuck; second, a sharp, precise final adjustment.
Found a smart starting point by looking for dense clusters of data first.

The result is a system that can look at a chaotic cloud of points and accurately reconstruct the invisible flat surfaces hidden inside, even when it doesn't know how many surfaces there are to begin with.

Technical Summary: Fitting Unknown Number of Hyperplanes with Manifold Optimization

Problem Definition
The paper addresses the fundamental challenge of fitting an unknown number of hyperplanes to a set of data points in a $d$ -dimensional space. This problem is characterized as non-convex, non-differentiable, and having an unknown model order (the number of hyperplanes $m$ ). Existing approaches, including traditional clustering algorithms (e.g., K-Means, DBSCAN) and RANSAC-based variants, often struggle with local optima, lack geometric consistency at intersection points, or fail to handle the dynamic nature of input/output dimensions inherent in unsupervised settings. Furthermore, deep learning methods face difficulties due to non-differentiable objectives and the need for fixed input/output dimensions.

Methodology
The authors propose a novel framework based on Manifold Optimization to overcome these limitations. The core methodology involves three main components:

Problem Reformulation and Manifold Representation:
- The problem is reformulated as an unsupervised clustering task where the cluster centers are hyperplanes.
- To handle the non-convex constraint $\|n\|^2 = 1$ (where $n$ is the unit normal vector of a hyperplane), the authors define the search space as the unit sphere manifold $S^{dim-1}$ .
- By representing hyperplanes via their unit normal vectors $n$ and distance parameters $d$ , the distance metric between points and hyperplanes is linearized, making gradient-based optimization tractable.
Two-Stage Manifold Optimization Algorithm:
The solution employs a two-phase iterative process (Algorithm 1):
- Phase I: Soft Optimization (Riemannian EM): This stage uses a Riemannian Expectation-Maximization (EM) framework. Instead of standard Gaussian assumptions, a heavy-tailed kernel (specifically, inverse-square distance $1/D^2$ ) is used to model posterior probabilities. This allows for robust estimation of point-to-hyperplane assignments, effectively resolving ambiguities where data points lie near intersecting hyperplanes. The optimization is performed on the manifold using retraction operations to ensure updates remain on the unit sphere.
- Phase II: Hard Refinement: Once the soft probabilistic weights converge, they degenerate into hard assignments (each point belongs to exactly one cluster). An unweighted manifold optimization is then performed within each cluster to refine the geometric parameters ( $n, d$ ) to a precise local optimum that strictly satisfies the geometric definition.
Initialization Strategy:
To address the unknown model order and avoid poor local optima, the authors introduce a projected density estimation strategy (Algorithm 3). This method incrementally selects initial hyperplanes by sampling normal vectors on the manifold (using trigonometric parameterization to reduce the state space) and identifying dense regions of points. This strategy aims to facilitate global convergence by significantly reducing the feature description space and search complexity.

Key Contributions
The paper claims the following contributions:

Reformulation: Transforming the non-differentiable hyperplane fitting problem into a clustering framework to eliminate non-differentiability.
Manifold Representation: Using unit normal vectors on the sphere manifold $S^{dim-1}$ to reduce the state space and linearize distance calculations.
Algorithm Design: Proposing a Two-Stage Manifold Optimization algorithm that combines Riemannian EM (for robustness and ambiguity resolution) with Hard Refinement (for geometric precision).
Initialization: Developing a method to determine potential hyperplanes and generate initial values, aiding in the search for global optima.

Experimental Results
Extensive experiments were conducted on synthetic 2D and 3D datasets with varying numbers of hyperplanes and noise levels.

Performance: The proposed "Full Pipeline" (Initialization + Phase I + Phase II) consistently outperformed state-of-the-art baselines, including Agglomerative Clustering, K-Means, DBSCAN, GMM, RANSAC, PARSAC, and SupeRANSAC.
Metrics: The method achieved superior results in Total Cost (aggregate Euclidean distance) and Hyperplane Error (parameter estimation accuracy). Notably, while some RANSAC variants performed well when the number of hyperplanes was known, they degraded significantly in the unsupervised setting (overestimating the number of hyperplanes). The proposed method successfully recovered the model order with high accuracy.
Ablation Studies: Experiments confirmed that the combination of Soft Optimization and Hard Refinement is critical; using either stage alone resulted in inferior performance. The proposed initialization strategy also proved effective compared to random sampling.
Scalability: Scaling tests indicated that the method maintains global optimality as the number of points increases, with Hyperplane Error decreasing as data density improves.

Significance and Claims
The paper positions this work as a solution to a long-standing challenge in machine learning and geometry: fitting an unknown number of hyperplanes without relying on convex relaxations or expensive global search heuristics. The authors claim that by leveraging the geometric structure of the data through manifold optimization, their method effectively handles non-convex constraints and non-differentiable objectives. The significance lies in providing a geometrically consistent, robust, and accurate framework that outperforms existing clustering and RANSAC-based approaches, particularly in scenarios involving intersecting hyperplanes and unknown model orders. The authors acknowledge limitations regarding the difficulty of distinguishing hyperplanes when their feature vectors are extremely close, but assert that their method represents a significant advancement over current baselines.