Name
Abstract | ||
|---|---|---|
We derive a robust Euclidean embedding pro- cedure based on semidefinite programming that may be used in place of the popular classical multidimensional scaling (cMDS) al- gorithm. We motivate this algorithm by ar- guing that cMDS is not particularly robust and has several other deficiencies. General- purpose semidefinite programming solvers are too memory intensive for medium to large sized applications, so we also describe a fast subgradient-based implementation of the ro- bust algorithm. Additionally, since cMDS is often used for dimensionality reduction, we provide an in-depth look at reducing dimen- sionality with embedding procedures. In par- ticular, we show that it is NP-hard to find optimal low-dimensional embeddings under a variety of cost functions. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1143844.1143866 | ICML |
Keywords | Field | DocType |
robust euclidean embedding,general-purpose semidefinite programming solvers,in-depth look,robust euclidean embedding procedure,embedding procedure,optimal low-dimensional embeddings,cost function,robust algorithm,semidefinite programming,fast subgradient-based implementation,dimensionality reduction,multidimensional scaling | Dimensionality reduction,Subgradient method,Multidimensional scaling,Computer science,Theoretical computer science,Artificial intelligence,Euclidean geometry,Mathematical optimization,Embedding,Curse of dimensionality,Semidefinite embedding,Machine learning,Semidefinite programming | Conference |
ISBN | Citations | PageRank |
1-59593-383-2 | 19 | 1.04 |
References | Authors | |
5 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lawrence Cayton | 1 | 152 | 8.27 |
| Sanjoy Dasgupta | 2 | 2052 | 172.00 |