Можно восстановить через учетную запись
live.com (аналог учетки Google, только для Microsoft)
https://outlook.live.com/people/
Вкладка мои контакты:
P.S. При условии что вы сохраняли контакты в облаке.
Припоминаю, что на моей Люмии была возможность использовать учетку Google