Семинар HDI Lab: Существование и построение близких к оптимальным столбцовых и крестовых аппроксимаций матриц: вероятностные оценки
В этот четверг, 14 марта, в 14:40 состоится очередной семинар. С докладом выступит Александр Осинский (Сколтех, ИВМ РАН).
Существование и построение близких к оптимальным столбцовых и крестовых аппроксимаций матриц: вероятностные оценки
Крестовые аппроксимации матриц часто используются для приближения больших массивов данных благодаря тому, что могут быть построены исходя из лишь небольшого числа строк и столбцов матриц. При этом в основе используемых на практике алгоритмов, таких как adaptive cross или maxvol, лежит идея максимизации объема подматрицы. Хотя такой подход формально может гарантировать небольшую величину только поэлементной ошибки, обычно наблюдается высокая точность методов также и в норме Фробениуса, несмотря на существование контрпримеров. В данном докладе будет рассмотрен вопрос об эффективности такого подхода к аппроксимации randsvd матриц и показано, что выбор подматриц из принципа максимального объема позволяет с высокой вероятностью (т.е. для большинства randsvd матриц) достичь точности, близкой к точности сингулярного разложения.