Robust conditional dimension reduction for dissimilarity data

Motivation

• Practitioners use pairwise dissimilarities because they can be easier to obtain than coordinates and need not impose Euclidean distance as the comparison measure.Examples include judgments of stimulus similarity, team comparisons, species abundance, and random heterogeneous media.Source: §1 · p. 1
• MDS seeks a low-dimensional configuration whose pairwise Euclidean distances approximate the observed dissimilarities.The target dimension p is interpreted as the number of underlying features controlling dissimilarities.Source: §1 · pp. 1–2
• Conditional MDS incorporates known features as prior information to recover coordinates associated with unknown features while accounting for known variation.The passage presents conditional MDS as a framework introduced by Bui (2024).Source: §1 · p. 2
• Squared-stress cMDS is vulnerable to contaminated dissimilarities because a few large residuals can dominate the objective and distort the recovered configuration.For classical MDS, double-centering can spread the effect of a single perturbed dissimilarity across many entries.Source: §1 · p. 2

Contribution

• rcMDS replaces squared stress with a scaled Fair M-estimation criterion, retaining robust absolute-residual behavior while avoiding singular weights near zero.The formulation preserves separation between known and unknown sources of variation.Source: §1 · p. 2

Paper outline

• The paper develops preliminaries and an objective-value convergence analysis, presents rcSMACOF, and evaluates the approach experimentally.Source: §1 · p. 2

2 Preliminaries and Problem Formulation

• The setup assumes symmetric dissimilarities with zero diagonal and an irreducible symmetric nonnegative weight matrix; asymmetric dissimilarities are symmetrized by pairwise averaging.Source: §2 · p. 2
• cMDS represents each object with latent coordinates U and an affine transformation of observed covariates, requiring n > p + q.The covariate-difference vectors on active pairs are assumed to contain q linearly independent vectors.Source: §2 · p. 3
• The conditional model combines latent-coordinate and transformed-covariate differences in fitted pairwise distances, and cMDS estimates these features by minimizing conditional stress.Source: §2 · p. 3

2.1 ℓ1-norm cMDS

• The algorithm majorizes nonsmooth conditional strife at the current iterate, converting it into successive fixed-weight conditional-stress problems solvable by Conditional SMACOF.The reweighting links the procedure to IRLS, with residual-based weights held fixed during each conditional-stress update.Source: §2.1 · pp. 3–4
• Least-absolute fitting penalizes large residuals linearly, but its direct IRLS weights are singular near zero; Fair loss smooths that cusp while behaving approximately like ℓ1 for large anomalies.Source: §2 · p. 3, §2.1 · p. 4
• Global minimization of the rcMDS objective is NP-hard, including the restricted one-dimensional case with zero covariates and unit weights.The proof reduces the restricted objective to a one-dimensional Fair-loss embedding problem.Source: §2.1 · pp. 4–5
• For η > 0, residual-dependent weights qk(Y) = wk/(|rk(Y)| + η) define a quadratic majorizer of the Fair objective whose minimization is equivalent to fixed-weight conditional stress.Source: §2.1 · p. 6

3 Robust Conditional SMACOF Algorithm

• At a fixed support point, the Fair objective is majorized by a surrogate whose minimization is equivalent to minimizing fixed-weight conditional stress.Source: §3 · p. 6
• rcSMACOF computes residual-based weights, holds them fixed for an inner Conditional SMACOF update, then recomputes them after the inner loop converges.Source: §3 · pp. 6–7
• With a connected active graph and covariate differences spanning R^q, robust reweighting preserves positive definiteness of V^T H[v] V, validating the ordinary inverse in the B-update.Source: §3 · p. 7
• The stabilized conditional strife decreases when each inner Conditional SMACOF step decreases fixed-weight stress, and its nonnegative sequence converges to a finite limit.Source: §3 · pp. 6–7

4 Computation Experiment

• Agreement was evaluated over ten resampling runs, each generated from 10 contaminated dissimilarity matrices, with corruption ranging from 0% to 20%.The experiments primarily report mean Procrustes statistic and mean average canonical correlation.Source: §4 · p. 8

4.1 Synthetic Car-Brand Perception

• As contamination increased, rcSMACOF maintained higher canonical correlation and lower Procrustes error than cSMACOF, with consistently smaller error bars.It converged within 3,000 iterations in all cases.Source: §4.1 · pp. 8, 10, Figure 2 · p. 9

4.2 Kinship Terms

• At 2% outlier levels, rcSMACOF more clearly recovered residual kinship groupings after conditioning on gender alone or on gender and kinship degree.The cSMACOF configurations showed disrupted local pairings or less coherent relational neighborhoods.Source: §4.2 · p. 10, Figure 3 · p. 11

4.3 Rectangles

• Mean SS was 0.01 for rcSMACOF versus 0.50 for cSMACOF in width–height, and 0.02 versus 0.47 in size–shape.Across 100 replications, rcSMACOF also had lower variability in both representations.Source: Table 1 · p. 12, §4.3 · pp. 12–13, Figure 4 · p. 12

4.4 Face Expression

• At 10% contamination, mean Procrustes error averaged over six scenarios rose from about 0.14 to 0.59 for cSMACOF, versus about 0.17 to 0.26 for rcSMACOF.rcSMACOF had substantially smaller errors across contamination levels in every panel.Source: §4.4 · p. 13

5.1 Choice of η

• Moderate α values, especially 0.01–0.1, provide the most stable balance between recovery accuracy and convergence speed; the experiments use η = 0.03s_Δ by default.Very small α increases iteration counts and often approaches the maximum, while very large α reduces iterations but weakens recovery.Source: §5.1 · p. 13, Figure 6 · p. 15

5.2 Convergence-speed experiment

• The convergence comparison uses matched starting configurations, a 10^-15 stopping tolerance, η = 0.01, and one conditional SMACOF update between robust-weight updates.Both methods are run up to 10,000 iterations.Source: §5.2 · p. 14
• Under 5% and 10% contamination, rcSMACOF rapidly reduces Procrustes error and stabilizes at substantially smaller errors within approximately 300 outer iterations.cSMACOF error stays large and unchanged across iterations; Figure 7 plots Procrustes statistic against iteration count, with lower values indicating better recovery.Source: §5.2 · pp. 14, 16, Figure 7 · p. 15

• rcMDS replaces squared residual loss with a Fair M-estimator, retaining robust absolute-residual behavior while avoiding the singular weights of formal ℓ1 IRLS.Source: §6 · p. 16
• The authors develop rcSMACOF and establish that rcMDS is NP-hard.Source: §6 · p. 16
• Numerical experiments show rcSMACOF is more robust than cSMACOF to corrupted dissimilarities, while small α can slow convergence and overly large α can reduce robustness.Source: §6 · p. 16
• The conclusion characterizes rcMDS as a robust, computationally tractable framework and identifies nonmetric dissimilarity transformations and large-matrix scalability as future directions.Source: §6 · p. 16