Завершение матрицы - Википедия - Matrix completion

Матричное завершение частично раскрытой матрицы 5 на 5 с рангом-1. Слева: наблюдается неполная матрица; Справа: результат завершения матрицы.

Завершение матрицы - это задача заполнения недостающих элементов частично наблюдаемой матрицы. Широкий спектр наборов данных естественным образом организован в матричную форму. Одним из примеров является матрица рейтингов фильмов, представленная в Проблема с Netflix: Дана матрица рейтингов, в которой каждая запись ${ displaystyle (я, j)}$ представляет рейтинг фильма ${ displaystyle j}$ заказчиком ${ displaystyle i}$ , если клиент ${ displaystyle i}$ смотрел фильм ${ displaystyle j}$ и отсутствует, мы хотели бы предсказать оставшиеся записи, чтобы дать клиентам хорошие рекомендации о том, что смотреть дальше. Другой пример - термодокументная матрица: Частота слов, используемых в коллекции документов, может быть представлена в виде матрицы, где каждая запись соответствует количеству раз, когда связанный термин встречается в указанном документе.

Без ограничений по количеству степени свободы в заполненной матрице эта задача недоопределенный поскольку скрытым записям могут быть присвоены произвольные значения. Таким образом, заполнение матрицы часто стремится найти наименьшее классифицировать матрица или, если известен ранг заполненной матрицы, матрица классифицировать ${ displaystyle r}$ что соответствует известным записям. На рисунке показано, что частично раскрытая матрица ранга 1 (слева) может быть заполнена с нулевой ошибкой (справа), поскольку все строки с пропущенными записями должны совпадать с третьей строкой. В случае проблемы Netflix ожидается, что матрица оценок будет иметь низкий рейтинг, поскольку предпочтения пользователей часто можно описать несколькими факторами, такими как жанр фильма и время выхода. Другие приложения включают в себя компьютерное зрение, при котором необходимо восстановить недостающие пиксели в изображениях, определение глобального позиционирования датчиков в сети на основе информации о частичном расстоянии и мультиклассовое обучение. Проблема пополнения матрицы в общем случае NP-жесткий, но при дополнительных предположениях существуют эффективные алгоритмы, которые с большой вероятностью достигают точной реконструкции.

С точки зрения статистического обучения, проблема заполнения матрицы - это приложение матричная регуляризация который является обобщением вектора регуляризация. Например, в задаче пополнения матрицы низкого ранга можно применить штраф за регуляризацию в виде ядерной нормы ${ Displaystyle R (X) = лямбда | X | _ {*}}$

Завершение матрицы низкого ранга

Один из вариантов задачи пополнения матрицы - найти наименьшее классифицировать матрица ${ displaystyle X}$ что соответствует матрице ${ displaystyle M}$ , которую мы хотим восстановить, для всех записей в наборе ${ displaystyle E}$ наблюдаемых записей. Математическая постановка этой задачи следующая:

{ displaystyle { begin {align} & { underset {X} { text {min}}} & { text {rank}} (X) & { text {subject to}} & X_ {ij} = M_ {ij} & ; ; forall i, j in E конец {выровнено}}}

Кандес и Рехт^[1] Доказано, что при допущениях о выборке наблюдаемых записей и достаточно большом количестве выбранных записей эта проблема имеет единственное решение с высокой вероятностью.

Эквивалентная формулировка при условии, что матрица ${ displaystyle M}$ подлежит восстановлению, как известно, из классифицировать ${ displaystyle r}$ , состоит в том, чтобы решить ${ displaystyle X}$ куда ${ Displaystyle X_ {ij} = M_ {ij} ; ; forall i, j in E}$

Предположения

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

Единая выборка наблюдаемых записей

Чтобы сделать анализ управляемым, часто предполагается, что набор ${ displaystyle E}$ наблюдаемых записей и фиксированных мощность выбирается равномерно случайным образом из совокупности всех подмножеств элементов мощности ${ displaystyle | E |}$ . Для дальнейшего упрощения анализа вместо этого предполагается, что ${ displaystyle E}$ построен Отбор проб Бернулли, т.е. что каждая запись наблюдается с вероятностью ${ displaystyle p}$ . Если ${ displaystyle p}$ установлен на ${ displaystyle { frac {N} {mn}}}$ куда ${ displaystyle N}$ желаемое ожидаемое мощность из ${ displaystyle E}$ , и ${ Displaystyle м, ; п}$ - размеры матрицы (пусть ${ Displaystyle м <п}$ не теряя общий смысл), ${ displaystyle | E |}$ внутри ${ Displaystyle О (п журнал п)}$ из ${ displaystyle N}$ с большой вероятностью, таким образом Выборка Бернулли является хорошим приближением для однородной выборки.^[1] Еще одно упрощение - предположить, что записи выбираются независимо и с заменой.^[2]

