| Аннотация |
Важнейшими задачами линейной алгебры являются построение аппроксимаций малого ранга или поиск разреженного представления данных. Работа в подпространстве с меньшей размерностью позволяет не только существенно ускорить решение различных задач, но часто позволяет избавиться и от части шума, оставляя лишь наиболее значимые данные. Одним из наиболее успешных и одновременно крайне быстрых методов построения аппроксимаций является крестовый метод, строящий аппроксимации на основе лишь части строк и столбцов матрицы. Выбор таких строк и столбцов тесно связан с выбором подматрицы на их пересечении: если данная подматрица обладает определенными экстремальными свойствами, то погрешность построенной крестовой аппроксимации оказывается мала. На данный момент большинство алгоритмов в качестве такого свойства используют так называемый объем подматрицы: жадно максимизируя объем путем добавления новых или замен текущих строк и столбцов, удается достичь аппроксимаций высокой точности по норме Чебышева. Аналогично, если требуется построить столбцовую аппроксимацию, то есть как можно точнее выразить столбцы матрицы через часть ее столбцов (задача одновременной аппроксимации), то можно использовать столбцы большого объема. Однако, это далеко не единственный, и далеко не самый эффективный способ построения аппроксимаций такого рода. Недавние теоретические результаты показывают, что ключевым свойством для достижения аппроксимаций высокой точности по спектральной норме и норме Фробениуса является ограничение на норму псевдообратной к найденной подматрице. Таким образом, важной актуальной задачей оказывается построение и анализ быстрых (жадных) алгоритмов поиска подматриц с ограниченными псевдообратными. Сейчас уже существует множество алгоритмов поиска таких подматриц, благодаря их важности также при дизайне экспериментов, поиске минимальных охватывающих эллипсоидов, при отборе признаков и других. Однако, подавляющее большинство существующих алгоритмов недостаточно эффективны (например, так называемые leverage scores часто приводят к набору существенно большего числа столбцов, чем требуется), недостаточно быстрые (например, жадное удаление столбцов, хотя и не требует много столбцов, требует вычислительно дорогостоящего пересчета сингулярного разложения) или в целом неверно используют критерий выбора (например, не максимизируют объем, а выбирают подматрицу с вероятностью, пропорциональной её объему), что часто связано с недостатком теоретических гарантий жадных алгоритмов. Более того, в научной литературе отсутствует практическое сравнение подобных алгоритмов, что затрудняет выбор оптимального решения. В связи с этим данный проект направлен на усовершенствование существующих и разработку новых алгоритмов поиска подматриц с ограниченными псевдообратными (по спектральной норме и норме Фробениуса). Его научная новизна будет заключаться в обосновании быстрой сходимости алгоритмов, анализе свойств полученных подматриц, а также в сравнении их эффективности в различных условиях - например, в зависимости от скорости убывания сингулярных чисел данных. Новые алгоритмы и оценки не только позволят в принципе находить наиболее значимые данные, но и более точно решать задачу построения крестовой аппроксимации и одновременной аппроксимации столбцов.
|
