Низкоранговое приближение

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

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

Определение

Данный

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

${\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{minimize}}\quad {\text{over }}{\widehat {D}}\quad \|D-{\widehat {D}}\|_{\text{F}}\quad {\text{subject to}}\quad \operatorname {rank} {\big (}{\widehat {D}}{\big )}\leq r$

имеет аналитическое решение в терминах по сингулярным значениям разложения матрицы данных . Результат называется леммой о матричной аппроксимации или теоремой Эккарта–Янга–Мирского . Первоначально эту проблему решил Эрхард Шмидт. в бесконечномерном контексте интегральных операторов (хотя его методы легко обобщаются на произвольные компактные операторы в гильбертовых пространствах) и позже переоткрыты К. Эккартом и Г. Янгом . Л. Мирский обобщил результат на произвольные унитарно-инвариантные нормы. Позволять

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

быть разложением по сингулярным значениям $D$, где $\Sigma =:\operatorname {diag} (\sigma _{1},\ldots ,\sigma _{m})$ это $m\times m$ прямоугольная диагональная матрица с сингулярными значениями $\sigma _{1}\geq \ldots \geq \sigma _{m}$. Для данного $r\in \{1,\dots ,m-1\}$, раздел $U$, $\Sigma$, и $V$ следующее:

$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}},$

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

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

таков, что

$\|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}}}.$

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

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

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

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

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

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

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

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

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

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

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

С $Y$ имеет $k$ столбцов, то должна существовать нетривиальная линейная комбинация первых $k+1$ столбцы $V$, то есть,

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

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

$\|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}.$

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

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

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

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

представляет собой по сингулярным значениям разложение $A$.

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

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

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

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

$\|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}$

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

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

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

${\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 i+j-2))\\&=\sigma _{i+j-1}(A).\end{aligned}}$

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

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

Поэтому,

$\|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},$

по мере необходимости.

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

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

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

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

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

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

По входу L _p задачи аппроксимации низкого ранга

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

Для $p=1$, известно, что эта норма L1 по входу более устойчива, чем норма Фробениуса при наличии выбросов, и указывается в моделях, где гауссовские предположения о шуме могут не применяться. Естественно стремиться свести к минимуму $\|B-A\|_{1}$. Для $p=0$ и $p\geq 1$, существуют алгоритмы с доказуемыми гарантиями.

Задача аппроксимации низкого ранга по расстоянию

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

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

Рассмотрены задачи аппроксимации низкого ранга в распределенной и потоковой постановке.

Представления изображений и ядер ограничений ранга

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

$\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$

и

$\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$

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

${\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$

и

${\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},$

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

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

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

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

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

function [dh, f] = wlra_ap(d, w, p, tol, maxiter)
[m, n] = size(d); r = size(p, 2); f = inf;
for i = 2:maxiter
    % minimization over L
    bp = kron(eye(n), p);
    vl = (bp' * w * bp) \ bp' * w * d(:);
    l  = reshape(vl, r, n);
    % minimization over P
    bl = kron(l', eye(m));
    vp = (bl' * w * bl) \ bl' * w * d(:);
    p  = reshape(vp, m, r);
    % check exit condition
    dh = p * l; dd = d - dh;
    f(i) = dd(:)' * w * dd(:);
    if abs(f(i - 1) - f(i)) < tol, break, end
endfor

Алгоритм переменных проекций

Алгоритм альтернативных проекций использует тот факт, что задача аппроксимации низкого ранга, параметризованная в форме изображения, является билинейной по переменным $P$ или $L$. Билинейный характер задачи эффективно используется в альтернативном подходе, называемом переменными проекциями.

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

$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)}}.$

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

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

function [dh, f] = wlra_varpro(d, w, p, tol, maxiter)
prob = optimset(); prob.solver = 'lsqnonlin';
prob.options = optimset('MaxIter', maxiter, 'TolFun', tol); 
prob.x0 = p; prob.objective = @(p) cost_fun(p, d, w);
[p, f ] = lsqnonlin(prob); 
[f, vl] = cost_fun(p, d, w); 
dh = p * reshape(vl, size(p, 2), size(d, 2));

function [f, vl] = cost_fun(p, d, w)
bp = kron(eye(size(d, 2)), p);
vl = (bp' * w * bp) \ bp' * w * d(:);
f = d(:)' * w * (d(:) - bp * vl);

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

Вариант: выпукло-ограниченная аппроксимация низкого ранга.

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

${\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$

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

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

См. также

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

Ссылки

• М. Т. Чу, Р. Э. Фундерлик, Р. Дж. Племмонс, Структурированная аппроксимация низкого ранга, Линейная алгебра и ее приложения, том 366, 1 июня 2003 г., страницы 157–172 два : 10.1016/S0024-3795(02)00505-0

Внешние ссылки

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