Multidimensional scaling with city‐block distances based on combinatorial optimization and systems of linear equations

Abstract

Multidimensional scaling is a technique for exploratory analysis of multidimensional data. The essential part of the technique is minimization of a multimodal function with unfavorable properties like invariants and non‐differentiability. In this paper a two‐level optimization based on combinatorial optimization and systems of linear equations is proposed exploiting piecewise quadratic structure of the objective function with city‐block distances. The approach is tested experimentally and improvement directions are identified.

Key words:

• Multidimensional scaling
• city‐block distances
• multilevel optimization
• combinatorial optimization