Коллоквиум ФКН "Существование и построение близких к оптимальным столбцовых и крестовых аппроксимаций матриц"

14 апреля 18:10 – 19:30

Докладчик: Александр Осинский, ИВМ РАН, Сколтех

Тема: Существование и построение близких к оптимальным столбцовых и крестовых аппроксимаций матриц

Аннотация: Часто при решении различных задач в данных присутствует избыточность – весь набор оказывается возможным приблизить, используя линейные комбинации небольшой их части. Для матриц такие приближения, использующие лишь небольшое число строк или столбцов, называются крестовыми аппроксимациями (для многомерных данных в виде тензоров приближаются матрицы разверток). Чтобы не потерять основное преимущество таких аппроксимаций – отсутствие необходимости рассмотрения всего набора данных – строки и столбцы на практике выбираются исходя из свойств подматрицы на их пересечении. Часто используемым свойством является объем подматрицы, для квадратных подматриц равный модулю их определителя. К сожалению, поиск подматриц большого или даже максимального объема не гарантирует достижения аппроксимаций, достаточно близких, например, к сингулярному разложению. Однако, высокая эффективность такого поиска на практике говорит о том, что подход должен работать для "большинства" матриц. В данном докладе будет показано, что данное утверждение можно сформулировать математически строго – что при любых фиксированных размерах и сингулярных числах матрицы, с точки зрения меры соответствующего им randsvd ансамбля, большинство матриц можно эффективно аппроксимировать на основе подматриц, выбранных из принципа максимального объема.