Neighbor-embedding methods such as t-SNE and UMAP turn a point cloud into a 2D or 3D picture by non-convex gradient descent. Like most non-convex solvers, they depend heavily on where they start. A common starting point is a spectral layout: the bottom eigenvectors of a graph Laplacian, a matrix built from the nearest-neighbor graph whose low-energy eigenvectors vary smoothly over the data. This start is a known weak point for one class of data. If the data lie on a long, thin manifold, such as a ribbon 20 times longer than it is wide, the bottom eigenvectors are mostly repeated "harmonics" of the long direction, like higher notes on one string. The width direction does not appear among them. The spectral start then folds the ribbon into a one-dimensional arch and contains no information about its width.
We propose to test whether this collapsed start traps the downstream optimizer even when that optimizer's own objective prefers an unfolded ribbon. We also propose a cheap fix that removes harmonics inside the eigensolver. On a rectangle, the $k$-th harmonic along the long axis is exactly the Chebyshev polynomial $T_k$ of the first eigenvector, since $\cos(k\theta) = T_k(\cos\theta)$. Requiring each new coordinate to be orthogonal to smooth functions of the coordinates already found therefore removes the harmonics. The width mode becomes the lowest remaining eigenvector, and the cost is $d$ small constrained eigensolves instead of computing a pool of eigenvectors that grows with the aspect ratio.
Core Claim
The proposal makes two claims, and either can fail independently. The first is diagnostic. On high-aspect-ratio manifolds, t-SNE-like objectives started from the standard spectral layout converge to local minima in which the ribbon is crumpled. Along such an embedding, the minor axis flips orientation at "domain walls," and repairing these flips would require coordinated global motion that local gradient steps cannot produce. Started from a correct layout, the same objective reaches a lower loss.
If this holds, the failure is caused by the starting point, not by the objective. That distinguishes it from the collapse analyzed in Manifold Learning: The Price of Normalization, which shows that methods requiring every output axis to have equal variance (Laplacian Eigenmaps, Diffusion Maps, and related methods) prefer the collapsed solution even with infinite data once the aspect ratio exceeds 2. t-SNE has no such variance constraint, so any collapse it shows must be inherited from where it starts.
The second claim is constructive. A functionally deflated eigensolver produces warm starts that avoid this trap. Its cost depends on the target dimension $d$ and the size of the deflation basis, not on the aspect ratio.
Relation to Prior Work
Three papers supply the motivating mechanism and the strongest existing remedies. All three filter eigenvectors after the eigensolver has run.
Minimally Redundant Laplacian Eigenmaps identifies Laplacian eigenvectors as Fourier-like harmonics. It computes a large pool of candidates and discards any candidate that nearest-neighbor regression can predict from the coordinates already kept. Its authors name moving this test into the solver as future work, and that is what we do: we turn "predictable from selected coordinates" into a linear constraint on the eigenproblem.
Selecting the independent coordinates of manifolds with large aspect ratios shows that collapse appears as a drop in the rank of the embedding's local metric. Its method, IES, chooses a subset of precomputed eigenvectors by trading off how much local volume they preserve against how smooth they are. We reuse its local-metric estimator, RMETRIC, as an evaluation metric rather than as a selection rule.
Product Manifold Learning with Independent Coordinate Selection applies greedy volume-based selection before factoring product manifolds, and it supplies the 1×7 strip benchmark.
Two limits are shared by all three methods. First, if the minor-axis mode sits beyond the computed pool, which happens once the aspect ratio exceeds the pool size, no filter can recover it. Second, none of them asks what happens after the eigenvectors are handed to an iterative optimizer.
The initialization side supplies the lens. Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity shows that the PCA objective is locally strongly convex only within a radius proportional to the eigenvalue gap, and that a power-iteration warm start places the solver inside that region. Finding Low-rank Solutions to Matrix Problems, Efficiently and Provably similarly makes a spectral start the entry point to its linear convergence guarantee.
These results treat the spectral start as reliably good. Our diagnostic claim is the counterpoint for manifold data: on high-aspect-ratio manifolds the spectral start is a confident, well-converged start toward the wrong structure.
From t-SNE to UMAP with contrastive learning frames t-SNE and UMAP as points on one contrastive spectrum, Neg-t-SNE, controlled by a normalization constant. It reports that settings with a low normalization constant rely on early exaggeration, a heuristic that temporarily strengthens attraction between neighbors early in training, to avoid fragmented local minima. We use that spectrum as the set of downstream objectives. Their observation is independent evidence that these losses have basins sensitive to initialization, though the paper does not study aspect ratio.
Understanding Dimensional Collapse in Contrastive Self-supervised Learning studies a related but distinct collapse in deep representation learning, where it is driven by the training dynamics of the network. We treat it as out of scope.
Research Program
The deflated eigensolver works as follows. Let $L$ be the graph Laplacian, $D$ the diagonal degree matrix, and $Y_{1:j-1}$ the coordinates found so far. Let $\Phi_j \in \mathbb{R}^{n \times m}$ hold $m$ smooth functions of those coordinates evaluated at the $n$ data points, for example Chebyshev polynomials or low-frequency random Fourier features, plus a constant column. Coordinate $j$ is then the solution of
$$\min_{y \in \mathbb{R}^n} \; y^\top L y \quad \text{subject to} \quad y^\top D y = 1,\;\; \Phi_j^\top D y = 0.$$
This is an ordinary generalized eigenproblem on the $D$-orthogonal complement of $\Phi_j$. We solve it with a projected block eigensolver (LOBPCG), started from one power-iteration step in the spirit of the PCA warm-start analysis. Each iteration costs one sparse multiplication by $L$ plus an $O(nm)$ projection.
On an exact rectangle, the Chebyshev basis removes every long-axis harmonic up to degree $m$. The true width mode is unaffected, because at fixed position along the long axis it still varies across the width. Its best approximation by functions of the first coordinate is therefore its average across the width, which is near zero.
On curved or noisy manifolds, the cancellation is only approximate. The program asks how much it degrades, measured as the leakage of the target mode into the span of $\Phi_j$, as a function of noise level, curvature, and $m$. The basis size $m$ is the method's single knob: too small leaves harmonics in place, and too large starts to remove real structure. We will derive a choice of $m$ tied to the target aspect ratio and test it against cross-validated predictability.
On the analysis side, we will measure the relative eigengap the solver faces with and without deflation, and test whether iteration counts follow it. We expect deflation to shrink the subspace that must be computed from roughly the aspect ratio down to $d$. We do not expect it to enlarge the gap to the nearest mixed mode, which is the product of the first long-axis mode and the width mode. That gap remains of order $1/L_1^2$, where $L_1$ is the long-axis length. We state this limit now rather than discover it later.
On the downstream side, we will take the resulting layout, rescale it as t-SNE and UMAP initializations conventionally are, and run Neg-t-SNE at several normalization constants with and without early exaggeration.
Baselines
The naive reference point is the spectral layout of the bottom $d$ nontrivial eigenvectors, together with random initialization. This is the configuration whose trap we claim exists. Each will be run through identical downstream optimizers with the same iteration budget, learning-rate schedule, and exaggeration schedule.
The strongest competitors are post-hoc selection methods used as initializers: IES from Selecting the independent coordinates of manifolds with large aspect ratios and MR-LEM from Minimally Redundant Laplacian Eigenmaps. Both target the same harmonic problem and are known to recover full rank when their candidate pool is large enough. The only reported number in the file comes from the MR-LEM paper on Small NORB: 13.8% nearest-neighbor classification error for MR-LEM versus 15.6% for standard Laplacian Eigenmaps, 16.6% for PCA, and 18.4% for raw pixels. On the synthetic strips, tori, and three-torus, no reported result was found on Lacuna for any numerical metric. The papers report only qualitative full-rank recovery.
For fairness, IES and MR-LEM will receive the same total eigensolver wall-clock as our method in one condition and an unlimited pool in another. Beating them means matching their rank and coordinate-recovery quality with fewer eigensolver matrix multiplications. It also means outperforming them outright in the matched-compute condition once the aspect ratio exceeds the pool size they can afford. On Small NORB, beating MR-LEM means achieving at or below 13.8% error at lower cost.
PCA initialization and landmark Isomap initialization serve as non-spectral starts. Isomap avoids harmonic collapse according to Manifold Learning: The Price of Normalization.
The key ablation replaces the smooth-function basis $\Phi_j$ with only the linear coordinates $Y_{1:j-1}$, which is ordinary orthogonal deflation and therefore just standard Laplacian Eigenmaps. A second ablation sweeps $m$. Together these isolate whether the nonlinear constraint is what does the work.
Why not just…?
Why not just initialize with PCA? For a flat ribbon embedded linearly, PCA recovers both axes exactly and would match our method, so flat strips cannot discriminate between the two. The comparison is decided on curved ribbons, such as rolled strips and the high-aspect-ratio torus. There the leading principal directions follow how the manifold sits in the ambient space rather than its intrinsic axes. If PCA initialization yields equally good downstream embeddings on those curved benchmarks, the constructive claim fails and we will report it.
Why not just use IES or MR-LEM coordinates as the warm start? This is the real threat. When the candidate pool exceeds the aspect ratio, we expect both to produce warm starts as good as ours. The proposal's advantage is cost and robustness to truncating the pool, not quality, and the matched-compute experiment settles this. If post-hoc selection with a pool of size proportional to the aspect ratio is cheap enough at the dataset sizes we test, the constructive half of the contribution reduces to an engineering speedup and should be described that way.
Why not just use Isomap, or rely on early exaggeration and longer runs? Isomap's all-pairs shortest paths and dense eigendecomposition limit it to landmark approximations at scale, and a single shortcut edge between distant parts of the manifold distorts all of its distances. We include landmark Isomap so that its quality-versus-cost tradeoff is measured rather than assumed. Early exaggeration is a direct test of the diagnostic claim. If heavy exaggeration or long runs reliably unfold a collapsed spectral start, the trap does not exist and the diagnostic half is falsified. We will sweep the strength and duration of exaggeration to find out.
Proposed Experiments
The synthetic suite consists of flat strips with aspect ratios from 2 to 200. It also includes rolled versions of those strips, the 1×7 strip from the product-manifold paper, the high-aspect-ratio torus and three-torus benchmarks from the IES paper, and Swiss-roll ribbons. Each is tested with and without additive noise, because noise triggers collapse even in methods that tolerate aspect ratio on clean data.
The metrics are the following:
- Procrustes error against the true intrinsic coordinates.
- The fraction of points at which the local metric estimated by RMETRIC is full rank.
- A count of domain walls, defined as sign changes in the local orientation of the minor axis along the long axis.
- The final value of the downstream objective.
- The number of Laplacian matrix multiplications.
The real-data suite consists of Small NORB, scored by nearest-neighbor classification error and compared against the reported MR-LEM figure, and the similarity-transformed faces, scored by the separation of translation from rotation. It also includes SDSS spectra, checked for whether the method selects coordinates equivalent to the IES choice of {1, 3} without being shown candidate 2.
The decisive check for the diagnostic claim is a single comparison. For each aspect ratio, run the identical t-SNE objective from the spectral start and from the ground-truth layout, and compare final losses and domain-wall counts. A consistently higher loss together with persistent domain walls from the spectral start, rising with aspect ratio, shows that the start traps the optimizer while the objective itself is not at fault. Equal losses would show that the objective, not the start, prefers collapse.
The decisive check for the constructive claim is the matched-compute curve. Plot recovery error against aspect ratio at a fixed eigensolver budget. Our method should stay flat, while spectral and post-hoc-selection starts should degrade once the minor-axis mode falls outside the eigenvectors they can afford to compute.
References
- Manifold Learning: The Price of Normalization
- Minimally Redundant Laplacian Eigenmaps
- Selecting the independent coordinates of manifolds with large aspect ratios
- Product Manifold Learning with Independent Coordinate Selection
- Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
- Finding Low-rank Solutions to Matrix Problems, Efficiently and Provably
- From $t$-SNE to UMAP with contrastive learning
- Understanding Dimensional Collapse in Contrastive Self-supervised Learning