Аппроксимация низкого ранга

В математике низкоранговая аппроксимация - это задача минимизации , в которой функция стоимости измеряет соответствие между заданной матрицей (данными) и аппроксимирующей матрицей (переменная оптимизации) при условии, что аппроксимирующая матрица имеет пониженный ранг . Задача используется для математического моделирования и сжатия данных . Ограничение ранга связано с ограничением сложности модели, которая соответствует данным. В приложениях часто существуют другие ограничения на аппроксимирующую матрицу, помимо ограничения ранга, например неотрицательность и ганкелевская структура .

Аппроксимация низкого ранга тесно связана с:

• анализ главных компонент ,
• факторный анализ ,
• Всего наименьших квадратов ,
• латентно-семантический анализ и
• ортогональная регрессия .

Определение [ править ]

Дано

• спецификация конструкции ,${\ displaystyle {\ mathcal {S}}: \ mathbb {R} ^ {n_ {p}} \ to \ mathbb {R} ^ {m \ times n}}$
• вектор параметров конструкции ,${\ displaystyle p \ in \ mathbb {R} ^ {n_ {p}}}$
• норма , и${\ Displaystyle \ | \ cdot \ |}$
• желаемый ранг ,${\ displaystyle r}$

${\ displaystyle {\ text {minim}} \ quad {\ text {over}} {\ widehat {p}} \ quad \ | p - {\ widehat {p}} \ | \ quad {\ text {при условии} } \ quad \ operatorname {rank} {\ big (} {\ mathcal {S}} ({\ widehat {p}}) {\ big)} \ leq r.}$

Приложения [ править ]

• Идентификация линейной системы , в этом случае аппроксимирующая матрица имеет структуру Ганкеля . ^{[1] [2]}
• Машинное обучение , и в этом случае аппроксимирующая матрица имеет нелинейную структуру. ^[3]
• Рекомендательные системы , в которых матрица данных имеет пропущенные значения и приближение категориально .
• Завершение матрицы расстояний , и в этом случае существует ограничение положительной определенности.
• Обработка естественного языка , и в этом случае приближение неотрицательно .
• Компьютерная алгебра , в этом случае приближение структурировано Сильвестром .

Основная задача аппроксимации низкого ранга [ править ]

Неструктурированная задача с подгонкой, измеряемой нормой Фробениуса , т. Е.

${\ displaystyle {\ text {minim}} \ quad {\ text {over}} {\ widehat {D}} \ quad \ | D - {\ widehat {D}} \ | _ {\ text {F}} \ quad {\ text {при условии}} \ quad \ operatorname {rank} {\ big (} {\ widehat {D}} {\ big)} \ leq r}$

имеет аналитическое решение с точки зрения сингулярного разложения матрицы данных. Результат называется леммой о матричной аппроксимации или теоремой Эккарта – Юнга – Мирского . ^[4] Пусть

${\displaystyle D=U\Sigma V^{\top }\in \mathbb {R} ^{m\times n},\quad m\geq n}$

разложение сингулярного значения и перегородки , и следующим образом :${\displaystyle D}$${\displaystyle U}$${\displaystyle \Sigma =:\operatorname {diag} (\sigma _{1},\ldots ,\sigma _{m})}$${\displaystyle V}$

${\displaystyle U=:{\begin{bmatrix}U_{1}&U_{2}\end{bmatrix}},\quad \Sigma =:{\begin{bmatrix}\Sigma _{1}&0\\0&\Sigma _{2}\end{bmatrix}},\quad {\text{and}}\quad V=:{\begin{bmatrix}V_{1}&V_{2}\end{bmatrix}},}$

где есть , есть и есть . Тогда матрица рангов , полученная из усеченного разложения по сингулярным числам${\displaystyle U_{1}}$${\displaystyle m\times r}$${\displaystyle \Sigma _{1}}$${\displaystyle r\times r}$${\displaystyle V_{1}}$${\displaystyle n\times r}$${\displaystyle r}$

${\displaystyle {\widehat {D}}^{*}=U_{1}\Sigma _{1}V_{1}^{\top },}$

таково, что

${\displaystyle \|D-{\widehat {D}}^{*}\|_{\text{F}}=\min _{\operatorname {rank} ({\widehat {D}})\leq r}\|D-{\widehat {D}}\|_{\text{F}}={\sqrt {\sigma _{r+1}^{2}+\cdots +\sigma _{m}^{2}}}.}$

