Robust Tangent Space Estimation via Laplacian Eigenvector Gradient Orthogonalization

Technical Summary: Robust Tangent Space Estimation via LEGO

Problem Statement
Estimating the tangent spaces of a data manifold is a fundamental task in geometric data analysis, underpinning applications such as manifold learning, data denoising, boundary detection, and local intrinsic dimension estimation. The standard approach, Local Principal Component Analysis (LPCA), constructs a local covariance matrix from $k$-nearest neighbors to identify the tangent basis. However, LPCA suffers from a critical trade-off regarding neighborhood size: small neighborhoods are highly susceptible to noise corruption, while larger neighborhoods introduce bias due to the underlying curvature and reach of the manifold. Selecting an optimal neighborhood size typically requires prior knowledge of geometric and noise characteristics that are often unavailable, rendering the problem ill-posed in high-noise settings.

Methodology: LEGO
The authors propose LEGO (Laplacian Eigenvector Gradient Orthogonalization), a spectral method that leverages the global structure of the data to guide local tangent space estimation. Instead of relying solely on local neighborhoods, LEGO estimates the tangent space at each data point by orthogonalizing the gradients of low-frequency eigenvectors of the graph Laplacian constructed from the noisy data.

The algorithm proceeds as follows:

1. Graph Construction: A graph Laplacian $L$ is constructed from the noisy point cloud using kernel-based methods (e.g., random walk, self-tuned, or doubly stochastic kernels).
2. Gradient Estimation: The gradients of the first $m$ low-frequency eigenvectors ($\phi_1, \dots, \phi_m$) are estimated at each data point. To ensure local fidelity and numerical stability, these gradients are modeled as vectors in the span of the first $m_0$ eigenvectors ($m_0 \gg m$).
3. Regularization: A Tikhonov regularization term is applied to the gradient estimation process to prevent numerical blow-up in low-noise or rank-deficient settings. The regularization parameter $\eta_j$ is derived from the local neighborhood geometry, with a hyperparameter $\beta$ controlling the power of the distance penalty.
4. Orthogonalization: At each point $j$, the estimated gradient vectors $\hat{\nabla}\phi(X_j)$ are orthogonalized (via SVD) to extract the orthonormal basis $Q_j$ of the $d$-dimensional tangent space. If the intrinsic dimension $d$ is unknown, it is inferred from the singular values of the gradient matrix.

Theoretical Justifications
The paper provides two complementary theoretical frameworks to justify LEGO's robustness:

1. Differential Geometric Perspective:
   The authors model noisy data as samples from a tubular neighborhood $T_{\epsilon r}$ surrounding a clean $d$-dimensional submanifold $B$. They analyze the Neumann eigenfunctions of the Laplacian on this tube.

   • Key Finding: They establish bounds showing that the eigenvalue $\lambda$ of an eigenfunction scales as $\Omega(\epsilon^{-2} E^\perp_B(\phi))$ with respect to its "vertical energy" (gradient in the noise direction) and as $O(E_B(\phi))$ with respect to its "horizontal energy" (gradient along the manifold).
   • Implication: Eigenfunctions with significant gradients in the noise direction must have high eigenvalues. Conversely, low-frequency eigenfunctions have gradients concentrated in the horizontal (tangent) space, making their gradients robust estimators of the tangent bundle.

2. Random Matrix Theoretic Perspective:
   The authors analyze the stability of Laplacian eigenvectors under sub-Gaussian noise using an "information plus noise" model where the noise variance proxy $\epsilon$ scales as $O(1/\sqrt{n \log n})$.

   • Key Finding: They prove that the noisy graph Laplacian converges to the clean Laplacian in operator norm at a rate of $O(n^{-1/2})$. By the Davis-Kahan theorem, provided the eigengaps of the clean Laplacian do not decay too rapidly, the eigenvectors of the noisy Laplacian remain close to the clean ones.
   • Implication: Under these conditions, the horizontal components of the gradients estimated from noisy data converge to those of the clean data, ensuring the stability of the tangent space estimates.

Key Contributions

• Algorithmic Proposal: Introduction of LEGO, a spectral algorithm for robust tangent space estimation that avoids the neighborhood size trade-off inherent in LPCA.
• Theoretical Frameworks: Derivation of asymptotic scaling laws for eigenvector gradients under a tubular noise model and proof of eigenvector stability under sub-Gaussian noise perturbations.
• Hyperparameter Guidance: Theoretical derivation suggesting $\beta = 1/2$ as the optimal Tikhonov regularization parameter when noise characteristics are unknown.
• Empirical Validation: Comprehensive experiments demonstrating LEGO's superiority over LPCA in noisy settings.

Results
Numerical experiments on synthetic datasets (high-aspect-ratio Swiss roll, truncated torus) and real-world data (Puppets dataset) demonstrate that:

• Accuracy: LEGO yields tangent space estimates significantly more robust to noise than LPCA. The discrepancy between estimated and ground-truth tangent spaces remains low even as noise levels increase, whereas LPCA estimates degrade rapidly.
• Downstream Performance: The improved tangent space estimates lead to marked improvements in downstream tasks:
  • Manifold Learning: LEGO produces accurate 2D embeddings that preserve the intrinsic topology (e.g., revealing the toroidal structure of the Puppets dataset), while LPCA-based embeddings collapse or become non-injective.
  • Boundary Detection: Boundary points detected using LEGO align closely with ground truth, whereas LPCA fails to identify boundaries accurately in noisy conditions.
  • Intrinsic Dimension Estimation: LEGO correctly concentrates functional variance in the true intrinsic dimensions, whereas LPCA spuriously allocates variance to noise directions.

Significance
The paper claims that LEGO offers a principled alternative to local methods by utilizing global spectral information to filter out noise. By demonstrating that low-frequency graph Laplacian eigenvectors naturally align with the tangent bundle of the underlying manifold while suppressing noise components, the authors provide a robust solution to the neighborhood size selection problem. This approach enables accurate geometric analysis in high-noise regimes where standard local methods fail, facilitating more reliable manifold learning and dimensionality reduction.