Manifold Dimension Estimation via Local Graph Structure

Technical Summary: Manifold Dimension Estimation via Local Graph Structure

Problem Statement
Estimating the intrinsic dimension $d$ of a manifold embedded in a high-dimensional ambient space $\mathbb{R}^p$ is a fundamental challenge in nonlinear dimensionality reduction. While many existing estimators (e.g., Local PCA, DanCo, TwoNN) rely on the "flatness assumption"—approximating local neighborhoods as $d$-dimensional linear subspaces—this approach struggles when manifolds exhibit significant curvature or are nonlinearly embedded. Recent methods like Curvature-Adjusted PCA (CA-PCA) attempt to address this by explicitly correcting eigenstructures for curvature, yet they often suffer from overestimation in high-dimensional ambient spaces or computational instability. The authors identify a gap in methods that can robustly model local curvature without relying on unstable direct curvature estimation or eigenvalue gap detection.

Methodology
The authors propose a new framework that reframes manifold dimension estimation as a regression problem on local PCA coordinates. Instead of assuming local flatness or explicitly estimating curvature tensors, the method models the local neighborhood of a point $x_k$ as a graph of a smooth function $g: \mathbb{R}^d \to \mathbb{R}^{p-d}$.

1. Local Graph Representation: For a point $x_k$ and its $K$-nearest neighbors, the authors perform PCA to establish a local coordinate system aligned with the estimated tangent space. The first $d$ coordinates represent the tangent space, while the remaining $p-d$ coordinates represent the normal space.
2. Regression Formulation: The framework posits that the normal coordinates can be expressed as a function of the tangent coordinates. Since the first-order Taylor expansion of this function is zero (by definition of the tangent space), the authors utilize second-order (quadratic) terms to capture local curvature.
3. Candidate Dimension Probing: The algorithm iterates through candidate dimensions $j$ (from 1 to $p-1$). For each $j$, it treats the first $j$ PCA coordinates as inputs and the $(j+1)$-th coordinate as the output, fitting a quadratic regression model.
4. Two Estimators:
   • Quadratic Embedding (QE): Uses Ordinary Least Squares (OLS) to fit the quadratic model. It evaluates the goodness-of-fit using the $F$-statistic and adjusted $R^2$. The estimated dimension is the smallest $j$ where the model fit becomes statistically significant (p-value < 1%) and remains significant for all higher dimensions.
   • Total Least Squares (TLS): Uses Total Least Squares to account for errors in both input and output variables. Instead of $F$-statistics, it evaluates the relative drop in total TLS error ($\eta_j$) between consecutive dimensions. The estimated dimension corresponds to the peak relative drop.

Key Contributions

• Regression-Based Framework: The paper introduces a novel perspective that casts dimension estimation as a recursive regression problem. This replaces unstable local geometric estimation (like direct curvature calculation) with a statistically aggregated fitting procedure, offering greater robustness to sampling sparsity and noise.
• Curvature-Aware Modeling: By employing quadratic models, the method explicitly captures the manifold's curvature without requiring explicit curvature estimation or eigenvalue correction, thereby mitigating the overestimation issues common in PCA-based methods.
• Robustness to Noise and Nonlinearity: The framework naturally accommodates noise and is designed to perform well on manifolds with complex, nonlinear embeddings where flatness assumptions fail.
• Practical Implementation: The authors provide two concrete estimators (QE and TLS) with detailed algorithms, including heuristics for limiting the search space ($p_{max}$) based on neighborhood size to ensure computational feasibility.

Experimental Results
The authors evaluated QE and TLS on 18 synthetic manifolds (including spheres, deformed spheres, and Gaussian surfaces) and 6 real-world datasets (ISOMAP, MNIST, ISOLET, Fashion MNIST, Frey Face, Gas Sensor Array Drift).

• Synthetic Data: QE and TLS demonstrated competitive or superior performance compared to state-of-the-art methods (Local PCA, CA-PCA, DanCo, TwoNN, MADA, etc.), particularly in small-sample regimes and on nonlinearly embedded manifolds (e.g., deformed spheres). They effectively mitigated the overestimation observed in CA-PCA and Local PCA when the ambient dimension $p$ significantly exceeds the intrinsic dimension $d$.
• Noise Robustness: In the presence of Gaussian, uniform, and Laplace noise, the proposed methods maintained robust performance, outperforming many flatness-based estimators whose accuracy degraded significantly.
• Real-World Data: On real-world datasets, the estimators produced results consistent with consensus ranges (e.g., estimating ISOMAP $\approx 3$, MNIST $\approx 8-11$). Notably, they avoided the severe overestimation seen in Local PCA and CA-PCA on datasets with high ambient dimensions.
• Limitations Observed: The methods showed reduced performance on "trivial" manifolds with zero curvature (e.g., hyperballs), where the quadratic model is a misspecification. Additionally, TLS is bounded below by 2 due to its reliance on relative error drops between dimensions.

Significance and Claims
The paper claims that by shifting the paradigm from geometric approximation to statistical regression, the proposed framework achieves improved robustness and accuracy, particularly in challenging regimes involving small sample sizes and complex curvature. The authors assert that their methods offer a compelling alternative to existing top-performing estimators, effectively addressing the limitations of both flatness-based approaches and eigenvalue-based curvature corrections. They conclude that while the current quadratic formulation is effective, future work could explore more expressive models if reliable diagnostic tools for sample statistics are developed. The work is presented as a significant step toward resolving the persistent challenges in manifold dimension estimation, though the authors remain modest regarding the need for further refinement in evaluation criteria (specifically for TLS) and the handling of noise in tangent space estimation.