Оптимальное перевзвешивание в IRLS: доказана сходимость для ядерной нормы
Минимизация ядерной нормы лежит в основе многих задач низкорангового восстановления — от сжатых измерений до рекомендательных систем. Итеративно перевзвешенные наименьшие квадраты (IRLS) — один из естественных подходов к решению таких задач, однако до сих пор оставались неясными их точная скорость сходимости и роль оператора весов. Новая теоретическая работа, опубликованная на arXiv, восполняет этот пробел.
Авторы доказали точные скорости сходимости для IRLS в задаче минимизации ядерной нормы с ограничениями. Ключевым элементом стал новый анализ мажоризации для сглаженной ядерной нормы: было показано, что оператор весов, основанный на гармоническом среднем, задаёт корректный глобальный квадратичный мажорант. Более того, этот оператор оптимален в семействе весов, построенных на степенных средних.
Этот результат проясняет, почему гармоническое среднее работает лучше классических односторонних схем перевзвешивания, которые учитывают только информацию о строчном или столбцовом пространстве. Ранее предпочтение гармонического среднего часто объяснялось эмпирически; теперь оно получило строгое теоретическое обоснование.
В работе также доказана глобальная линейная сходимость IRLS при выполнении свойства нулевого пространства Шаттена-1. Для варианта с гармоническими весами установлена локальная скорость сходимости, которая не зависит от размерности задачи — важный результат для практического применения в больших массивах данных.
Дополнительно авторы привели контрпример, показывающий, что такой размерно-независимой локальной скорости в общем случае нельзя добиться для односторонних операторов весов, которые преобладают в литературе. Это уточняет границы применимости различных схем и помогает выбрать правильный метод.
Численные эксперименты, выполненные авторами, подтверждают теоретические выводы и демонстрируют практическое преимущество гармонического перевзвешивания для квадратных, прямоугольных и даже неблагоприятно инициализированных задач восстановления. Результаты открывают путь к более надёжным и быстрым алгоритмам в областях, где требуется восстановление матриц по неполным данным.
