КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ
Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.
ОБЩИЕ СВЕДЕНИЯ
Номер проекта 19-71-00063
НазваниеСложность в линейной алгебре: алгоритмы и нижние оценки
Руководитель Шитов Ярослав Николаевич, Кандидат физико-математических наук
Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Московский физико-технический институт (национальный исследовательский университет)" , г Москва
Конкурс №40 - Конкурс 2019 года «Проведение инициативных исследований молодыми учеными» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными
Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-102 - Алгебра
Ключевые слова линейная алгебра, разложение тензора, неотрицательные матрицы, алгоритмическая сложность, комбинаторная оптимизация, вычислительная геометрия, абстрактная алгебра, теория колец, теория полуколец, расширения полей
Код ГРНТИ27.17.29
ИНФОРМАЦИЯ ИЗ ЗАЯВКИ
Аннотация
К непосредственным практическим приложениям тропической линейной алгебры можно отнести теорию оптимизации (хотя бы потому, что естественное обобщение понятия определителя матрицы на тропический случай соответствует решению фундаментальной задачи о назначениях [Kuhn H. W. The Hungarian method for the assignment problem // Naval research logistics quarterly 2 (1955) 83-97]), а также теории расписаний и дискретных систем событий [Cohen G., Gaubert S., Quadrat J. P. Max-plus algebra and system theory: where we are and where to go now // Annual reviews in control 23 (1999) 207-219], и помимо того, находит заметные приложения в алгебраической геометрии, дискретной математики и других областях "чистой" науки [Develin M., Santos F., Sturmfels B. On the rank of a tropical matrix // Combinatorial and computational geometry 52 (2005) 213-242]. Сказанное выше может быть отнесено и к линейной алгебре над нечеткими структурами, которые не только обобщают тропические алгебры, но и находят самостоятельные приложения в теории автоматов [A. Stamenkovic, M. Ciric, M. Basic, Ranks of fuzzy matrices. Applications in state reduction of fuzzy automata, Fuzzy Sets Syst., 333 (2018) 124-139] и обработке данных [R. Belohlavek, M. Krmelova, Beyond Boolean matrix decompositions: toward factor analysis and dimensionality reduction of ordinal data, IEEE ICDM 2013 961-966].
Проблема факторизации неотрицательных матриц также является одной из заметных задач прикладной математики: отметим статью Ли и Сеунга об обработке изображений, опубликованную в журнале NATURE [D. D. Lee, H. S. Seung, Learning the parts of objects by non-negative matrix factorization, Nature 401 (1999), 788-791]: эта статья имеет около 10 000 цитирований в рецензируемых журналах. К другим областям прикладной и вычислительной математики, где факторизация неотрицательных матриц находит важные приложения, относятся теория оптимизации [M. Yannakakis, Expressing combinatorial optimization problems by linear programs, J. Comput. System Sci. 43(3) (1991) 441–466], теория сложности вычислений [S. Arora, R. Ge, R. Kannan, A. Moitra, Computing a nonnegative matrix factorization - provably, Proceedings of the 44th symposium on Theory of Computing, ACM, 2012], [S. A. Vavasis, On the complexity of nonnegative matrix factorization, SIAM Journal on Optimization 20(3) (2009), 1364–1377], математическая статистика [K. Kubjas, E. Robeva, B. Sturmfels, Fixed points of the EM algorithm and nonnegative rank boundaries, Annals of Statistics 43(1) (2015), 422–461], [J. E. Cohen, U. G. Rothblum, Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, Linear Algebra Appl. 190 (1993) 149–168], вычислительная геометрия [S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, R. de Wolf, Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds, Proc. 44th Symp. on Th. of Comp., ACM, 2012], [T. Rothvoss, Some 0/1 polytopes need exponential size extended formulations, Mathematical Programming 142 (2013) 255–268].
Наконец, понятие ранга тензора и соответствующего разложения играет не менее значительную роль в практических приложениях, чем аналогичные понятия для неотрицательных матриц. Области применения разложений тензоров включают, например, аналитическую химию [A. Lorber, Avraham, Features of quantifying chemical composition from two-dimensional data array by the rank annihilation factor analysis method, Analytical Chemistry. 57 (1985) 2395-2397], обработку сигналов [A. Cichocki, S.-I. Amari. Adaptive Blind Signal and Image Processing, Wiley, New York, 2002], статистический анализ [R. Sands, F. W. Young, Component models for three-way data: An alternating least squares algorithm with optimal scaling features, Psychometrika. 45 (1980) 39-67], машинное обучение [A. Anandkumar, R. Ge, D. Hsu, S. T. Kakade, M. Telgarsky, Tensor decompositions for learning latent variable models, The Journal of Machine Learning Research. 15 (2014) 2773–2832].
В силу использования перечисленных методов в реальных приложениях задача построения новых алгоритмов и изучения их сложности становится особенно важной. Заявитель надеется получить новые результаты по данной теме и надеется, что перечисленные приложения подтверждают значимость темы проекта как в целом, так и с точки зрения направления «Н1» из «Стратегии НТР РФ».