Минимизатор уникален тогда и только тогда, когда .${\displaystyle {\widehat {D}}^{*}}$${\displaystyle \sigma _{r+1}\neq \sigma _{r}}$

Доказательство теоремы Эккарта – Юнга – Мирского (для спектральной нормы ) [ править ]

Позвольте быть реальной (возможно, прямоугольной) матрицей с . Предположим, что ${\displaystyle A\in \mathbb {R} ^{m\times n}}$${\displaystyle m\geq n}$

${\displaystyle A=U\Sigma V^{\top }}$

это разложение по сингулярным значениям из . Напомним, что и - ортогональные матрицы, а - диагональная матрица с такими элементами , что .${\displaystyle A}$${\displaystyle U}$${\displaystyle V}$${\displaystyle \Sigma }$${\displaystyle m\times n}$ ${\displaystyle (\sigma _{1},\sigma _{2},\cdots ,\sigma _{n})}$${\displaystyle \sigma _{1}\geq \sigma _{2}\geq \cdots \geq \sigma _{n}\geq 0}$

Мы утверждаем, что наилучшее ранговое приближение к в спектральной норме, обозначаемое как , дается выражением${\displaystyle k}$${\displaystyle A}$${\displaystyle \|\cdot \|_{2}}$

${\displaystyle A_{k}=\sum _{i=1}^{k}\sigma _{i}u_{i}v_{i}^{\top }}$

где и обозначают ый столбец и соответственно.${\displaystyle u_{i}}$${\displaystyle v_{i}}$${\displaystyle i}$${\displaystyle U}$${\displaystyle V}$

Во-первых, обратите внимание, что у нас есть

${\displaystyle \|A-A_{k}\|_{2}=\left\|\sum _{i=k+1}^{n}\sigma _{i}u_{i}v_{i}^{\top }\right\|_{2}=\sigma _{k+1}}$

Следовательно, нам нужно показать, что если где и есть столбцы, то .${\displaystyle B_{k}=XY^{\top }}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle k}$${\displaystyle \|A-A_{k}\|_{2}=\sigma _{k+1}\leq \|A-B_{k}\|_{2}}$

Поскольку имеет столбцы, то должна быть нетривиальная линейная комбинация первых столбцов , т. Е.${\displaystyle Y}$${\displaystyle k}$${\displaystyle k+1}$${\displaystyle V}$

${\displaystyle w=\gamma _{1}v_{1}+\cdots +\gamma _{k+1}v_{k+1},}$

такой что . Не умаляя общности, мы можем масштабировать так или (что эквивалентно) . Следовательно,${\displaystyle Y^{\top }w=0}$${\displaystyle w}$${\displaystyle \|w\|_{2}=1}$${\displaystyle \gamma _{1}^{2}+\cdots +\gamma _{k+1}^{2}=1}$

${\displaystyle \|A-B_{k}\|_{2}^{2}\geq \|(A-B_{k})w\|_{2}^{2}=\|Aw\|_{2}^{2}=\gamma _{1}^{2}\sigma _{1}^{2}+\cdots +\gamma _{k+1}^{2}\sigma _{k+1}^{2}\geq \sigma _{k+1}^{2}.}$

Результат получается извлечением квадратного корня из обеих частей указанного неравенства.

Доказательство теоремы Эккарта – Юнга – Мирского (для нормы Фробениуса ) [ править ]

Позвольте быть реальной (возможно, прямоугольной) матрицей с . Предположим, что${\displaystyle A\in \mathbb {R} ^{m\times n}}$${\displaystyle m\geq n}$

${\displaystyle A=U\Sigma V^{\top }}$

это разложение по сингулярным значениям из .${\displaystyle A}$

Мы утверждаем, что наилучшее ранговое приближение к в норме Фробениуса, обозначаемое как , дается выражением${\displaystyle k}$${\displaystyle A}$${\displaystyle \|\cdot \|_{F}}$

${\displaystyle A_{k}=\sum _{i=1}^{k}\sigma _{i}u_{i}v_{i}^{\top }}$

где и обозначают ый столбец и соответственно.${\displaystyle u_{i}}$${\displaystyle v_{i}}$${\displaystyle i}$${\displaystyle U}$${\displaystyle V}$

Во-первых, обратите внимание, что у нас есть

${\displaystyle \|A-A_{k}\|_{F}^{2}=\left\|\sum _{i=k+1}^{n}\sigma _{i}u_{i}v_{i}^{\top }\right\|_{F}^{2}=\sum _{i=k+1}^{n}\sigma _{i}^{2}}$

