Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction

Classical multidimensional scaling only works well when the noisy distances observed in a high dimensional space can be faithfully represented by Euclidean distances in a low dimensional space. Advanced models such as Maximum Variance Unfolding (MVU) and Minimum Volume Embedding (MVE) use Semi-Defin...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2017-07, Vol.164 (1-2), p.341-381
Main Authors: Ding, Chao, Qi, Hou-Duo
Format: Article
Language:English
Subjects:
Asymptotic properties
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Computational geometry
Convex analysis
Convexity
Data points
Euclidean geometry
Full Length Paper
Learning
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematical models
Mathematics
Mathematics and Statistics
Mathematics of Computing
Matrices (mathematics)
Multipliers
Noise prediction
Nonlinearity
Numerical Analysis
Optimization
Programming
Quality
Reduction
Representations
Scaling
Theoretical
Variance
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Classical multidimensional scaling only works well when the noisy distances observed in a high dimensional space can be faithfully represented by Euclidean distances in a low dimensional space. Advanced models such as Maximum Variance Unfolding (MVU) and Minimum Volume Embedding (MVE) use Semi-Definite Programming (SDP) to reconstruct such faithful representations. While those SDP models are capable of producing high quality configuration numerically, they suffer two major drawbacks. One is that there exist no theoretically guaranteed bounds on the quality of the configuration. The other is that they are slow in computation when the data points are beyond moderate size. In this paper, we propose a convex optimization model of Euclidean distance matrices. We establish a non-asymptotic error bound for the random graph model with sub-Gaussian noise, and prove that our model produces a matrix estimator of high accuracy when the order of the uniform sample size is roughly the degree of freedom of a low-rank matrix up to a logarithmic factor. Our results partially explain why MVU and MVE often work well. Moreover, the convex optimization model can be efficiently solved by a recently proposed 3-block alternating direction method of multipliers. Numerical experiments show that the model can produce configurations of high quality on large data points that the SDP approach would struggle to cope with.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-016-1090-7