On Location: Euclidean Distance Matrices, Theory, Algorithms, and Applications

September 30, 2015
Davis Auditorium, CEPSR
Speaker: Martin Vetterli, Professor, Ecole Polytechnique Fédérale de Lausanne and Swiss National Science Foundation


"Location, location, and location" are the three things that matter in real estate, as the saying goes. In many other areas as well, location is key, from indoor positioning, to calibration in source/receiver arrays, to crystallography, to name a few. And central to location in physical space are Euclidean distance matrices (EDMs).

EDMs are matrices of squared distances between points. The definition is deceivingly simple; thanks to their many useful properties, they have found applications in psychometrics, crystallography, machine learning, wireless sensor networks, acoustics, and more. Despite the usefulness of EDMs, they seem to be insufficiently known or used in the signal processing and communication communities.

Our goal is to correct this deficit in a short but comprehensive overview. We go over the fundamental properties of EDMs, such as rank or (non)definiteness, and show how the various EDM properties can be used to design algorithms for completing and denoising distance data.

Along the way, we demonstrate applications to microphone position calibration, ultrasound tomography, room reconstruction from echoes, phase retrieval and acoustic simultaneous location and mapping (SLAM).

By spelling out the essential algorithms, we hope to motivate other researchers to apply EDMs to their own problems. Finally, we suggest directions for further research.

The talk is based on an overview paper in the IEEE Signal Processing Magazine, where the code for all of described algorithms and to generate figures is available online here in the spirit of reproducible research.

This is joint work with Ivan Dokmanic (EPFL), Reza Parhizkar (MaCX ReD), Juri Ranieri (EPFL) and Miranda Krekovic (EPFL).

Speaker Bio

Martin VetterliMartin Vetterli received the Dipl. El.-Ing.degree from Eidgenössische Technische Hochschule (ETHZ) in 1981, the Master of Science degree from Stanford University in 1982, and the Doctorat ès Sciences degree from Ecole Polytechnique Fédérale de Lausanne (EPFL) in 1986.

After his dissertation, he was an Assistant and Associate Professor in Electrical Engineering at Columbia University in New York, and in 1993, he became an Associate and then Full Professor at the Department of Electrical Engineering and Computer Science at the University of California at Berkeley. In 1995, he joined the EPFL as a Full Professor. He held several positions at EPFL, including Chair of Communication Systems and founding director of the National Competence Center in Research on Mobile Information and Communication systems (NCCR-MICS). From 2004 to 2011 he was Vice President of EPFL for international affairs, and from 2011 to 2012, he was the Dean of the School of Computer and Communications Sciences. Since January 2013, he is President of the National Research Council of the Swiss National Science Foundation.

He works in the areas of electrical engineering, computer sciences and applied mathematics. His work covers wavelet theory and applications, image and video compression, self-organized communications systems and sensor networks, as well as fast algorithms, and has led to about 150 journals papers, as well as about 30 patents that led to technology transfer to high-tech companies and the creation of several start-ups.

He is the co-author of three textbooks, Wavelets and Subband Coding (with J. Kovacevic, Prentice-Hall, 1995), Signal Processing for Communications ( P. Prandoni, EPFL Press, 2008) and Foundations of Signal Processing (with J. Kovacevic and V. Goyal , Cambridge University Press, 2014). These books are available in open access, and his research group follows the reproducible research philosophy.

His work has won him numerous prizes, such as best paper awards from EURASIP in 1984 and from the IEEE Signal Processing Society in 1991, 1996 and 2006, the Swiss National Latsis Prize in 1996, the SPIE Presidential award in 1999, the IEEE Signal Processing Technical Achievement Award in 2001 and the IEEE Signal Processing Society Award in 2010. He is a Fellow of the IEEE, the ACM, and EURASIP, was a member of the Swiss Council on Science and Technology (2000-2004), and is a ISI highly cited researcher in engineering.

Hosted by Aurel A. Lazar.

500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University