A filtering technique for Markov chains with applications to spectral embedding

Spectral methods have proven to be a highly effective tool in understanding the intrinsic geometry of a high-dimensional data set {xi}i=1n⊂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 the probability of going from xjxj to xixi is proportional topij∼exp⁡(−1ε‖xi−xj‖ℓ2(Rd)2)where ε>0 is a free parameter. We propose a method which increases the self-consistency of such Markov chains before spectral methods are applied. Instead of directly using a Markov transition matrix P  , we set pii=0pii=0 and rescale, thereby obtaining a transition matrix P⁎P⁎ modeling a non-lazy random walk. We then create a new transition matrix Q=(qij)i,j=1n by demanding that for fixed j   the quantity qijqij be proportional toqij∼min⁡((P⁎)ij,((P⁎)2)ij,…,((P⁎)k)ij)where we usually set k=2. We show that the method can increase the efficiency of spectral methods and prove that it finds randomly introduced errors with high probability.