TL;DR
This paper tackles the tough problem of point-set registration when many points are "outliers" (mismatched or noisy). They introduce a novel approach using the Hadamard product of Gram matrices to identify the "inliers" (correctly matched points) before alignment. This leads to two new methods, one spectral and one based on row sums, that can robustly recover inlier correspondences even with vanishingly small inlier fractions, a significant improvement over existing methods.
What Problem Does This Paper Address?
Point-set registration is a fundamental task in fields like computer vision and robotics, aiming to find the transformation (like rotation and translation) that best aligns two sets of points. A major challenge arises when these point sets contain "outliers" – points that don't correspond to each other or are heavily corrupted by noise. Existing robust registration methods often struggle when the fraction of inliers (correctly matched points) becomes very small, a scenario that can occur in adversarial settings. The core problem this paper addresses is how to reliably identify these inliers before attempting the alignment, especially when the inlier proportion is not guaranteed to be a constant fraction of the total points.
Methods
The authors reframe the inlier recovery problem as a "planted clique" type problem. Their key innovation is to use the Hadamard product of Gram matrices derived from the two point sets. The Gram matrix captures pairwise similarities within a point set. By taking the Hadamard product of the Gram matrices from the two sets, they create a new matrix, $H$, where entries related to inlier pairs have distinct statistical properties compared to entries involving outliers.
This leads to two main algorithmic approaches:
- Eigenvector Matching: This method analyzes the leading eigenvector of the Gram-matrix overlap matrix $H$. The idea is that the structure of $H$ induced by inlier correspondences will be reflected in its dominant eigenvector, allowing for the separation of inlier and outlier indices. This method provides "weak recovery" guarantees.
- Row-Sum Matching: This approach leverages the row sums of the matrix $H$. By aggregating information across rows, this method offers stronger theoretical guarantees, achieving "exact recovery" under a broader range of dimensional scalings, including scenarios where the inlier fraction is vanishingly small.
The paper also discusses a parallel implementation strategy to improve scalability for large datasets.
Datasets
The paper uses the following datasets for evaluation:
- Brain Imaging Data: From the Human Connectome Project, specifically focusing on the left hemisphere with six features per vertex. This dataset is used to study statistical sensitivity to inlier proportion and computational scalability.
- Sky Dataset: RGB pixel values from sky images are used to examine sensitivity to noise under two perturbation scenarios: interchanged areas and permuted areas.
Key Insights and Ideas
- Gram-Matrix Overlap as a Novel Formulation: Reframing inlier recovery as analyzing the Hadamard product of Gram matrices is a fresh perspective that avoids direct optimization on the rotation group, simplifying the problem.
- Spectral vs. Row-Sum Guarantees: The eigenvector method offers a spectral approach with weaker guarantees, while the row-sum method provides stronger "exact recovery" guarantees, particularly in challenging low-inlier regimes. This highlights a trade-off between method complexity and theoretical robustness.
- Exact Recovery with Vanishing Inliers: The row-sum method's ability to achieve exact recovery even when the number of inliers is as small as $\sqrt{n}$ (up to log factors) is a significant theoretical breakthrough, pushing the boundaries of what's possible in robust registration.
- Dimensionality Flexibility: The row-sum method's theoretical guarantees hold over a much wider range of dimensional scalings (e.g., $\log n \le d \le n^2/\log n$) compared to the eigenvector method (which requires $d \approx n$), making it more broadly applicable.
- Practical Performance: Numerical experiments show that both methods, especially their k-means variants, perform well in practice, effectively identifying matched structures even under substantial corruption and noise.
Key Results
- Eigenvector Method: Achieves "weak recovery" when dimension $d$ and sample size $n$ are of the same order ($d \approx n$), provided the inlier fraction is a constant.
- Row-Sum Method: Achieves "exact recovery" under a broader range of dimensional scalings ($\log n \le d \le n^2/\log n$). Crucially, when $d \approx n$, it can achieve exact recovery even with vanishing inlier fractions, where the number of inliers is on the order of $\sqrt{n}$ (up to logarithmic factors).
- Parallelization: The proposed parallel computing strategy significantly reduces computation time (e.g., ~30% reduction with two splits) while maintaining stable classification accuracy.
- Noise Sensitivity: Both methods degrade gracefully as noise levels increase, with the row-sum method showing slightly more stability in complex perturbation settings.
- Case Study: Demonstrates the methods' ability to identify local differences in real images, correctly localizing added objects, though they can also pick up on illumination changes.
Limitations and Future Work
- Computational Cost: While parallelization helps, constructing the Gram matrices and the product matrix $H$ can still be computationally intensive for very large datasets.
- Theoretical Assumptions: The theoretical analysis relies on specific assumptions about the noise distribution (e.g., Gaussian for data points) and the structure of the inlier/outlier sets.
- Future Work: The authors mention discussing parallel implementation strategies and numerical experiments, implying that further exploration of scalability and practical performance is a natural extension. The paper also hints at potential extensions by discussing the implications of their findings for robust registration under substantial corruption.
Summary updated