کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4604938 | 1631329 | 2016 | 13 صفحه PDF | دانلود رایگان |
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.
Journal: Applied and Computational Harmonic Analysis - Volume 40, Issue 3, May 2016, Pages 575–587