Robust Euclidean embedding

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Robust Euclidean embedding

Full text

Pdf (257 KB)

Source

ACM International Conference Proceeding Series; Vol. 148 archive
Proceedings of the 23rd international conference on Machine learning table of contents

Pittsburgh, Pennsylvania

Pages: 169 - 176

Year of Publication: 2006

ISBN:1-59593-383-2

Authors

Lawrence Cayton	University of California, San Diego, CA
Sanjoy Dasgupta	University of California, San Diego, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 36, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1143844.1143866 What is a DOI?

ABSTRACT

We derive a robust Euclidean embedding procedure based on semidefinite programming that may be used in place of the popular classical multidimensional scaling (cMDS) algorithm. We motivate this algorithm by arguing 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 robust algorithm. Additionally, since cMDS is often used for dimensionality reduction, we provide an in-depth look at reducing dimensionality with embedding procedures. In particular, we show that it is NP-hard to find optimal low-dimensional embeddings under a variety of cost functions.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. Belongie , J. Malik , J. Puzicha, Shape Matching and Object Recognition Using Shape Contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.509-522, April 2002 [doi>10.1109/34.993558 ]
	2	Bertsekas, D. P. (1999). Nonlinear progamming. Athena Scientific. 2nd edition.
	3	Borg, I., & Groenen, P. (2005). Modern multidimensional scaling. Springer. 2nd edition.
	4	Dattorro, J. (2005). Convex optimization and euclidean distance geometry. Meboo publishing.
	5	de Silva, V., & Tenenbaum, J. (2004). Sparse multidimensional scaling using landmark points. Manuscript.
	6	Dhamdhere, K., Gupta, A., & Ravi, R. (2004). Approximation algorithms for minimizing average distortion. Proc. 21st STACS.
	7	Gaffke, N., & Mathar, R. (1989). A cyclic projection algorithm via duality. Metrika, 36, 29--54.
	8	W. Glunt , T. L. Hayden , S. Hong , J. Wells, An alternating projection algorithm for computing the nearest euclidean distance matrix, SIAM Journal on Matrix Analysis and Applications, v.11 n.4, p.589-600, Oct. 1990 [doi>10.1137/0611042]
	9	Johan Håstad , Lars Ivansson , Jens Lagergren, Fitting Points on the Real Line and Its Application to RH Mapping, Proceedings of the 6th Annual European Symposium on Algorithms, p.465-476, August 24-26, 1998
	10	Huber, P. (1981). Robust statistics. Wiley Interscience.
	11	Kruskal, J., & Wish, M. (1978). Multidimensional scaling. Sage Publications.
	12	Linial, N., London, E., & Rabinovich, Y. (1995). The geometry of graphs and some of its algorithmic applications. Combinatorica, 15, 215--245.
	13	Platt, J. (2005). Fastmap, metricmap, and landmark mds are all nyström algorithms. Proc. 10th AISTATS.
	14	Saxe, J. (1979). Embeddability of weighted graphs in κ-space is strongly np-hard. Proc. Allerton Conference on Circuit and System theory.
	15	Toh, K. C., Todd, M. J., & Tutuncu, R. (1999). SDPT3 --- a Matlab software package for semidefinite programming. Opt. Methods and Software, 11.