Bridge detection and robust geodesics estimation via random walks

Eugene Brevdo; Peter Jeffrey Ramadge

doi:10.1109/ICASSP.2010.5495135

Bridge detection and robust geodesics estimation via random walks

Eugene Brevdo, Peter Jeffrey Ramadge

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We propose an algorithm for detecting bridges and estimating geodesic distances from a set of noisy samples of an underlying manifold. Finding geodesics on a nearest neighbors graph is known to fail in the presence of bridges. Our method detects bridges using global statistics via a Markov random walk and denoises the nearest neighbors graph using "surrogate" weights. We show experimentally that our method outperforms methods based on local neighborhood statistics.

Original language	English (US)
Title of host publication	2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings
Pages	2102-2105
Number of pages	4
DOIs	https://doi.org/10.1109/ICASSP.2010.5495135
State	Published - Nov 8 2010
Event	2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Dallas, TX, United States Duration: Mar 14 2010 → Mar 19 2010

Other

Other	2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010
Country/Territory	United States
City	Dallas, TX
Period	3/14/10 → 3/19/10

All Science Journal Classification (ASJC) codes

Software
Signal Processing
Electrical and Electronic Engineering

Access to Document

10.1109/ICASSP.2010.5495135

Cite this

@inproceedings{9ba2a83bb12e4647a0117ed3fd9aed87,

title = "Bridge detection and robust geodesics estimation via random walks",

abstract = "We propose an algorithm for detecting bridges and estimating geodesic distances from a set of noisy samples of an underlying manifold. Finding geodesics on a nearest neighbors graph is known to fail in the presence of bridges. Our method detects bridges using global statistics via a Markov random walk and denoises the nearest neighbors graph using {"}surrogate{"} weights. We show experimentally that our method outperforms methods based on local neighborhood statistics.",

author = "Eugene Brevdo and Ramadge, {Peter Jeffrey}",

year = "2010",

month = nov,

day = "8",

doi = "10.1109/ICASSP.2010.5495135",

language = "English (US)",

isbn = "9781424442966",

pages = "2102--2105",

booktitle = "2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings",

note = "2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 ; Conference date: 14-03-2010 Through 19-03-2010",

}

Brevdo, E & Ramadge, PJ 2010, Bridge detection and robust geodesics estimation via random walks. in 2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings., 5495135, pp. 2102-2105, 2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010, Dallas, TX, United States, 3/14/10. https://doi.org/10.1109/ICASSP.2010.5495135

TY - GEN

T1 - Bridge detection and robust geodesics estimation via random walks

AU - Brevdo, Eugene

AU - Ramadge, Peter Jeffrey

PY - 2010/11/8

Y1 - 2010/11/8

N2 - We propose an algorithm for detecting bridges and estimating geodesic distances from a set of noisy samples of an underlying manifold. Finding geodesics on a nearest neighbors graph is known to fail in the presence of bridges. Our method detects bridges using global statistics via a Markov random walk and denoises the nearest neighbors graph using "surrogate" weights. We show experimentally that our method outperforms methods based on local neighborhood statistics.

AB - We propose an algorithm for detecting bridges and estimating geodesic distances from a set of noisy samples of an underlying manifold. Finding geodesics on a nearest neighbors graph is known to fail in the presence of bridges. Our method detects bridges using global statistics via a Markov random walk and denoises the nearest neighbors graph using "surrogate" weights. We show experimentally that our method outperforms methods based on local neighborhood statistics.

UR - http://www.scopus.com/inward/record.url?scp=78049411348&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78049411348&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.2010.5495135

DO - 10.1109/ICASSP.2010.5495135

M3 - Conference contribution

AN - SCOPUS:78049411348

SN - 9781424442966

SP - 2102

EP - 2105

BT - 2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings

T2 - 2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010

Y2 - 14 March 2010 through 19 March 2010

ER -

Bridge detection and robust geodesics estimation via random walks

Abstract

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this