A FILTERING TECHNIQUE FOR MARKOV CHAINS WITH APPLICATIONS TO SPECTRAL EMBEDDING

Abstract. Spectral methods have proven to be a highly effective tool in understanding the intrinsic geometry of a high-dimensional data set {xi}ni=1 ⊂ Rd. The key ingredient is the construction of a Markov chain on the set, where transition probabilities depend on the distance between elements, for example where for every 1 ≤ j ≤ n the probability of going from xj to xi is proportional to pij ∼ exp −