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

DOI10.1007/S10107-016-1090-7zbMATH Open1391.90472DBLPjournals/mp/DingQ17arXiv1406.5736OpenAlexW2963244596WikidataQ59614089 ScholiaQ59614089MaRDI QIDQ2364497FDOQ2364497

Houduo Qi, Chao Ding

Publication date: 21 July 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: 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, we develop a fast inexact accelerated proximal gradient method. 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.

Full work available at URL: https://arxiv.org/abs/1406.5736

zbMATH Keywords

error boundsnonlinear dimensionality reductionmultidimensional scalingrandom graph modelsEuclidean distance matrixlow-rank matrixconvex matrix optimization

Mathematics Subject Classification ID

Convex programming (90C25) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Matrix completion from noisy entries
• Statistics for high-dimensional data. Methods, theory and applications.
• Modern multidimensional scaling. Theory and applications.
• The Structure and Function of Complex Networks
• Noisy low-rank matrix completion with general sampling distribution
• Exact matrix completion via convex optimization
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• Characterization of the subdifferential of some matrix norms
• Remarks to Maurice Frechet's article ``Sur la definition axiomatique d'une classe d'espaces vectoriels distancies applicables vectoriellement sur l'espace de Hilbert
• Multidimensional scaling.
• Some distance properties of latent root and vector methods used in multivariate analysis
• A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
• User-friendly tail bounds for sums of random matrices
• Some properties of invariant sets of a flow
• 10.1162/15324430260185592
• Random graphs.
• Rank penalized estimators for high-dimensional matrices
• The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• A Simpler Approach to Matrix Completion
• On the rank minimization problem and its control applications
• A rank-corrected procedure for matrix completion with fixed basis coefficients
• Dimension Reduction: A Guided Tour
• Localization from incomplete noisy distance measurements
• Second‐Order Cone Programming Relaxation of Sensor Network Localization

Cited In (14)

• An Ordinal Weighted EDM Model for Nonmetric Multidimensional Scaling
• A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery
• On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming
• Perturbation analysis of the Euclidean distance matrix optimization problem and its numerical implications
• COAST: A Convex Optimization Approach to Stress-Based Embedding
• Geometric Characterization of Maximum Diversification Return Portfolio via Rao’s Quadratic Entropy
• Ordinal Distance Metric Learning with MDS for Image Ranking
• A Corrected Tensor Nuclear Norm Minimization Method for Noisy Low-Rank Tensor Completion
• Matrix optimization based Euclidean embedding with outliers
• Robust low transformed multi-rank tensor methods for image alignment
• Color Image Inpainting via Robust Pure Quaternion Matrix Completion: Error Bound and Weighted Loss
• A Euclidean distance matrix model for protein molecular conformation
• A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications
• Robust Euclidean embedding via EDM optimization

Uses Software

• SDPT3
• SNLSDP
• MNIST
• Enron Email Dataset
• Frey Face

This page was built for publication: Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2364497)