शोधकर्ताओं ने उच्च-आयामी प्रोक्स्टिस मिलान समस्या में सटीक पुनर्प्राप्ति के लिए एक बहुपद-समय एल्गोरिदम प्रस्तुत किया, जहाँ गॉसियन सदिशों के दो सेट अज्ञात क्रमपरिवर्तन और घूर्णन के माध्यम से संरेखित किए जाते हैं। विधि इस संरेखण को प्राप्त करने के लिए चौड़े वृक्षों के भारित गणना की गणना करती है।
- एल्गोरिदम उच्च प्रायिकता के साथ सफल होता है जब आयाम $d \ge \mathrm{polylog}(n)$ और सहसंबंध का वर्ग $\rho^2 > \sqrt{\alpha}$ हो, जहाँ $\alpha \approx 0.338$ ओटर का वृक्ष गणना स्थिरांक है।
- एक सुधारी गई सूचना-सैद्धांतिक गारंटी दिखाती है कि सटीक पुनर्प्राप्ति तब संभव है जब $\rho^2 \gtrsim \max\{\log n/d, \sqrt{\log n/n}\}$ हो।
- एक निम्न-घात लाभ गणना सुझाव देती है कि किसी भी वृक्ष गणना एल्गोरिदम के लिए शर्त $\rho^2 > \sqrt{\alpha}$ आवश्यक है।
यह कार्य उस उच्च-आयामी क्षेत्र को संबोधित करता है जो पहले अज्ञात था, जहाँ पूर्व गारंटी में लगभग पूर्ण सहसंबंध की आवश्यकता थी।