КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ
Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.
ОБЩИЕ СВЕДЕНИЯ
Номер проекта 25-71-00096
НазваниеАнализ и реализация алгоритмов построения малоранговых приближений в чебышевской норме
Руководитель Морозов Станислав Викторович, канд. физ.-мат. наук
Организация финансирования, регион Федеральное государственное бюджетное учреждение науки Институт вычислительной математики им. Г.И. Марчука Российской академии наук , г Москва
Конкурс №110 - Конкурс 2025 года «Проведение инициативных исследований молодыми учеными» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными, приоритетного направления деятельности Российского научного фонда «Поддержка молодых ученых»
Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-206 - Вычислительная математика
Ключевые слова норма Чебышева, малоранговые приближения, каноническое тензорное разложение, равномерные приближения, переменная минимизация
Код ГРНТИ27.41.15
ИНФОРМАЦИЯ ИЗ ЗАЯВКИ
Аннотация
Задача построения малоранговых приближений матриц и тензоров является важным компонентом во многих областях науки. Для матриц эта задача может быть легко решена с помощью сингулярного разложения (SVD) в унитарно инвариантных нормах, таких как спектральная норма или норма Фробениуса. В то же время, в некоторых приложениях может потребоваться приближать матрицу поэлементно, то есть в чебышевской норме. Недавние результаты показывают, что эффективные приближения в норме Чебышева могут иметь большие перспективы. Так, например, некоторые функционально порожденные матрицы и тензоры или матрицы, возникающие в моделях с латентными переменными, могут не иметь хороших приближений в унитарно-инвариантных нормах, но допускать эффективные поэлементные приближения. Однако построение малоранговых приближений в чебышевской норме является сложной задачей. Например, уже задача построения оптимальных приближений ранга 1 для матриц является NP-полной. Недавно был предложен алгоритм, способный строить такие приближения (хотя число операций в нем может расти экспоненциально). Однако в случае ранга больше 1 никаких алгоритмов, способных гарантированно строить оптимальные приближения не существует. Целью данного проекта является построение и изучение свойств алгоритмов для решения задачи о малоранговом приближении матриц и тензоров в чебышевской норме, а именно планируется:
1) предложить методы ускорения алгоритма переменной минимизации для решения задачи о построении малоранговых приближений матриц и тензоров в чебышевской норме;
2) предложить алгоритмы построения нижних оценок для точности малорангового приближения матриц в чебышевской норме;
3) исследовать возможность построения алгоритмов, способных гарантированно строить оптимальные приближения для произвольного ранга;
4) исследовать возможность построения оптимальных приближений ранга 1 в каноническом полилинейном формате для тензоров при помощи метода переменной минимизации;
5) предложить алгоритмы аппроксимации функций многих переменных в виде суммы произведений функций одной переменной в равномерной норме.
Ожидаемые результаты
Ожидаемые результаты выполнения проекта состоят в следующем:
1) предложены методы ускорения алгоритма переменной минимизации для решения задачи о построении малоранговых приближений матриц и тензоров в чебышевской норме;
2) предложены алгоритмы построения нижних оценок для точности малорангового приближения матриц в чебышевской норме;
3) исследована возможность построения алгоритмов, способных гарантированно строить оптимальные приближения для произвольного ранга;
4) исследована возможность построения оптимальных приближений ранга 1 в каноническом полилинейном формате для тензоров при помощи метода переменной минимизации;
5) предложены алгоритмы аппроксимации функций многих переменных в виде суммы произведений функций одной переменной в равномерной норме.
На сегодняшний день не существует алгоритмов, способных гарантированно строить оптимальные малоранговые приближения за исключением случая приближений ранга 1 для матриц. Более того, все существующие алгоритмы получают оценки на точность приближения сверху. Алгоритмов, способных получать также нижние оценки на точность приближения, неизвестно. В случае приближения функций многих переменных в виде суммы произведений функций одной переменной (в равномерной норме) известны теоретические оценки на точность приближения, однако никаких алгоритмов также не существует. Исключение составляет случай приближения функции двух переменных в виде произведения функций одной переменной. Стоит также отметить, что задачи об оценке точности малоранговой аппроксимации матриц в чебышевской норме эквивалентна задаче об оценке поперечника по Колмогорову косого октаэдра --- одного из немногих поперечников, для которых на сегодняшний день неизвестна точная асимптотика.
Успешное выполнение проекта позволит эффективнее решать задачи сжатия данных, в том числе в задачах связанных в машинным обучением, а также лучше понимать потенциал использования чебышевских приближений в различных приложениях.