Низкоранговое приближение
В математике аппроксимация низкого ранга — это задача минимизации , в которой функция стоимости измеряет соответствие между заданной матрицей (данными) и аппроксимирующей матрицей (переменной оптимизации) при условии, что аппроксимирующая матрица имеет пониженный ранг . Задача используется для математического моделирования и сжатия данных . Ограничение ранга связано с ограничением сложности модели, соответствующей данным. В приложениях часто помимо ограничения ранга существуют и другие ограничения на аппроксимирующую матрицу, например, неотрицательность и структура Ганкеля .
Низкоранговая аппроксимация тесно связана со многими другими методами, включая анализ главных компонентов , факторный анализ , общий метод наименьших квадратов , скрытый семантический анализ , ортогональную регрессию и декомпозицию по динамическому моду .
Определение
[ редактировать ]Данный
- спецификация структуры ,
- вектор параметров структуры ,
- норма , и
- желаемый ранг ,
Приложения
[ редактировать ]- Идентификация линейной системы , в этом случае аппроксимирующая матрица имеет структуру Ганкеля .
- Машинное обучение , в этом случае аппроксимирующая матрица имеет нелинейную структуру.
- Рекомендательные системы , в которых в матрице данных отсутствуют значения и аппроксимация является категориальной .
- расстояний Завершение матрицы , в этом случае существует ограничение положительной определенности.
- Обработка естественного языка , в этом случае аппроксимация неотрицательна .
- Компьютерная алгебра , в этом случае приближение имеет структуру Сильвестра .
Основная задача аппроксимации низкого ранга
[ редактировать ]Неструктурированная задача с подгонкой, измеряемой нормой Фробениуса , т. е.
имеет аналитическое решение в терминах по сингулярным значениям разложения матрицы данных . Результат называется леммой о матричной аппроксимации или теоремой Эккарта–Янга–Мирского . Первоначально эту проблему решил Эрхард Шмидт. [1] в бесконечномерном контексте интегральных операторов (хотя его методы легко обобщаются на произвольные компактные операторы в гильбертовых пространствах) и позже переоткрыты К. Эккартом и Г. Янгом . [2] Л. Мирский обобщил результат на произвольные унитарно-инвариантные нормы. [3] Позволять
быть разложением по сингулярным значениям , где это прямоугольная диагональная матрица с сингулярными значениями . Для данного , раздел , , и следующее:
где является , является , и является . Тогда звание- матрица, полученная в результате усеченного разложения по сингулярным значениям
таков, что
Минимизатор уникально тогда и только тогда, когда .
Доказательство теоремы Эккарта–Янга–Мирского (для спектральной нормы )
[ редактировать ]Позволять быть вещественной (возможно, прямоугольной) матрицей с . Предположим, что
представляет собой по сингулярным значениям разложение . Напомним, что и являются ортогональными матрицами, а это диагональная матрица с элементами такой, что .
Мы утверждаем, что лучший ранг- приближение к в спектральной норме, обозначаемой , определяется
где и обозначают й столбец и , соответственно.
Во-первых, обратите внимание, что мы имеем
Следовательно, нам нужно показать, что если где и иметь столбцы тогда .
С имеет столбцов, то должна существовать нетривиальная линейная комбинация первых столбцы , то есть,
такой, что . Без потери общности мы можем масштабировать так что или (эквивалентно) . Поэтому,
Результат получается, если извлечь квадратный корень из обеих частей приведенного выше неравенства.
Доказательство теоремы Эккарта–Янга–Мирского (для нормы Фробениуса )
[ редактировать ]Позволять быть вещественной (возможно, прямоугольной) матрицей с . Предположим, что
представляет собой по сингулярным значениям разложение .
Мы утверждаем, что лучший ранг приближение к в норме Фробениуса, обозначаемой , определяется
где и обозначают й столбец и , соответственно.
Во-первых, обратите внимание, что мы имеем
Следовательно, нам нужно показать, что если где и иметь столбцы тогда
По неравенству треугольника со спектральной нормой, если затем . Предполагать и соответственно обозначают ранг приближение к и методом СВД, описанным выше. Тогда для любого
С , когда и мы заключаем, что для
Поэтому,
по мере необходимости.
Взвешенные задачи аппроксимации низкого ранга
[ редактировать ]Норма Фробениуса равномерно взвешивает все элементы ошибки аппроксимации. . Предварительные знания о распределении ошибок можно принять во внимание, рассматривая задачу взвешенной аппроксимации низкого ранга.
где векторизует матрицу столбец мудрый и — заданная положительно (полу)определенная весовая матрица.
Общая задача взвешенной аппроксимации низкого ранга не допускает аналитического решения в терминах разложения по сингулярным значениям и решается методами локальной оптимизации, не дающими гарантии нахождения глобально оптимального решения.
В случае некоррелированных весов задачу взвешенной аппроксимации низкого ранга также можно сформулировать следующим образом: [4] [5] для неотрицательной матрицы и матрица мы хотим свести к минимуму над матрицами, , ранга не более .
По входу L p задачи аппроксимации низкого ранга
[ редактировать ]Позволять . Для , самый быстрый алгоритм работает в время. [6] [7] Одна из важных использованных идей называется Oblivious Subspace Embedding (OSE), она впервые была предложена Сарлосом. [8]
Для , известно, что эта норма L1 по входу более устойчива, чем норма Фробениуса при наличии выбросов, и указывается в моделях, где гауссовские предположения о шуме могут не применяться. Естественно стремиться свести к минимуму . [9] Для и , существуют алгоритмы с доказуемыми гарантиями. [10] [11]
Задача аппроксимации низкого ранга по расстоянию
[ редактировать ]Позволять и — два множества точек в произвольном метрическом пространстве. Позволять представлять матрица где . Такие матрицы расстояний обычно вычисляются в пакетах программного обеспечения и применяются для изучения многообразий изображений, распознавания рукописного текста и многомерного развертывания. Пытаясь уменьшить размер описания, [12] [13] можно изучать аппроксимацию таких матриц низкого ранга.
Распределенная/потоковая задача аппроксимации низкого ранга
[ редактировать ]Рассмотрены задачи аппроксимации низкого ранга в распределенной и потоковой постановке. [14]
Представления изображений и ядер ограничений ранга
[ редактировать ]Используя эквивалентности
и
задача взвешенной аппроксимации низкого ранга становится эквивалентной задачам оптимизации параметров
и
где - единичная матрица размера .
Алгоритм альтернативных проекций
[ редактировать ]Изображение ограничения ранга предлагает метод оптимизации параметров, в котором функция стоимости минимизируется альтернативно по одной из переменных ( или ) с другим фиксированным. Хотя одновременная минимизация по обоим и представляет собой сложную задачу двояковыпуклой оптимизации , минимизация только по одной из переменных представляет собой линейную задачу наименьших квадратов и может быть решена глобально и эффективно.
Полученный алгоритм оптимизации (называемый альтернативными проекциями) глобально сходится с линейной скоростью сходимости к локально оптимальному решению взвешенной задачи аппроксимации низкого ранга. Начальное значение для (или ) параметр должен быть задан. Итерация останавливается, когда удовлетворяется определенное пользователем условие сходимости.
Реализация в Matlab алгоритма переменных проекций для взвешенной низкоранговой аппроксимации:
функция [dh, f] = wlra_ap ( d, w, p, tol, maxiter ) [ m , n ] = размер ( d ); г = размер ( п , 2 ); ж = инф ; для i = 2 : минимизация maxiter % по L bp = kron ( eye ( n ), p ); vl = ( bp ' * w * bp ) \ bp ' * w * d (:); л = изменить форму ( вл , р , п ); % минимизация по P bl = kron ( l ' , eye ( m )); vp = ( bl ' * w * bl ) \ bl ' * w * d (:); п = изменить форму ( вп , м , р ); % проверить условие выхода dh = p * l ; дд = д - дч ; f ( i ) = dd (:) ' * w * dd (:); if abs ( f ( i - 1 ) - f ( i )) < tol , перерыв , конец endfor
Алгоритм переменных проекций
[ редактировать ]Алгоритм альтернативных проекций использует тот факт, что задача аппроксимации низкого ранга, параметризованная в форме изображения, является билинейной по переменным или . Билинейный характер задачи эффективно используется в альтернативном подходе, называемом переменными проекциями. [15]
Рассмотрим снова взвешенную задачу аппроксимации низкого ранга, параметризованную в форме изображения. Минимизация по отношению к переменной (линейная задача наименьших квадратов) приводит к замкнутому выражению ошибки аппроксимации как функции
Таким образом, исходная задача эквивалентна нелинейной задаче наименьших квадратов минимизации относительно . стандартные методы оптимизации, например алгоритм Левенберга-Марквардта Для этой цели можно использовать .
Реализация в Matlab алгоритма переменных проекций для взвешенной низкоранговой аппроксимации:
функция [dh, f] = wlra_varpro ( d, w, p, tol, maxiter ) проб = optimset (); проблема . решатель = 'lsqnonlin' ; проблема . options = optimset ( 'MaxIter' , maxiter , 'TolFun' , tol ); проблема . х0 = р ; проблема . цель = @( p ) Cost_fun ( p , d , w ); [ п , ж ] = lsqnonlin ( проблема ); [ ж , vl ] = Cost_fun ( п , d , ш ); dh = p * изменить форму ( vl , размер ( p , 2 ), размер ( d , 2 )); function [f, vl] = Cost_fun ( p, d, w ) bp = kron ( глаз ( размер ( d , 2 )), p ); vl = ( bp ' * w * bp ) \ bp ' * w * d (:); f = d (:) ' * w * ( d (:) - bp * vl );
Подход переменных проекций может быть применен также к задачам аппроксимации низкого ранга, параметризованным в форме ядра. Метод эффективен, когда количество исключаемых переменных значительно превышает количество переменных оптимизации, оставшихся на этапе нелинейной минимизации методом наименьших квадратов. Такие проблемы возникают при идентификации системы, параметризованной в форме ядра, где исключенные переменные являются аппроксимирующей траекторией, а оставшиеся переменные являются параметрами модели. В контексте линейных стационарных систем шаг исключения эквивалентен сглаживанию Калмана .
Вариант: выпукло-ограниченная аппроксимация низкого ранга.
[ редактировать ]Обычно мы хотим, чтобы наше новое решение не только имело низкий ранг, но и удовлетворяло другим выпуклым ограничениям, связанным с требованиями приложения. Наша интересующая проблема будет заключаться в следующем:
Эта задача имеет множество реальных приложений, в том числе для восстановления хорошего решения из неточного (полуопределенного программирования) релаксации. Если дополнительное ограничение является линейным, поскольку мы требуем, чтобы все элементы были неотрицательными, проблема называется структурированной аппроксимацией низкого ранга. [16] Более общая форма называется выпукло-ограниченной аппроксимацией низкого ранга.
Эта задача помогает решить многие проблемы. Однако это сложно из-за сочетания выпуклых и невыпуклых (низкоранговых) ограничений. Различные методы были разработаны на основе различных реализаций . Однако метод множителей чередующегося направления (ADMM) можно применить для решения невыпуклой задачи с выпуклой целевой функцией, ранговыми ограничениями и другими выпуклыми ограничениями. [17] и, таким образом, подходит для решения нашей вышеуказанной проблемы. Более того, в отличие от общих невыпуклых задач, ADMM гарантирует сходимость допустимого решения, если его двойственная переменная сходится на итерациях.
См. также
[ редактировать ]- Аппроксимация матрицы CUR производится из строк и столбцов исходной матрицы.
Ссылки
[ редактировать ]- ^ Э. Шмидт, К теории линейных и нелинейных интегральных уравнений, Math. 63 (1907), 433-476. два : 10.1007/BF01449770
- ^ К. Эккарт, Г. Янг, Приближение одной матрицы другой более низкого ранга. Психометрика, том 1, 1936, страницы 211–8. дои : 10.1007/BF02288367
- ^ Л. Мирский, Симметричные калибровочные функции и унитарно-инвариантные нормы, QJ Math. 11 (1960), 50–59. дои : 10.1093/qmath/11.1.50
- ^ Сребро, Натан; Яаккола, Томми (2003). Взвешенные низкоранговые аппроксимации (PDF) . ICML'03.
- ^ Разенштейн, Илья; Сун, Чжао; Вудрафф, Дэвид П. (2016). Взвешенные аппроксимации низкого ранга с доказуемыми гарантиями . STOC '16 Материалы сорок восьмого ежегодного симпозиума ACM по теории вычислений.
- ^ Кларксон, Кеннет Л.; Вудрафф, Дэвид П. (2013). Низкоранговая аппроксимация и регрессия во времени разреженности входных данных . STOC '13 Материалы сорок пятого ежегодного симпозиума ACM по теории вычислений. arXiv : 1207.6365 .
- ^ Нельсон, Джелани; Нгуен, Хай Л. (2013). OSNAP: более быстрые алгоритмы числовой линейной алгебры с помощью более разреженных вложений подпространства . ФОКС '13. arXiv : 1211.1002 .
- ^ Сарлос, Тамас (2006). Улучшенные алгоритмы аппроксимации больших матриц с помощью случайных проекций . ФОКС'06.
- ^ Сун, Чжао; Вудрафф, Дэвид П.; Чжун, Пейлинь (2017). Аппроксимация низкого ранга с погрешностью нормы L1 . STOC '17 Материалы сорок девятого ежегодного симпозиума ACM по теории вычислений. arXiv : 1611.00898 .
- ^ Брингманн, Карл; Колев, Павел; Вудрафф, Дэвид П. (2017). Алгоритмы аппроксимации L0-низкоранговой аппроксимации . НИПС'17. arXiv : 1710.11253 .
- ^ Кьерикетти, Флавио; Голлапуди, Шринивас; Кумар, Рави; Латтанци, Сильвио; Паниграхи, Рина; Вудрафф, Дэвид П. (2017). Алгоритмы Lp-аппроксимации низкого ранга . ICML'17. arXiv : 1705.06730 .
- ^ Бакши, Айнеш Л.; Вудрафф, Дэвид П. (2018). Низкоранговая аппроксимация матриц расстояний сублинейным временем . НейрИПС. arXiv : 1809.06986 .
- ^ Индик, Петр; Вакилиан, Али; Вагнер, Таль; Вудрафф, Дэвид П. (2019). Выборочно-оптимальная низкоранговая аппроксимация матриц расстояний . КОЛЬТ.
- ^ Буцидис, Христос; Вудрафф, Дэвид П.; Чжун, Пейлинь (2016). Оптимальный анализ главных компонентов в распределенных и потоковых моделях . СТОК. arXiv : 1504.06729 .
- ^ Г. Голуб и В. Перейра, Сепарабельный нелинейный метод наименьших квадратов: метод переменной проекции и его приложения, Институт физики, обратные задачи, том 19, 2003, страницы 1-26.
- ^ Чу, Муди Т.; Фундерлик, Роберт Э.; Племмонс, Роберт Дж. (2003). «структурированное низкоранговое приближение» . Линейная алгебра и ее приложения . 366 : 157–172. дои : 10.1016/S0024-3795(02)00505-0 .
- ^ «Общая система эвристического решения выпуклых задач над невыпуклыми множествами» (PDF) .
- М. Т. Чу, Р. Э. Фундерлик, Р. Дж. Племмонс, Структурированная аппроксимация низкого ранга, Линейная алгебра и ее приложения, том 366, 1 июня 2003 г., страницы 157–172 два : 10.1016/S0024-3795(02)00505-0