D-SLR заменяет усечённое SVD за три разложения без настройки параметров

Исследователи представили D-SLR (Disjoint Row-Sparse plus Low-Rank) — метод сжатия матриц, который претендует на роль прямой замены усечённого SVD. Он считается в замкнутой форме, весь график «ошибка против числа параметров» и итоговое решение стоят три сингулярных разложения, а при нуле сохранённых строк алгоритм вырождается в обычный SVD. Значит, при равном бюджете он не проигрывает. Препринт вышел в arXiv cs.LG, эксперименты проведены на таблицах эмбеддингов LLM, сетевом трафике и гиперспектральных изображениях.

Что не так с усечённым SVD

Когда матрицу нужно сжать с возможностью восстановления, по умолчанию берут усечённое SVD: данные приближаются одной низкоранговой структурой. Метод быстрый и хорошо изучен, но у него есть слабое место. Если несколько строк плохо ложатся в общее низкоранговое подпространство, они тянут вверх остаточную ошибку, а ранг приходится повышать для всех строк сразу.

Чтобы это исправить, к низкому рангу обычно добавляют строчно-разреженную компоненту, которая перекрывается с низкоранговой частью. Такие совместные задачи решают итеративно, с подбором коэффициентов регуляризации. Это лишняя настройка, нестабильность и время вычислений. Авторы D-SLR предлагают обойтись без всего этого.

Как устроена дизъюнктность

Ключевое ограничение звучит просто: каждая строка либо хранится дословно, либо приближается низкоранговой подгонкой, но никогда не делает и то и другое. Для квадратичной ошибки, как утверждают авторы, это ограничение ничего не стоит. Оптимум совместной задачи достижим и в дизъюнктной форме, причём с меньшим числом параметров при любом нетривиальном ранге и любом числе сохранённых строк.

Алгоритм сразу оценивает весь компромисс между ошибкой и числом параметров по сетке «ранг × число сохранённых строк». Решение выбирается уже после этого: по целевой ошибке, по бюджету параметров или по заданному правилу выбора. Один раз посчитанную сетку можно использовать под разные требования.

Основные характеристики из аннотации:

• замкнутое решение без итеративных солверов;
• стоимость сетки и решения вместе — три SVD;
• нет настраиваемых параметров и регуляризации;
• при нуле сохранённых строк совпадает с усечённым SVD;
• при каждом нетривиальном ранге и числе строк использует не больше параметров, чем совместная модель.

Сертификат вместо надежды на удачный выбор

Отдельный вклад работы — апостериорная нижняя граница ошибки, не требующая допущений о данных. Она вычисляется для каждой формы решения, то есть для каждой пары «ранг и число хранимых строк». Для выбранного решения можно посмотреть, сколько в принципе могла бы выиграть любая другая комбинация. Если запас мал, подбирать дальше нет смысла. Если велик, понятно, где искать.

Числовых результатов экспериментов в аннотации нет. Авторы пишут, что опыты на синтетических и реальных данных подтверждают выигрыш и показывают, насколько информативен сертификат. Реальный масштаб улучшений по сравнению с SVD придётся смотреть в полном тексте. Заявление «не хуже при равной стоимости» следует из конструкции метода, а вот «насколько лучше» зависит от структуры конкретных данных.

Где это можно применить

Самый очевидный кандидат — таблицы эмбеддингов языковых моделей. В них часть токенов, например редкие или нетипичные, плохо описывается общим низким рангом, и хранить такие строки целиком может быть выгоднее, чем повышать ранг для всей таблицы. Похожая логика работает для сетевого трафика с редкими аномальными потоками и для гиперспектральных снимков с выбивающимися пикселями.

Практически метод стоит проверить там, где SVD уже стоит в пайплайне сжатия: достаточно подставить D-SLR и сравнить кривые ошибки при том же бюджете параметров. Так как при нуле строк результат совпадает с SVD, риск регрессии минимален. Оговорка одна: гарантии сформулированы для квадратичной ошибки, а для метрик качества модели, например перплексии после сжатия весов, выигрыш нужно измерять отдельно.