Research map / Learning theory and algorithms / Matrix and tensor methods
Neuc-MDS: Non-Euclidean Multidimensional Scaling Through Bilinear Forms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends classical MDS to indefinite symmetric bilinear forms by selecting eigenvalues (including negative ones) of the centered dissimilarity Gram matrix to minimize STRESS, with a linear-time selection algorithm and a generalized variant (Neuc-MDS+).
Problem
Classical MDS assumes Euclidean geometry; on non-Euclidean, non-metric dissimilarities it discards negative eigenvalues, yielding suboptimal STRESS and a "dimensionality paradox" where more dimensions increase error.
Approach
Generalize the inner product to indefinite symmetric bilinear forms so negative eigenvalues are retained; choose the k eigenvalues (by magnitude and sign balance) that minimize a lower bound on STRESS, and extend to optimal linear combinations of eigenvalues (Neuc-MDS+).
Key results
- On Random-simplex, Neuc-MDS+ reaches STRESS 0.194 versus 80.520 for cMDS and 31.542 for Lower-MDS.
- On MNIST (k=100), Neuc-MDS achieves STRESS 9.935 versus 65.107 for cMDS.
- Neuc-MDS and Neuc-MDS+ fully resolve the dimensionality paradox where cMDS STRESS increases with k.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Neuc-MDS instead of the strongest baseline | MDS · Random-Simplex | STRESS: 31.542 -> 1.179 | Helped |
| Use Neuc-MDS+ instead of the strongest baseline | MDS · Random-Simplex | STRESS: 31.542 -> 0.194 | Helped |
| Use Neuc-MDS instead of the strongest baseline | MDS · Euclidean Ball | STRESS: 17.303 -> 1.196 | Helped |
| Use Neuc-MDS+ instead of the strongest baseline | MDS · Euclidean Ball | STRESS: 17.303 -> 1.351 | Helped |
| Use Neuc-MDS instead of the strongest baseline | MDS · Brain | STRESS: 0.081 -> 0.046 | Helped |
| Use Neuc-MDS+ instead of the strongest baseline | MDS · Brain | STRESS: 0.081 -> 0.045 | Helped |
| Use Neuc-MDS instead of the strongest baseline | MDS · Breast | STRESS: 0.078 -> 0.029 | Helped |
| Use Neuc-MDS+ instead of the strongest baseline | MDS · Breast | STRESS: 0.078 -> 0.029 | Helped |
| Use Neuc-MDS instead of the strongest baseline | MDS · Colorectal | STRESS: 0.036 -> 0.017 | Helped |
| Use Neuc-MDS+ instead of the strongest baseline | MDS · Colorectal | STRESS: 0.036 -> 0.026 | Helped |
| Use Neuc-MDS instead of the strongest baseline | MDS · Leukemia | STRESS: 0.005 -> 0.078 | Hurt |
| Use Neuc-MDS+ instead of the strongest baseline | MDS · Leukemia | STRESS: 0.005 -> 0.096 | Hurt |
Surprising findings
- SMACOF, a nonlinear optimizer, blows up to very large STRESS on Euclidean-ball and image datasets (e.g. 4e6, 2.35e5).
- Neuc-MDS+ does not always beat Neuc-MDS on STRESS, which the authors attribute to the neglected third error term C3.
Limitations
- Optimizes only a lower bound of STRESS; the third error term C3 is not optimized and is non-negligible in some cases.
- Output dissimilarities can contain negative values, which need special handling in downstream tasks.
- Random-matrix analysis assumes unstructured data, and experiments are limited to 10 datasets.
Experimental setup
Datasets: Random-simplex Euclidean-ball CuMiDa genomics (Brain, Breast, Colorectal, Leukemia, Renal) MNIST Fashion-MNIST CIFAR-10
Benchmarks: Random-simplex Euclidean-ball CuMiDa genomics datasets MNIST Fashion-MNIST CIFAR-10
Metrics: STRESS average geometric distortion additive error
Baselines: cMDS Lower-MDS SMACOF
Builds on: classical multidimensional scaling Lower-MDS SMACOF
Closest papers by meaning
- Johnson-Lindenstrauss Lemma Beyond Euclidean Geometry (NeurIPS 2025 · similarity 0.87)
- Finsler Multi-Dimensional Scaling: Manifold Learning for Asymmetric Dimensionality Reduction and Embedding (CVPR 2025 · similarity 0.87)
- Generalized Dimension Reduction Using Semi-Relaxed Gromov-Wasserstein Distance (AAAI 2025 · similarity 0.86)
- Navigating the Effect of Parametrization for Dimensionality Reduction (NeurIPS 2024 · similarity 0.85)
- Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity (NeurIPS 2025 · similarity 0.84)
- Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.