Відновлення матриць відстаней та їх застосування
DOI:
https://doi.org/10.32626/2308-5878.2021-22.75-80Анотація
Матриці відстаней застосовуються в геометричному моделюванні та в задачах відновлення геометричних об’єктів, економіці, біоінформатиці, програмуванні. Матриці відстаней застосовуються у машинному навчанні, наприклад, створюються програми, пов'язані з дорожнім трафіком, автобусними маршрутами, геолокацією зокрема компанія Yandex створила сервіс, у якому, за допомогою матриць відстаней прогнозується завантаженість доріг, на потрібний час у майбутньому. Таким чином, автомобілісти можуть запобігти потрапляння у затори. Distance Matrix API — це сервіс, який повідомляє відстань і час в дорозі між початком руху та точкою призначення. Сервіс повертає інформацію на основі запропонованого маршруту між початковою та кінцевою точками, обчисленого API картами Google, і складається із значеннь тривалості подорожі та відстані для кожної пари пунктів.
Також матриці відстаней можуть бути застосовані при створенні будь-якої статистики. У біоінформатиці матриці відстаней використовуються для представлення структур білків незалежним від координат чином, або для відновлення відстаней у ланцюгу ДНК.
У [4] автори розглядають фундаментальні властивості EDM, такі як ранг та не визначеність. У статті досліджують, як різні властивості EDM можуть бути використані для розробки алгоритмів для заповнення та зменшення шумів даних про відстані. Попутно автори демонструють застосування матриць відстаней для калібрування положення мікрофона та ультразвукової томографії.
В роботі знайдено критерій можливості відновлення матриці Евклідових відстаней на прямій, та між вершинами опуклого n-кутника на площині. Розроблено алгоритм передачі ключа к шифру з використанням матриць Евклідових відстаней на площині. Розроблено швидкий алгоритм відновлення матриці відстаней між об’єктами на прямій.
Посилання
Patwari N., Ash J. N., Kyperountas S., Hero A. O., Moses R. L., Correal N. S. Locating the Nodes: Cooperative Localization in Wireless Sensor Networks. N IEEE Signal Process. Mag. 2005. Vol. 22. № 4. P. 54-69.
Alfakih A., Khandani A., Wolkowicz H. Solving Euclidean Distance Matrix Completion Problems via Semidefinite Programming. Comput. Optim. Appl. 1999. Vol. 12. № 1-3. P. 13-30.
Doherty L., Pister K., El Ghaoui L. Convex Position Estimation in Wireless Sensor Networks. Proc. IEEE INFOCOM. 2001. Vol. 3. P. 1655-1663.
Dokmanic I., Parhizkar R., Ranieri J., Vetterli M. Euclidean Distance Matrices: Essential Theory, Algorithms and Application. IEEE Signal Process. Mag. 2015. Vol. 32. № 6. P. 12-30.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
