- Предварительная подготовка метода Качмажа путем зарисовок (arXiv)
Автор : Александр Катруца, Иван Оселедец
Аннотация: Мы предлагаем новый метод предварительной обработки метода Качмажа путем эскизирования. Метод Качмажа — это стохастический метод решения переопределенных линейных систем, основанный на выборке строк матрицы. Стандартный подход к ускорению сходимости итерационных методов — использование предобуславливателя. Как мы показываем, наилучший предобуславливатель для этого метода может быть построен из QR-разложения матрицы системы, но сложность этой процедуры слишком высока. Поэтому, чтобы уменьшить эту сложность, мы используем случайное зарисовывание и сравниваем его с методом Качмажа без предварительной обработки. Разработанный метод применим для различных модификаций классического метода Качмажа, предложенных в последнее время. Мы приводим численные эксперименты, чтобы показать эффективность разработанных методов при решении как случайных, так и реальных переопределенных линейных систем.
2. О блочном гауссовском эскизе для метода Качмажа (arXiv)
Автор : Дина Ниделл, Елизавета Реброва
Аннотация: Алгоритм Качмажа является одним из самых популярных методов решения крупномасштабных переопределенных линейных систем благодаря своей простоте и вычислительной эффективности. Этот метод можно рассматривать как частный случай более общего класса методов эскиза и проекта. Недавно была предложена блочная гауссовская версия, в которой используется блочный гауссовский эскиз, обладающий свойствами регуляризации гауссовского эскиза в сочетании с ускорением блочных вариантов. Теоретический анализ был предоставлен только для неблочной версии метода Гауссова эскиза. Здесь мы предоставляем теоретические гарантии для блочного гауссовского метода Качмажа, доказывая ряд результатов сходимости, демонстрирующих экспоненциальную сходимость к решению в ожидании. С другой стороны, благодаря этой теории и обширной экспериментальной поддержке мы видим, что численная сложность каждой итерации обычно уступает этому методу другим итеративным методам проецирования. Мы выделяем только одну ситуацию, в которой это может быть выгодно, а именно, когда эффект регуляризации используется для уменьшения дисперсии итераций при определенных моделях шума и сходимости для некоторых конкретных матричных конструкций.