Следовательно, нам нужно показать, что если где и есть столбцы, то${\displaystyle B_{k}=XY^{\top }}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle k}$

${\displaystyle \|A-A_{k}\|_{F}^{2}=\sum _{i=k+1}^{n}\sigma _{i}^{2}\leq \|A-B_{k}\|_{F}^{2}.}$

По неравенству треугольника со спектральной нормой, если тогда . Предположим, что и соответственно обозначают приближение ранга к и по методу SVD, описанному выше. Тогда для любого${\displaystyle A=A'+A''}$${\displaystyle \sigma _{1}(A)\leq \sigma _{1}(A')+\sigma _{1}(A'')}$${\displaystyle A'_{k}}$${\displaystyle A''_{k}}$${\displaystyle k}$${\displaystyle A'}$${\displaystyle A''}$${\displaystyle i,j\geq 1}$

${\displaystyle {\begin{aligned}\sigma _{i}(A')+\sigma _{j}(A'')&=\sigma _{1}(A'-A'_{i-1})+\sigma _{1}(A''-A''_{j-1})\\&\geq \sigma _{1}(A-A'_{i-1}-A''_{j-1})\\&\geq \sigma _{1}(A-A_{i+j-2})\qquad ({\text{since }}{\rm {rank}}(A'_{i-1}+A''_{j-1})\leq {\rm {rank\,}}(A_{i+j-2}))\\&=\sigma _{i+j-1}(A).\end{aligned}}}$

Поскольку , когда и заключаем, что для${\displaystyle \sigma _{k+1}(B_{k})=0}$${\displaystyle A'=A-B_{k}}$${\displaystyle A''=B_{k}}$${\displaystyle i\geq 1,j=k+1}$

${\displaystyle \sigma _{i}(A-B_{k})\geq \sigma _{k+i}(A).}$

Следовательно,

${\displaystyle \|A-B_{k}\|_{F}^{2}=\sum _{i=1}^{n}\sigma _{i}(A-B_{k})^{2}\geq \sum _{i=k+1}^{n}\sigma _{i}(A)^{2}=\|A-A_{k}\|_{F}^{2},}$

как требуется.

Взвешенные задачи аппроксимации низкого ранга [ править ]

Норма Фробениуса равномерно взвешивает все элементы ошибки аппроксимации . Предварительные знания о распределении ошибок могут быть приняты во внимание, рассматривая взвешенную задачу аппроксимации низкого ранга${\displaystyle D-{\widehat {D}}}$

${\displaystyle {\text{minimize}}\quad {\text{over }}{\widehat {D}}\quad \operatorname {vec} ^{\top }(D-{\widehat {D}})W\operatorname {vec} (D-{\widehat {D}})\quad {\text{subject to}}\quad \operatorname {rank} ({\widehat {D}})\leq r,}$

где векторизует матрицу по столбцам и является заданной положительной (полу) определенной весовой матрицей.${\displaystyle vec(A)}$ ${\displaystyle A}$${\displaystyle W}$

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

В случае некоррелированных весов задача взвешенной аппроксимации низкого ранга также может быть сформулирована следующим образом: ^{[5] [6]} для неотрицательной матрицы и матрицы, которую мы хотим минимизировать по матрицам, ранга не выше .${\displaystyle W}$${\displaystyle A}$${\displaystyle \sum _{i,j}(W_{i,j}(A_{i,j}-B_{i,j}))^{2}}$${\displaystyle B}$${\displaystyle r}$

Проблемы аппроксимации низкого ранга с точки зрения входа ${\displaystyle L_{p}}$[ править ]

Пусть . Ибо самый быстрый алгоритм выполняется за время. ^{[7] [8]} Одна из важных использованных идей - это забвение вложенных подпространств (OSE), она впервые была предложена Сарлосом. ^[9]${\displaystyle \|A\|_{p}=\left(\sum _{i,j}|A_{i,j}^{p}|\right)^{1/p}}$${\displaystyle p=2}$${\displaystyle nnz(A)+n\cdot poly(k/\epsilon )}$

В самом деле, известно, что эта начальная норма L1 более устойчива, чем норма Фробениуса при наличии выбросов, и указывается в моделях, где предположения Гаусса относительно шума могут не применяться. Стремление к минимизации естественно . ^[10] Для и есть несколько алгоритмов с доказуемыми гарантиями. ^{[11] [12]}${\displaystyle p=1}$${\displaystyle \|B-A\|_{1}}$${\displaystyle p=0}$${\displaystyle p\geq 1}$

Проблема аппроксимации низкого ранга расстояния [ править ]

Позвольте и быть двумя точечными множествами в произвольном метрическом пространстве. Позвольте представить матрицу где . Такие матрицы расстояний обычно вычисляются в программных пакетах и ​​имеют приложения для изучения многообразий изображений, распознавания почерка и многомерного развертывания. В попытке уменьшить размер их описания ^{[13] [14]} можно изучить низкоранговую аппроксимацию таких матриц.${\displaystyle P=\{p_{1},\ldots ,p_{m}\}}$${\displaystyle Q=\{q_{1},\ldots ,q_{n}\}}$${\displaystyle A}$${\displaystyle m\times n}$${\displaystyle A_{i,j}=dist(p_{i},q_{i})}$

Распределенная / потоковая проблема аппроксимации низкого ранга [ править ]

Проблемы аппроксимации низкого ранга в распределенной и потоковой среде рассмотрены в ^[15].

Изображение и ядро ​​представления ограничений ранга [ править ]

Используя эквивалентности

${\displaystyle \operatorname {rank} ({\widehat {D}})\leq r\quad \iff \quad {\text{there are }}P\in \mathbb {R} ^{m\times r}{\text{ and }}L\in \mathbb {R} ^{r\times n}{\text{ such that }}{\widehat {D}}=PL}$

а также

${\displaystyle \operatorname {rank} ({\widehat {D}})\leq r\quad \iff \quad {\text{there is full row rank }}R\in \mathbb {R} ^{m-r\times m}{\text{ such that }}R{\widehat {D}}=0}$

взвешенная задача аппроксимации низкого ранга становится эквивалентной задачам оптимизации параметров

${\displaystyle {\text{minimize}}\quad {\text{over }}{\widehat {D}},P{\text{ and }}L\quad \operatorname {vec} ^{\top }(D-{\widehat {D}})W\operatorname {vec} (D-{\widehat {D}})\quad {\text{subject to}}\quad {\widehat {D}}=PL}$

а также

${\displaystyle {\text{minimize}}\quad {\text{over }}{\widehat {D}}{\text{ and }}R\quad \operatorname {vec} ^{\top }(D-{\widehat {D}})W\operatorname {vec} (D-{\widehat {D}})\quad {\text{subject to}}\quad R{\widehat {D}}=0\quad {\text{and}}\quad RR^{\top }=I_{r},}$

где - единичная матрица размера .${\displaystyle I_{r}}$${\displaystyle r}$

Алгоритм альтернативных проекций [ править ]

Представление в виде изображения рангового ограничения предлагает метод оптимизации параметров, в котором функция стоимости минимизируется поочередно по одной из переменных ( или ) с фиксированной другой. Хотя одновременная минимизация по обоим параметрам и является сложной задачей двояковыпуклой оптимизации , минимизация по одной только одной из переменных представляет собой линейную задачу наименьших квадратов и может быть решена глобально и эффективно.${\displaystyle P}$${\displaystyle L}$${\displaystyle P}$${\displaystyle L}$

Результирующий алгоритм оптимизации (называемый чередующимися проекциями) глобально сходится с линейной скоростью сходимости к локально оптимальному решению взвешенной задачи аппроксимации низкого ранга. Необходимо указать начальное значение параметра (или ). Итерация останавливается, когда удовлетворяется определенное пользователем условие сходимости.${\displaystyle P}$${\displaystyle L}$

Реализация в Matlab алгоритма чередующихся проекций для взвешенного низкорангового приближения:

функция [dh, f] = wlra_ap ( d, w, p, tol, maxiter ) [ m , n ] = размер ( d ); r = размер ( p , 2 ); f = inf ;          для i = 2 : maxiter    % минимизации над L bp = крон ( глаз ( n ), p );    vl = ( bp ' * w * bp ) \ bp ' * w * d (:);             l = изменить форму ( vl , r , n );     % минимизации над P bl = крон ( l ' , глаз ( м ));    vp = ( bl ' * w * bl ) \ bl ' * w * d (:);             p = изменить форму ( vp , m , r );     % проверить условие выхода dh = p * l ; дд = д - дх ;          f ( я ) = дд (:) ' * ш * дд (:);       если abs ( f ( i - 1 ) - f ( i )) < tol , break , end         конец

Алгоритм переменных проекций [ править ]

Алгоритм чередующихся проекций использует тот факт, что задача аппроксимации низкого ранга, параметризованная в форме изображения, является билинейной по переменным или . Билинейный характер проблемы эффективно используется в альтернативном подходе, называемом переменными проекциями. ^[16]${\displaystyle P}$${\displaystyle L}$

Рассмотрим снова взвешенную задачу аппроксимации низкого ранга, параметризованную в форме изображения. Минимизация по переменной (линейная задача наименьших квадратов) приводит к выражению в замкнутой форме ошибки аппроксимации как функции${\displaystyle L}$${\displaystyle P}$

${\displaystyle f(P)={\sqrt {\operatorname {vec} ^{\top }(D){\Big (}W-W(I_{n}\otimes P){\big (}(I_{n}\otimes P)^{\top }W(I_{n}\otimes P){\big )}^{-1}(I_{n}\otimes P)^{\top }W{\Big )}\operatorname {vec} (D)}}.}$

Таким образом, исходная задача эквивалентна нелинейной задаче наименьших квадратов минимизации по . Для этого можно использовать стандартные методы оптимизации, например, алгоритм Левенберга-Марквардта .${\displaystyle f(P)}$${\displaystyle P}$

Реализация в Matlab алгоритма переменных проекций для взвешенной низкоранговой аппроксимации:

функция [dh, f] = wlra_varpro ( d, w, p, tol, maxiter ) prob = optimset (); Проб . solver = 'lsqnonlin' ;     Проб . options = optimset ( 'MaxIter' , maxiter , 'TolFun' , tol ); Проб . х0 = р ; Проб . objective = @ ( p ) cost_fun ( p , d , w );              [ Р , е ] = lsqnonlin ( пробы ); [ f , vl ] = cost_fun ( p , d , w ); dh = p * reshape ( vl , size ( p , 2 ), size ( d , 2 ));                   функция [f, vl] = cost_fun ( p, d, w ) bp = крон ( глаз ( размер ( d , 2 )), p );    vl = ( bp ' * w * bp ) \ bp ' * w * d (:);            f = d (:) ' * w * ( d (:) - bp * vl );          

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

Вариант: выпукло-ограниченное приближение низкого ранга [ править ]

Обычно мы хотим, чтобы наше новое решение было не только низкого ранга, но и удовлетворяло другим выпуклым ограничениям из-за требований приложения. Наша интересующая проблема будет заключаться в следующем:

${\displaystyle {\text{minimize}}\quad {\text{over }}{\widehat {p}}\quad \|p-{\widehat {p}}\|\quad {\text{subject to}}\quad \operatorname {rank} {\big (}{\mathcal {S}}({\widehat {p}}){\big )}\leq r{\text{ and }}g({\widehat {p}})\leq 0}$

У этой проблемы есть много приложений в реальном мире, в том числе для восстановления хорошего решения из неточного (полуопределенного программирования) релаксации. Если дополнительное ограничение является линейным, например, мы требуем, чтобы все элементы были неотрицательными, проблема называется структурированным приближением низкого ранга. ^[17] Более общая форма называется выпукло-ограниченной аппроксимацией низкого ранга.${\displaystyle g({\widehat {p}})\leq 0}$

Эта проблема помогает при решении многих проблем. Однако это сложно из-за комбинации выпуклых и невыпуклых (низкого ранга) ограничений. На основе разных реализаций были разработаны разные техники . Однако метод множителей с переменным направлением (ADMM) может применяться для решения невыпуклой задачи с выпуклой целевой функцией, ранговыми ограничениями и другими выпуклыми ограничениями ^[18] и, таким образом, подходит для решения нашей вышеупомянутой проблемы. Более того, в отличие от общих невыпуклых задач, ADMM гарантирует сходимость допустимого решения до тех пор, пока его двойственная переменная сходится в итерациях.${\displaystyle g({\widehat {p}})\leq 0}$

См. Также [ править ]

• Аппроксимация матрицы CUR производится по строкам и столбцам исходной матрицы.

Ссылки [ править ]

• MT Chu, RE Funderlic, RJ Plemmons, Структурированная аппроксимация низкого ранга, Линейная алгебра и ее приложения, Том 366, 1 июня 2003 г., страницы 157–172 doi : 10.1016 / S0024-3795 (02) 00505-0

Внешние ссылки [ править ]

• Пакет C ++ для приближения структурированного низкого ранга