Нижняя граница количества наблюдаемых записей

Предположим, что ${ displaystyle m}$ к ${ displaystyle n}$ матрица ${ displaystyle M}$ (с ${ Displaystyle м <п}$ ) мы пытаемся восстановить классифицировать ${ displaystyle r}$ . Существует теоретико-информационная нижняя граница того, сколько записей должно быть соблюдено перед ${ displaystyle M}$ можно однозначно реконструировать. Набор ${ displaystyle m}$ к ${ displaystyle n}$ матрицы с рангом меньше или равным ${ displaystyle r}$ является алгебраическим многообразием в ${ Displaystyle { mathbb {C}} ^ {м раз п}}$ с размером ${ Displaystyle (п + м) р-р ^ {2}}$ . Используя этот результат, можно показать, что по крайней мере ${ displaystyle 4nr-4r ^ {2}}$ записи должны быть соблюдены для заполнения матрицы в ${ Displaystyle { mathbb {C}} ^ {п раз п}}$ иметь уникальное решение, когда ${ Displaystyle г Leq п / 2}$ .^[3]

Во-вторых, должна быть хотя бы одна наблюдаемая запись в каждой строке и столбце ${ displaystyle M}$ . В Разложение по сингулярным значениям из ${ displaystyle M}$ дан кем-то ${ Displaystyle U Sigma V ^ { dagger}}$ . Если строка ${ displaystyle i}$ незаметен, легко увидеть ${ displaystyle i ^ { text {th}}}$ правый сингулярный вектор ${ displaystyle M}$ , ${ displaystyle v_ {i}}$ , может быть изменено на какое-то произвольное значение и все равно дает соответствие матрицы ${ displaystyle M}$ над множеством наблюдаемых записей. Аналогично, если столбец ${ displaystyle j}$ не наблюдается, ${ displaystyle j ^ { text {th}}}$ левый сингулярный вектор ${ displaystyle M}$ , ${ displaystyle u_ {i}}$ может быть произвольным. Если мы предположим выборку Бернулли из набора наблюдаемых записей, Эффект сборщика купонов подразумевает, что записи в порядке ${ Displaystyle О (п журнал п)}$ должны соблюдаться, чтобы гарантировать, что есть наблюдение из каждой строки и столбца с высокой вероятностью.^[4]

Комбинируя необходимые условия и полагая, что ${ displaystyle r ll m, n}$ (допустимое предположение для многих практических приложений), нижняя граница количества наблюдаемых элементов, необходимых для предотвращения недоопределения проблемы завершения матрицы, составляет порядка ${ displaystyle nr log n}$ .

Несогласованность

Понятие бессвязности возникло в сжатое зондирование. Он вводится в контексте завершения матрицы, чтобы гарантировать наличие сингулярных векторов ${ displaystyle M}$ не являются слишком "разреженными" в том смысле, что все координаты каждого сингулярного вектора имеют сравнимую величину, а не только несколько координат, имеющих значительно большие величины.^[5]^[6] Стандартные базисные векторы тогда нежелательны в качестве сингулярных векторов, а вектор ${ displaystyle { frac {1} { sqrt {n}}} { begin {bmatrix} 1 1 vdots 1 end {bmatrix}}}$ в ${ Displaystyle mathbb {R} ^ {п}}$ желательно. В качестве примера того, что может пойти не так, если особые векторы достаточно "разрежены", рассмотрим ${ displaystyle m}$ к ${ displaystyle n}$ матрица ${ displaystyle { begin {bmatrix} 1 & 0 & cdots & 0 vdots && vdots 0 & 0 & 0 & 0 & 0 end {bmatrix}}}$ с разложение по сингулярным числам ${ displaystyle I_ {m} { begin {bmatrix} 1 & 0 & cdots & 0 vdots && vdots 0 & 0 & 0 & 0 end {bmatrix}} I_ {n}}$ . Практически все записи ${ displaystyle M}$ должен быть отобран, прежде чем его можно будет реконструировать.

