КАРТОЧКА
ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ
Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.
ОБЩИЕ СВЕДЕНИЯ
Номер 19-71-00063
НазваниеСложность в линейной алгебре: алгоритмы и нижние оценки
РуководительШитов Ярослав Николаевич, Кандидат физико-математических наук
Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Московский физико-технический институт (национальный исследовательский университет)", г Москва
| Период выполнения при поддержке РНФ | 07.2019 - 06.2021 |
Конкурс№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» из «Стратегии НТР РФ».
Ожидаемые результаты
Ниже приводится список проблем, над которыми заявитель надеется работать (и некоторые из которых надеется решить) по ходу выполнения проекта. Все перечисленные результаты дают решения задач, поставленных ранее другими исследователями, и в списке приводятся авторы, журнал и год выхода статьи с соответствующей проблемой. Как видно из списка, большинство этих проблем были поставлены достаточно давно в активно цитируемых работах, вышедших в ведущих международных журналах. Заявитель надеется, что эти факты могут свидетельствовать о значимости планируемого им исследования.
1. Описание сложности вполне положительного (cp-) и вполне неотрицательно определенного (cpsd-) разложения матрицы:
(a) доказательство ETR-сложности вычисления cp-разложения матрицы [Berman A., Rothblum U. G. Linear Algebra Appl. 419 (2006) 1-7],
(b) доказательство ETR-сложности вычисления cpsd-разложения матрицы [Gribling S., de Laat D., Laurent M. Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization, to appear in Foundations of Computational Mathematics, 2019],
(c) построение быстрого алгоритма построения cpsd-разложения матрицы в случае ограниченного ранга,
(d) исследование сложности распознавания вполне положительных матриц [Berman A., Shaked-Monderer N. Acta Mathematica Vietnamica 43 (2018) 629-639].
2. Исследование нижних оценок сложности расширения многогранников и связанных с ними вопросов.
(а) Выпуклые многоугольники общего вида: является ли любой выпуклый n-угольник линейной проекцией многогранника с не более, чем 2*Sqrt(2n-2)-1 гранями [Vandaele, A., Gillis, N., Glineur, F., & Tuyttens, D. (2016). Heuristics for exact nonnegative matrix factorization. Journal of Global Optimization, 65(2), 369-400], [Fiorini, T. Rothvoß, and H. R. Tiwary, Extended formulations for polygons, Discrete Comput. Geom., 48 (2012), pp. 658–668], [Padrol A. Extension complexity of polytopes with few vertices or facets //SIAM Journal on Discrete Mathematics. – 2016. – Т. 30. – №. 4. – С. 2162-2176].
(b) Доказательство того, что некоторые выпуклые n-угольники не допускают расширенного представления с менее, чем n гранями, при отсутствии скрытых вершин [Pashkovich K., Weltge S. Hidden vertices in extensions of polytopes // Operations Research Letters. – 2015. – Т. 43. – №. 2. – С. 161-164].
(c) Вычисление сложности расширения правильных многогранников старшей размерности [Vandaele, A., Gillis, N., Glineur, F., & Tuyttens, D. (2016). Heuristics for exact nonnegative matrix factorization. Journal of Global Optimization, 65(2), 369-400].
(d) Исследование сложности задачи факторизации нечетких матриц фиксированного ранга [Shitov Y. Factoring a band matrix over a semiring, to appear in Fuzzy Sets and Systems, 2019].
3. Дальнейшие контрпримеры к известной гипотезе Комона:
(a) для частично симметричных тензоров [Buczyński J., Landsberg J. M. Linear Algebra and its Applications 438 (2013) 668-689],
(b) над полем вещественных чисел [Zhang X., Huang Z. H., Qi L. SIAM Journal on Matrix Analysis and Applications. 37 (2016) 1719-1728],
(c) для тензоров старшей размерности [Shitov Y. SIAM Journal of Applied Algebra and Geometry 2 (2018) 428-443].
Кроме того, заявитель планирует развивать и другие направления, намеченные в его предыдущих работах. В частности, планируется исследовать алгоритмическую сложность иных актуальных задач теории графов, тропической математики и абстрактной алгебры.
ОТЧЁТНЫЕ МАТЕРИАЛЫ