Кандес и Рехт^[1] определить когерентность матрицы ${ displaystyle U}$ с пространство столбца ан ${ displaystyle r-}$ мерное подпространство ${ Displaystyle mathbb {R} ^ {п}}$ в качестве ${ displaystyle mu (U) = { frac {n} {r}} max _ {i$ , куда ${ displaystyle P_ {U}}$ ортогональный проекция на ${ displaystyle U}$ . Затем несогласованность утверждает, что с учетом разложение по сингулярным числам ${ Displaystyle U Sigma V ^ { dagger}}$ из ${ displaystyle m}$ к ${ displaystyle n}$ матрица ${ displaystyle M}$ ,

${ Displaystyle му (U), ; му (V) leq mu _ {0}}$
Записи ${ displaystyle sum _ {k} u_ {k} v_ {k} ^ { dagger}}$ имеют величины, ограниченные сверху ${ displaystyle mu _ {1} { sqrt { frac {r} {mn}}}}$

для некоторых ${ displaystyle mu _ {0}, ; mu _ {1}}$ .

Завершение матрицы низкого ранга с шумом

В реальных приложениях часто наблюдается повреждение всего нескольких записей, по крайней мере, из-за небольшого шума. Например, в проблеме Netflix рейтинги неопределенны. Candès и план ^[7] показали, что можно заполнить многие недостающие элементы больших матриц низкого ранга всего из нескольких зашумленных выборок путем минимизации ядерной нормы. Шумная модель предполагает, что мы наблюдаем

${ Displaystyle Y_ {ij} = M_ {ij} + Z_ {ij}, (i, j) in Omega,}$

куда ${ displaystyle {Z_ {ij} :( i, j) in Omega}}$ это шумовой термин. Обратите внимание, что шум может быть стохастическим или детерминированным. В качестве альтернативы модель может быть выражена как

${ Displaystyle P _ { Omega} (Y) = P _ { Omega} (M) + P _ { Omega} (Z),}$

куда ${ displaystyle Z}$ является ${ Displaystyle п раз п}$ матрица с записями ${ displaystyle Z_ {ij}}$ за ${ Displaystyle (я, j) в Omega}$ при условии, что ${ Displaystyle | P _ { Omega} (Z) | _ {F} leq delta}$ для некоторых ${ displaystyle delta> 0}$ .Чтобы восстановить неполную матрицу, мы пытаемся решить следующую задачу оптимизации:

${ displaystyle { begin {align} & { underset {X} { text {min}}} & | X | _ {*} & { text {subject to}} & | P_ { Omega} (XY) | _ {F} leq delta конец {выровнено}}}$

Среди всех матриц, согласующихся с данными, найдите матрицу с минимальной ядерной нормой. Candès и план ^[7] показали, что эта реконструкция точна. Они доказали, что когда происходит полное бесшумное восстановление, то пополнение матрицы устойчиво по отношению к возмущениям. Ошибка пропорциональна уровню шума. ${ displaystyle delta}$ . Следовательно, когда уровень шума мал, ошибка мала. Здесь проблема завершения матрицы не подчиняется свойству ограниченной изометрии (RIP). Для матриц RIP предполагает, что оператор выборки подчиняется

${ displaystyle (1- delta) | X | _ {F} ^ {2} leq { frac {1} {p}} | P _ { Omega} (X) | _ {F} ^ {2} leq (1+ delta) | X | _ {F} ^ {2}}$

для всех матриц ${ displaystyle X}$ с достаточно малым рангом и ${ displaystyle delta <1}$ Методы также применимы к проблемам восстановления разреженных сигналов, в которых RIP не выполняется.

Завершение матрицы высокого ранга

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

Эрикссон, Бальцано и Новак ^[8] рассмотрели проблему заполнения матрицы в предположении, что столбцы матрицы принадлежат объединению нескольких подпространств низкого ранга. Поскольку столбцы принадлежат объединению подпространств, проблема может рассматриваться как версия таблицы с отсутствующими данными. кластеризация подпространств проблема. Позволять ${ displaystyle X}$ быть ${ Displaystyle п раз N}$ матрица, (полные) столбцы которой лежат в объединении не более чем ${ displaystyle k}$ подпространства, каждое из ${ displaystyle rank leq r$ , и предположим ${ Displaystyle N gg kn}$ . Эрикссон, Бальцано и Новак ^[8] показал, что при мягких предположениях каждый столбец ${ displaystyle X}$ могут быть полностью восстановлены с высокой вероятностью из неполной версии, если хотя бы ${ Displaystyle CrN log ^ {2} (п)}$ записи ${ displaystyle X}$ наблюдаются равномерно случайно, причем ${ displaystyle C> 1}$ константа, зависящая от обычных условий некогерентности, геометрического расположения подпространств и распределения столбцов по подпространствам.

Алгоритм включает несколько шагов: (1) локальные окрестности; (2) локальные подпространства; (3) уточнение подпространства; (4) полное матричное завершение. Этот метод может быть применен для заполнения матрицы расстояния в Интернете и идентификации топологии.

Алгоритмы

Предлагались различные алгоритмы завершения матрицы.^[6] К ним относятся алгоритм на основе выпуклой релаксации,^[1] градиентный алгоритм,^[9] и альтернативный алгоритм, основанный на минимизации.^[10]

Выпуклое расслабление

Задача минимизации ранга такова: NP-жесткий. Один из подходов, предложенных Кандесом и Рехтом, заключается в создании выпуклый релаксация проблемы и минимизация ядерных норма ${ Displaystyle | М | _ {*}}$ (что дает сумму сингулярные значения из ${ displaystyle M}$ ) вместо ${ Displaystyle { текст {ранг}} (М)}$ (который считает количество ненулевых сингулярные значения из ${ displaystyle M}$ ).^[1] Это аналогично минимизации L1-норма а не L0-норма для векторов. В выпуклый релаксация может быть решена с помощью полуопределенное программирование (SDP), заметив, что проблема оптимизации эквивалентна

${ displaystyle { begin {align} & { underset {W_ {1}, W_ {2}} { text {min}}} && { text {trace}} (W_ {1}) + { text {trace}} (W_ {2}) & { text {subject to}} && X_ {ij} = M_ {ij} ; ; forall i, j in E &&& { begin {bmatrix } W_ {1} & X X ^ {T} & W_ {2} end {bmatrix}} successq 0 end {выровнено}}}$

Сложность использования SDP для решения выпуклой релаксации ${ Displaystyle О ({ текст {макс}} (м, п) ^ {4})}$ . Современные решатели, такие как SDP3, могут обрабатывать только матрицы размером до 100 на 100. ^[11] Альтернативным методом первого порядка, который приближенно решает выпуклую релаксацию, является алгоритм пороговой обработки сингулярных значений, введенный Каем, Кандесом и Шеном.^[11]

Кандес и Рехт показывают, используя исследование случайных величин на Банаховы пространства, что если количество наблюдаемых записей порядка ${ displaystyle max { { mu _ {1} ^ {2}, { sqrt { mu _ {0}}} mu _ {1}, mu _ {0} n ^ {0.25} }} nr log n}$ (без ограничения общности предположим ${ Displaystyle м <п}$ ) задача минимизации ранга имеет единственное решение, которое также является решением его выпуклой релаксации с вероятностью ${ displaystyle 1 - { frac {c} {n ^ {3}}}}$ для некоторой постоянной ${ displaystyle c}$ . Если ранг ${ displaystyle M}$ маленький ( ${ displaystyle r leq { frac {n ^ {0.2}} { mu _ {0}}}}$ ) размер набора наблюдений уменьшается до порядка ${ displaystyle mu _ {0} n ^ {1.2} r log n}$ . Эти результаты близки к оптимальным, поскольку минимальное количество элементов, которые необходимо соблюдать, чтобы проблема пополнения матрицы не была недооценена, составляет порядка ${ displaystyle nr log n}$ .

Этот результат был улучшен Кандесом и Тао.^[4] Они достигают оценок, которые отличаются от оптимальных только на полилогарифмический факторов, усиливая предположения. Вместо свойства некогерентности они предполагают свойство сильной некогерентности с параметром ${ displaystyle mu _ {3}}$ . Это свойство утверждает, что:

${ displaystyle | langle e_ {a}, P_ {U} e_ {a '} rangle - { frac {r} {m}} 1_ {a = a'} | leq mu _ {3} { frac { sqrt {r}} {m}}}$ за ${ displaystyle a, a ' leq m}$ и ${ displaystyle | langle e_ {b}, P_ {U} e_ {b '} rangle - { frac {r} {n}} 1_ {b = b'} | leq mu _ {3} { frac { sqrt {r}} {n}}}$ за ${ displaystyle b, b ' leq n}$
Записи ${ Displaystyle сумма _ {я} и_ {я} v_ {я} ^ { кинжал}}$ ограничены по величине ${ displaystyle mu _ {3} { sqrt { frac {r} {mn}}}}$

Интуитивно сильная непоследовательность матрицы ${ displaystyle U}$ утверждает, что ортогональные проекции стандартных базисных векторов на ${ displaystyle U}$ имеет величины, которые имеют высокую вероятность, если сингулярные векторы были распределены случайным образом.^[5]

Кандес и Тао обнаруживают, что когда ${ displaystyle r}$ является ${ displaystyle O (1)}$ и количество наблюдаемых записей порядка ${ Displaystyle му _ {3} ^ {4} п ( журнал п) ^ {2}}$ , задача минимизации ранга имеет единственное решение, которое также оказывается решением его выпуклой релаксации с вероятностью ${ displaystyle 1 - { frac {c} {n ^ {3}}}}$ для некоторой постоянной ${ displaystyle c}$ . Для произвольных ${ displaystyle r}$ , количество наблюдаемых элементов, достаточное для выполнения этого утверждения, порядка ${ displaystyle mu _ {3} ^ {2} nr ( log n) ^ {6}}$

Градиентный спуск

Кешаван, Монтанари и Ох^[9] рассмотрим вариант заполнения матрицы, где классифицировать из ${ displaystyle m}$ к ${ displaystyle n}$ матрица ${ displaystyle M}$ , который подлежит восстановлению, как известно ${ displaystyle r}$ . Они предполагают Отбор проб Бернулли записей, постоянное соотношение сторон ${ displaystyle { frac {m} {n}}}$ , ограниченное количество записей ${ displaystyle M}$ (пусть верхняя оценка будет ${ displaystyle M _ { text {max}}}$ ), а постоянная номер условия ${ displaystyle { frac { sigma _ {1}} { sigma _ {r}}}}$ (куда ${ displaystyle sigma _ {1}}$ и ${ displaystyle sigma _ {r}}$ самые большие и самые маленькие сингулярные значения из ${ displaystyle M}$ соответственно). Далее они предполагают, что два условия некогерентности выполняются ${ displaystyle mu _ {0}}$ и ${ displaystyle mu _ {1} { frac { sigma _ {1}} { sigma _ {r}}}}$ куда ${ displaystyle mu _ {0}}$ и ${ displaystyle mu _ {1}}$ являются константами. Позволять ${ displaystyle M ^ {E}}$ быть матрицей, которая соответствует ${ displaystyle M}$ на съемочной площадке ${ displaystyle E}$ наблюдаемых записей и 0 в других местах. Затем они предлагают следующий алгоритм:

Подрезать ${ displaystyle M ^ {E}}$ удалив все наблюдения из столбцов со степенью больше, чем ${ displaystyle { frac {2 | E |} {n}}}$ установив для записей в столбцах значение 0. Аналогичным образом удалите все наблюдения из строк со степенью больше, чем ${ displaystyle { frac {2 | E |} {n}}}$ .
Проект ${ displaystyle M ^ {E}}$ на свой первый ${ displaystyle r}$ основные компоненты. Полученную матрицу назовем ${ displaystyle { text {Tr}} (M ^ {E})}$ .
Решать ${ displaystyle min _ {X, Y} min _ {S in mathbb {R} ^ {r times r}} { frac {1} {2}} sum _ {i, j in E} (M_ {ij} - (XSY ^ { dagger}) _ {ij}) ^ {2} + rho G (X, Y)}$ куда ${ Displaystyle G (X, Y)}$ есть некоторые регуляризация функция градиентный спуск с линейный поиск. Инициализировать ${ Displaystyle X, ; Y}$ в ${ Displaystyle X_ {0}, ; Y_ {0}}$ куда ${ displaystyle { text {Tr}} (M_ {E}) = X_ {0} S_ {0} Y_ {0} ^ { dagger}}$ . Набор ${ Displaystyle G (X, Y)}$ как некоторая функция, заставляющая ${ Displaystyle X, ; Y}$ оставаться некогерентным на протяжении всего градиентного спуска, если ${ displaystyle X_ {0}}$ и ${ displaystyle Y_ {0}}$ бессвязны.
Возвращаться матрица ${ displaystyle XSY ^ { dagger}}$ .

Шаги 1 и 2 алгоритма дают матрицу ${ displaystyle { text {Tr}} (M ^ {E})}$ очень близко к истинной матрице ${ displaystyle M}$ (измеряется среднеквадратичная ошибка (RMSE) с большой вероятностью. В частности, с вероятностью ${ displaystyle 1 - { frac {1} {n ^ {3}}}}$ , ${ displaystyle { frac {1} {mnM _ { text {max}} ^ {2}}} | M - { text {Tr}} (M ^ {E}) | _ {F} ^ { 2} leq C { frac {r} {m | E |}} { sqrt { frac {m} {n}}}}$ для некоторой постоянной ${ displaystyle C}$ . ${ Displaystyle | cdot | _ {F}}$ обозначает Фробениуса норма. Обратите внимание, что полный набор предположений не требуется для того, чтобы этот результат был верным. Например, условие некогерентности применяется только при точной реконструкции. Наконец, хотя обрезка может показаться нелогичной, поскольку включает в себя отбрасывание информации, она обеспечивает проецирование ${ displaystyle M ^ {E}}$ на свой первый ${ displaystyle r}$ основные компоненты дает больше информации о базовой матрице ${ displaystyle M}$ чем о наблюдаемых записях.

На шаге 3 пространство матриц-кандидатов ${ Displaystyle X, ; Y}$ можно уменьшить, заметив, что внутренняя задача минимизации имеет то же решение для ${ displaystyle (X, Y)}$ что касается ${ displaystyle (XQ, YR)}$ куда ${ displaystyle Q}$ и ${ displaystyle R}$ находятся ортонормированный ${ displaystyle r}$ к ${ displaystyle r}$ матрицы. потом градиентный спуск может выполняться над перекрестное произведение из двух Многообразия Грассмана. Если ${ displaystyle r ll m, ; n}$ и наблюдаемый набор записей находится в порядке ${ displaystyle nr log n}$ , матрица, возвращенная на шаге 3, в точности равна ${ displaystyle M}$ . Тогда алгоритм является оптимальным по порядку, поскольку мы знаем, что для задачи пополнения матрицы не должно быть недоопределенный количество записей должно быть в порядке ${ displaystyle nr log n}$ .

Минимизация альтернативных наименьших квадратов

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

${ displaystyle X = UV ^ {T}}$ ;

алгоритм затем чередует поиск лучших ${ displaystyle U}$ и лучший ${ displaystyle V}$ . Хотя общая проблема невыпуклая, каждая подзадача обычно является выпуклой и может быть решена эффективно. Джайн, Нетрапалли и Сангхави ^[10] дали одну из первых гарантий выполнения попеременной минимизации как для завершения матрицы, так и для определения матрицы.

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

${ displaystyle { begin {align} & { underset {U, V in mathbb {R} ^ {n times k}} { text {min}}} & | P _ { Omega} (UV ^ {T}) - P _ { Omega} (M) | _ {F} ^ {2} конец {выровнено}}}$

Алгоритм AltMinComplete, предложенный Джайном, Нетрапалли и Сангхави, представлен здесь:^[10]

Вход: наблюдаемый набор ${ displaystyle Omega}$ , значения ${ Displaystyle P _ { Omega} (М)}$
Раздел ${ displaystyle Omega}$ в ${ displaystyle 2T + 1}$ подмножества ${ displaystyle Omega _ {0}, cdots, Omega _ {2T}}$ с каждым элементом ${ displaystyle Omega}$ принадлежащий одному из ${ displaystyle Omega _ {t}}$ с равной вероятностью (выборка с заменой)
${ displaystyle { hat {U}} ^ {0} = SVD ({ frac {1} {p}} P _ { Omega _ {0}} (M), k)}$ т.е. верхний ${ displaystyle k}$ левые особые векторы ${ displaystyle { frac {1} {p}} P _ { Omega _ {0}} (M)}$
Вырезка: Установить все элементы ${ displaystyle { hat {U}} ^ {0}}$ которые имеют величину больше, чем ${ displaystyle { frac {2 mu { sqrt {k}}} { sqrt {n}}}}$ к нулю и ортонормировать столбцы ${ displaystyle { hat {U}} ^ {0}}$
за ${ Displaystyle т = 0, cdots, Т-1}$ делать
${ displaystyle quad { hat {V}} ^ {t + 1} leftarrow { text {argmin}} _ {V in mathbb {R} ^ {n times k}} | P _ { Омега _ {t + 1}} ({ hat {U}} V ^ {T} -M) | _ {F} ^ {2}}$
${ displaystyle quad { hat {U}} ^ {t + 1} leftarrow { text {argmin}} _ {U in mathbb {R} ^ {m times k}} | P _ { Омега _ {T + t + 1}} (U ({ hat {V}} ^ {t + 1}) ^ {T} -M) | _ {F} ^ {2}}$
конец для
Возвращаться ${ displaystyle X = { hat {U}} ^ {T} ({ hat {V}} ^ {T}) ^ {T}}$

Они показали, что наблюдая ${ displaystyle | Omega | = O (({ frac { sigma _ {1} ^ {*}} { sigma _ {k} ^ {*}}}) ^ {6} k ^ {7} журнал п журнал (k | M | _ {F} / epsilon))}$ случайные элементы некогерентной матрицы ${ displaystyle M}$ , Алгоритм AltMinComplete может восстанавливать ${ displaystyle M}$ в ${ Displaystyle О ( журнал (1 / эпсилон))}$ шаги. По сложности выборки ( ${ displaystyle | Omega |}$ ), теоретически чередующаяся минимизация может потребовать большего ${ displaystyle Omega}$ чем выпуклая релаксация. Однако эмпирически это кажется не так, что подразумевает, что границы сложности выборки могут быть еще более жесткими. Что касается временной сложности, они показали, что AltMinComplete требует времени.

${ Displaystyle О (| Омега | к ^ {2} журнал (1 / эпсилон))}$ .

Следует отметить, что, хотя методы, основанные на выпуклой релаксации, имеют строгий анализ, алгоритмы на основе альтернативной минимизации более успешны на практике.^{[нужна цитата ]}

Приложения

Кандес и План резюмируют несколько применений завершения матрицы.^[7] следующее:

Совместная фильтрация

Совместная фильтрация Это задача автоматического прогнозирования интересов пользователя путем сбора информации о вкусовых качествах многих пользователей. Такие компании, как Apple, Amazon, Barnes and Noble и Netflix, пытаются предсказать свои пользовательские предпочтения на основе частичного знания. В такого рода задачах завершения матрицы неизвестная полная матрица часто считается низким рангом, потому что только несколько факторов обычно влияют на вкусы или предпочтения человека.

Идентификация системы

При контроле хотелось бы приспособиться к дискретной линейной инвариантной во времени модели в пространстве состояний.

${ Displaystyle { begin {align} x (t + 1) & = Ax (t) + Bu (t) y (t) & = Cx (t) + Du (t) end {align}}}$

к последовательности входов ${ Displaystyle и (т) в mathbb {R} ^ {m}}$ и выходы ${ Displaystyle у (т) в mathbb {R} ^ {p}, т = 0, ldots, N}$ . Вектор ${ Displaystyle х (т) в mathbb {R} ^ {п}}$ состояние системы во время ${ displaystyle t}$ и ${ displaystyle n}$ это порядок модели системы. Из пары ввода / вывода хотелось бы восстановить матрицы ${ displaystyle A, B, C, D}$ и начальное состояние ${ Displaystyle х (0)}$ . Эту проблему также можно рассматривать как проблему пополнения матриц низкого ранга.

Локализация Интернета вещей (IoT)

Проблема локализации (или глобального позиционирования) возникает естественным образом в сенсорных сетях IoT. Проблема в том, чтобы восстановить карту сенсора в Евклидово пространство от локального или частичного набора попарных расстояний. Таким образом, это задача завершения матрицы с рангом два, если датчики расположены в 2-D плоскости, и с тремя, если они находятся в 3-D пространстве.^[12]