매트릭스 완료

행렬 완료는 부분적으로 관측된 행렬의 누락된 항목을 채우는 작업이다.다양한 데이터셋이 자연스럽게 매트릭스 형태로 구성된다.넷플릭스 문제에서 볼 수 있는 것처럼 영화배열 매트릭스가 한 예다.각 항목$({\displaystyle i}$, ${\displaystyle j}$) ${\displaystyle (i,j)}$이(가) $고객{\displaystyle }$ i ${\displaystyle i}$에 의한 $영화{\displaystyle }$ j ${\displaystyle j}$의 등급을 나타내는$$ 등급 매트릭스를 고려할 때$,$ 고객 $i{\displaystyle }$ ${\$$displaystyle i}$을($가$$)$ 보고$$${\displaystyle }$ 다른$$ 방법으로 누락된 경우, 나머지 항목을 순서대로 예측하려고 한다.다음에 무엇을 볼 것인가에 대해 고객에게 좋은 추천을 하기 위해서입니다.또 다른 예는 용어-문서 행렬이다.문서 모음에서 사용되는 단어의 빈도는 매트릭스로 나타낼 수 있으며, 여기서 각 항목은 표시된 문서에 관련 용어가 나타나는 횟수에 해당된다.

완료된 행렬의 자유도에 대한 제한 없이 이 문제는 숨겨진 항목에 임의의 값이 할당될 수 있기 때문에 충분히 결정되지 않는다.따라서 우리는 행렬이 최대 결정 인자를 가지고 있거나, 양수 확정이거나, 순위가 낮다고 가정하는 것과 같이 잘 조정된 문제를 만들기 위해 행렬에 대한 가정을 요구한다.^[1][2]

예를 들어, 행렬이 낮은 순위 구조를 가지고 있다고 가정하고 가장 낮은 순위 행렬을 찾거나, 완성된 행렬의 순위를 알고 있는 경우 알려진 항목과 일치하는$$ 순위 $r{\displaystyle }$ ${\displaystyle r}$ 행렬을 찾을 수 있다.그림에서는 누락된 항목이 있는 모든 행이 세 번째 행과 같아야 하므로 부분적으로 드러난 순위 1 행렬(왼쪽)을 제로 오류(오른쪽)로 완료할 수 있음을 보여준다.넷플릭스 문제의 경우 영화 장르나 개봉 시간 등 몇 가지 요인으로 사용자 선호도를 설명할 수 있는 경우가 많아 등급 매트릭스가 낮은 순위로 예상된다.다른 애플리케이션으로는 이미지에서 누락된 픽셀을 재구성해야 하는 컴퓨터 비전, 부분 거리 정보로부터 네트워크 내 센서의 글로벌 위치 탐지, 멀티클라스 학습 등이 있다.매트릭스 완료 문제는 일반적으로 NP-hard이지만, 추가 가정에서는 높은 확률로 정확한 재구성을 달성하는 효율적인 알고리즘이 있다.

통계학 학습의 관점에서, 매트릭스 완성 문제는 벡터 정규화의 일반화인 매트릭스 정규화의 적용이다.예를 들어, 낮은 순위의 매트릭스 완성 문제에서는 핵 $규범{\displaystyle }$ ${\displaystyle R}$( X${\displaystyle }$)${\displaystyle }$= ${\displaystyle \lambda }$ ${\displaystyle X{\Vert }_{}}$ $∗{\$\ X\$_{*}$의 형태를 취하여 정규화 페널티를 적용할 수 있다.

낮은 순위 매트릭스 완료

매트릭스 완료 문제의 변형 중 하나는 관찰된 항목의$$ $집합{\displaystyle }$ E ${\displaystyle E}$에 있는 모든 항목에 대해 $복구$하려는 매트릭스 M {\$displaystyle$ M$}$과$($와$)$ 일치하는 최하위 $매트릭스{\displaystyle }$ X ${\displaystyle X}$를 찾는 것이다.이 문제의 수학적 공식은 다음과 같다.

${\displaystyle {\begin{aigned}&{\underset {X}{\text{min}}}&#{\text{lank}\&#{n1}의 대상}&#X_{ij}=M_{ij}&\;\\all i,j\in E\\end{aigned}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}"$

캔디스와 레흐트는^[3] 관측된 항목과 표본 추출된 항목들의 표본 추출에 대한 가정을 통해 이 문제가 높은 확률의 고유한 해결책을 가지고 있음을 증명했다.

An equivalent formulation, given that the matrix ${\displaystyle M}$ to be recovered is known to be of rank ${\displaystyle r}$, is to solve for ${\displaystyle X}$ where ${\displaystyle X_{ij}=M_{ij}\;\;\forall i,j\in E}$

가정

관측된 항목의 샘플링과 샘플링된 항목 수에 대한 여러 가지 가정을 자주 수행하여 분석을 단순화하고 문제가 충분히 결정되지 않도록 한다.

관측된 항목의 균일한 샘플링

분석을 추적가능하게 하기 위해, 관측된 항목과 고정된 카디널리티의$$ $설정{\displaystyle }$ E ${\displaystyle E}$이(가) ${\displaystyle 카디널리티}$ E${\displaystyle }${\$displaystyle E}$의 모든 하위 집합의 수집에서 무작위로 균일하게 샘플링된다고 가정한다$.$ 대신 분석을 더욱 단순화하기 위해 $E{\displaystyle }$ ${\displaystylement$ E}로 가정한다.$E}$은(는) 베르누이 샘플링에 의해 생성된다$$. 즉, 각 항목이 확률 $p{\displaystyle }$ ${\displaystyle$ p}을$($를) 사용하여 관찰되는 경우$.$ $p{\displaystyle }$ ${\displaystyle$ $p$$}$이(가$)$ ${\displaystyle \frac{Nm}{}}$ ${\displaystyle \frac{n}{}}$ ${\$$displaystystyle$$${\$frac{n}}}}}$로 설정되면, 여기서$$$$ $N$은 $E{\displaystyle }${\$displaystystystystystyturestyturestyleasestyleasestyleasestyleasestyone$}$$$및$ m${\displaystyle }$, {$\$daystyturestyt$m,\;n}$은(는) 행렬의 치수(일반성 없이 m$<$ {\$displaystyle$ m$<n}),$ ${\displaystyle E}$ ${\displaystyle \{\backslash }$$displaystyle$ E ${\displaystyle \}}$은(는) $N{\displaystyle }$ ${\displaystyle N}$의 $(n\log$n) 내에 있으며$$ 높은$$ 확률로 있으므로 베르누이 균일한 샘플링에 대한 좋은 근사치이다.^[3]또 다른 단순화는 항목이 독립적으로 대체되어 샘플링된다고 가정하는 것이다.^[4]

관찰된 항목 수에 대한 하한

$우리$가 복구하려고 하는 m <$>$의 n$$ {\$displaystyle n}$ 행렬$$ $M{\displaystyle }$ {\$displaystyle M}($< n {\$displaystyle m<n}$ 포함이 $r{\displaystyle }$ ${\displaystyle r}$ 등급이라고 가정합시다$.$$M{\displaystyle }$ ${\displaystyle M}$을(를) 고유하게 재구성하기 전에 얼마나$$ 많은 항목을 관찰해야 하는지에 대한 정보 이론적 하한이 있다.The set of ${\displaystyle m}$ by ${\displaystyle n}$ matrices with rank less than or equal to ${\displaystyle r}$ is an algebraic variety in ${\displaystyle {\mathbb {C} }^{m\times n}}$with dimension ${\displaystyle (n+m)r-r^{2}}$. Using this result, one can show that a$r{\displaystyle }$ ${\displaystyle \le n}$/ ${\displaystyle 2\mathrm{}}$ ${\$$displaystyle$ $r$${\displaystyle \backslash {re-2\mathrm{}}^{}}${${\displaystyle {\mathrm{nr-4r}}^{}}$$^{2}}$개의$$ 매트릭스 완료 항목을 ${\displaystyle {Cn}^{}}$ ${\displaystyle {\times }^{}}$ n ${\$의 항목에서 관찰해야$$ r nn / 2 {\$displaystystyle$ r$\leq n/$^[5]2}일 때 고유한 솔루션을 가질 수 있다.

Secondly, there must be at least one observed entry per row and column of ${\displaystyle M}$. The singular value decomposition of ${\displaystyle M}$ is given by ${\displaystyle U\Sigma V^{\dagger }}$. If row ${\displaystyle i}$ is unobserved, it is easy to see the ${\displaystyle i^{\text{$$th$$}}}}$ M의 $우측{\displaystyle }$단수 벡터$,$ ${\displaystyle v_{}}$ $i{\displaystyle {}_{}}$ ${\$은(는) 임의의 값으로 변경할 수 있으며, 관찰된 항목 집합에 $걸쳐$ M$${\$displaystyle M$}과(와) 일치하는 행렬을 생성할 수 있다.마찬가지로, 열 $j{\displaystyle }$ ${\displaystyle j}$이(가) 관측되지 않는$$ 경우, j ${\displaystyle {\text{th}}^{}}$ ${\$ j$^{\text{th}}}$의 왼쪽 단수 $벡터$인 M$${\$displaysty M$ ${\displaystyle u_{}}$ i$${\$displaysty u_{i}}}$이(가)가 임의적일 수 있다$$.관찰된 항목 집합의 베르누이를 샘플링한다고 가정할 $경우{\displaystyle }$ 쿠폰 수집기 효과는${\displaystyle }$O(${\displaystyle n}$ log$){\displaystyle$ O$(n\log$ n$)}$의 순서를 준수하여 각 행과 컬럼에서 높은 확률로 관찰이 이루어지도록 해야 함을$$ 의미한다.^[6]

필요한 ${\displaystyle \mathrm{조건}}$을 결합하고 ${\displaystyle r}$ ${\displaystyle \ll }$ m${\displaystyle }$, n ${\displaystyle r\ll m,n}($많은 실제 적용에 대한 유효한 가정)을 가정하면, 매트릭스 완료 문제가 과소 결정되는 것을 방지하기 위해 필요한 관찰 항목 수에 대한 하한이 n r ${\displaystyle \mathrm{로그}\log }$ n ${\displaystyle nr\log n}$의 순서에 있다$.$

불순수

일관성이라는 개념은 압축된 감지에서 생겨났다.$M{\displaystyle }$ ${\displaystyle M}$의 단수 벡터가 각 단수 벡터의 모든 좌표가 현저하게 큰 몇 개의 좌표 대신 비교 가능한 크기의 것이라는 점에서 너무 "분수"가$$ 되지 않도록 하기 위해 매트릭스 완료의 맥락에서 도입된다.^[7][8]표준 기준 벡터는 단수 벡터로 바람직하지 않으며, R $n{\displaystyle {\mathbb{}}^{}}$ ${\\$ ${\$$\\\1\$1\end$\1$\1$\nd{bmatrix$$}}}}}}$은(으)의 벡터${\displaystyle \frac{}{}\frac{\sqrt{1n}}{}}$$}$이 바람직하다$$.만약 단수 벡터 충분히" 성기다"무엇이 잘못될 것인가에 관한 예로서,;\cdots, 0\\\vdots &,&\vdots \\0&, 0&, 0&, 0\end{bmatrix}}}& n{n\displaystyle}매트릭스[10⋯ 0⋮ ⋮ 0000]{\displaystyle{\begin{bmatrix}1&amp이 m{m\displaystyle};0&amp을 고려해 보세요. 단수 값 decomposi과tion [ 1 0 ${\$0&$0\end{bmatrix}}}}}}$$I_{n$ $M{\displaystyle }$ ${\displaystyle M}$의 거의 모든 항목을 샘플링해야$$ 재구성할 수 있다.

Candès and Recht^[3] define the coherence of a matrix ${\displaystyle U}$ with column space an ${\displaystyle r-}$dimensional subspace of ${\displaystyle \mathbb {R} ^{n}}$ as ${\displaystyle \mu (U)={\frac {n}{r}}\max _{i<n}\ P_{$$U}e_{i}\ ^{2}}$, where ${\displaystyle P_{U}}$ is the orthogonal projection onto ${\displaystyle U}$. Incoherence then asserts that given the singular value decomposition ${\displaystyle U\Sigma V^{\dagger }}$ of the ${\displaystyle m}$ by ${\displaystyle n}$ matrix ${\displaystyle M}$$$,

1. ${\displaystyle \mu(U),\;\mu(V)\leq \mu _{0}}$
2. $\sum {\displaystyle \underset{k}{}}$ ${\displaystyle \underset{}{}{}_{}}$ ${\displaystyle {}_{}{}_{}^{}}$ $†{\$의 항목에는 ${\displaystyle {\mu \mathrm{}}_{}}$ 1 ${\displaystyle \sqrt{\frac{\mathrm{rm}}{}}}$ n ${\$}{\$sqrt{r}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$만큼의 크기가 상한으로 지정되어 있다$$.

일부 ${\displaystyle {\mu \mathrm{}}_{}}$ 0${\displaystyle {}_{}}$ ${\displaystyle \mu {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$

낮은 순위 매트릭스(노이즈 포함) 완료

실제 세계 애플리케이션에서는 최소 소량의 노이즈로 인해 손상된 항목 몇 개만 관찰하는 경우가 많다.예를 들어 넷플릭스 문제에서는 시청률이 불확실하다.칸데스와 플랜은 핵 규범 최소화를 통해 소음이 많은 샘플 몇 개에서 대규모 하위 행렬의 누락된 많은 항목들을 채울 수 있다는 것을 보여주었다.시끄러운 모델은 우리가 관찰하는 것으로 가정한다.

${\displaystyle Y_{ij}=M_{ij}+Z_{ij}(i,j)\in \Oomega ,}$

여기서 Z ${\displaystyle i_{}}$ ${\displaystyle j_{}}$:${\displaystyle }$( ${\displaystyle i}$, ${\displaystyle j}$) ${\displaystyle \in }$ ${\displaystyle \mathrm{\Omega }}$ ${\$은 잡음 용어다$$.소음은 확률론적이거나 결정론적일 수 있다는 점에 유의하십시오.또는 모델은 다음과 같이 표현될 수 있다.

${\displaystyle P_{\Oomega }(Y)=P_{\Oomega }}(M)+P_{\Oomega }(Z),}$

어디 Z{Z\displaystyle}항목이 있는 n×n{\displaystyle n\times의 스녀}매트릭스 Z나는 j{\displaystyle Z_{ij}}에(나는, j)∈ Ω{\displaystyle(i,j)\in \Omega}가정은 ‖ PΩ(Z)‖ F≤ δ{\displaystyle)P_{\Omega}(Z)\ _{F}\leq \delta}을 위한 δ>0{\displaystyle \delta하다.;0}불완전한 매트릭스를 복구하기 위해 다음과 같은 최적화 문제를 해결하려고 한다.

${\displaystyle {\begin{aigned}&{\underset {X}{\text{min}}\\\\\n\\text{nowleder}}\{*}\p_\\\P_\\Oomega}(X-Y)\{F}\leq \delta \\ended}}}}}}}}}}}}}}}}}}$

데이터와 일치하는 모든 행렬 중에서 핵 규범이 최소인 행렬을 찾아라.칸디스와 플랜은 이 재구성이 정확하다는 것을 보여주었다.그들은 완벽한 소리 없는 회복이 일어났을 때 매트릭스 완성이 육안으로 볼 때 안정적이라는 것을 증명했다.오류는 소음 수준 $\Delta {\displaystyle }$ ${\displaystyle \delta }$에 비례하므로 소음 수준이 작을 때는 오류가 작다$.$여기서 행렬 완료 문제는 제한된 등거리 특성(RIP)을 준수하지 않는다.행렬의 경우, RIP는 샘플링 운영자가 준수한다고 가정할 것이다.

${\displaystyle (1-\delta )\ X\ _{F}^{2}\leq {\frac {1}{p}\ P_{\Oomega }(X)\ _{F}^{2}\leq (1+\delta )\ X\{F}^{F}2}}:$

모든 행렬 $X{\displaystyle }$ ${\displaystyle X}$에 대해, 가충분히 Δ < 1 {\displaystyle $\delta$ <1}이$(가$) 충분히 작다.이 방법은 RIP가 유지되지 않는 희박한 신호 복구 문제에도 적용할 수 있다.

상위행렬완료

일반적으로 상위 매트릭스 완성은 NP-하드다.그러나 특정 가정에서는 불완전한 상위 매트릭스 또는 전체 순위 매트릭스를 완료할 수 있다.

에릭손, 발자노, 노왁은 매트릭스의 기둥이 복수의 하위 영역의 결합에 속한다는 가정 하에 매트릭스를 완성하는 문제를 고려했다.열은 서브스페이스 조합에 속하므로 서브스페이스 클러스터링 문제의 데이터 누락 버전으로 볼 수 있다.X{X\displaystyle} n의(완전한)기둥이 노조의 각 r의 오빠 k≤ r<>대부분의 k{k\displaystyle}subspaces, n{\displaystylerank\leq r<, n}로 유지된다면×N{\displaystyle n\times N} 행렬과 N≫ kn{\displaystyle N\gg kn}를 취하다 할게. 에릭손, Balzano과 노워크 씨[10] 된 것은 온화하다assumptiOns X{X\displaystyle}의 각 칼럼 완벽하게 높은 확률과 불완전한 버전을 너무 오랫동안으로 적어도 Cr할 수 있는 N로그 2⁡(n){\displaystyle CrN\log{2^}(n)}항목의 X{X\displaystyle}관찰되지 않게 무작위로,과 함께 C1{\displaystyle C> 1} 일정에 맞추기 위해서는그는 usu연속성 조건, 서브스페이스의 기하학적 배열 및 서브스페이스에 대한 컬럼 분포.

알고리즘에는 (1) 지역 근린, (2) 지역 서브 스페이스, (3) 하위 공간 미세화, (4) 전체 매트릭스 완료 등의 몇 단계가 포함된다.이 방법은 인터넷 거리 매트릭스 완료 및 위상 식별에 적용할 수 있다.

저등급 매트릭스 완성을 위한 알고리즘

다양한 매트릭스 완성 알고리즘이 제안되었다.^[8]여기에는 볼록 이완 기반 알고리즘,^[3] 그라데이션 기반 알고리즘 및 ^[11]교번 최소화 기반 알고리즘이 포함된다.^[12]

볼록 이완

순위 최소화 문제는 NP-hard이다.One approach, proposed by Candès and Recht, is to form a convex relaxation of the problem and minimize the nuclear norm ${\displaystyle \ M\ _{*}}$ (which gives the sum of the singular values of ${\displaystyle M}$) instead of ${\displaystyle {\text{rank}}(M)}$ (which counts the number of non zero sing$M{\displaystyle }$ ${\displaystyle M}$의 ular 값.$$^[3]이는 벡터에 대한 L0 표준이 아닌 L1 표준의 최소화와 유사하다.볼록한 이완은 최적화 문제가 다음과 동등하다는 것을 알아채면 세미드파이널 프로그래밍(SDP)을 이용하여 해결할 수 있다.

${\displaystyle {\begin{aligned}&{\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}}\succeq 0\ended}}}$

는 볼록 완화를 해결하기 위해 SDP를 사용하는 복잡성은 O(max(m, n)4){\displaystyle O({\text{max}}(m,n)^{4})}. SDP3 같은 예술 해결사들의 상태만 100[13]크기의 100까지 매트릭스 처리할 수 있는 대략은 볼록 완화를 해결한다 다른 하나의 대안은 첫번째 주문 방법은 특이한 값 Thresholding AlgorCai, Candés, Shen에 의해 소개되었다.^[13]

Candès and Recht show, using the study of random variables on Banach spaces, that if the number of observed entries is on the order of ${\displaystyle \max {\{\mu _{1}^{2},{\sqrt {\mu _{0}}}\mu _{1},\mu _{0}n^{0.25}\}}nr\log n}$ (assume without loss of generality M<>n{\displaystyle m<, n}), 순위 최소화 문제는 볼록 완화의 해결책 가능성 어떤 상수 c{\displaystyle c}을 위해 1− cn3{\displaystyle 1-{\frac{c}{n^{3}}}}. M{M\displaystyle}의 계급은 작다(r≤ n0에 무슨 일이 독특한 해결책을 가지고 있다.2${\$${{}}{\mu _{0}}}}}}$ $관측치$ 집합의 크기가 ${\displaystyle {\mu \mathrm{}}_{}}$ ${\displaystyle {0\mathrm{n}}^{}}$ ${\displaystyle {}^{}}$.2 ${\displaystyle r}$ 로그 ${\displaystyle }$ ${\displaystyle n}$ ${\displaystyle \mu$ _${0}n^{1$}1의 순서로 감소한다$.$$2}r\log$ n$\}.$매트릭스 완료 문제가 충분히 결정되지 않기 위해 관찰되어야 하는 최소 항목 수는 $n{\displaystyle }$ ${\displaystyle r}$ ${\displaystyle \log }$ ${\displaystyle n}$ ${\displaystyle nr\logn}$의 순서에 있으므로 이러한 결과는 거의 최적에 가깝다$.$

이 결과는 칸데스와 타오에 의해 개선되었다.^[6]그들은 가정을 강화함으로써 다변량 인자에 의해서만 최적의 한계와 다른 한계를 달성한다.이 속성은 일관성 속성 대신 매개변수 ${\$를 사용하여 강한 일관성 속성을 가정한다$.$ 이 속성은 다음과 같이 명시한다.

1. $displaystyle \langle e_{a$$U}e_{a'}\rangle -{\frac {r}{m}}1_{a=a'} \leq \mu _{3}{\frac {\sqrt {r}}{m}}}$ for ${\displaystyle a,a'\leq m}$ and ${\displaystyle \langle e_{b},P_{$$U$$}e_{b'}\$$rangele$$-{\frac {r}{n1}_{b=b'} \leq \mu _{3}{\frac{\sqrt{r}{n}}},$ ${\displaystyle {}^{},}$ b$,$≤ $≤{\displaystystystyleqn}$
2. $\sum {\displaystyle \underset{}{}}$ ${\displaystyle \underset{}{i}}$ ${\displaystyle {}_{}{}_{}^{}}$ v ${\displaystyle i_{}^{}}$† ${\$의 항목은$$ $\mu {\displaystyle {}_{}}$ ${\displaystyle \sqrt{\frac{3rm}{}}}$ ${\displaystyle \sqrt{\frac{n}{}}}$ ${\$

직관적으로 $매트릭스{\displaystyle }$ U ${\displaystyle U}$의 강한 일관성은 U {\$displaystyle U}$에 대한 표준 기준 벡터의 직교 투영 크기가 단수 벡터가 랜덤하게 분포된 경우 높은 가능성을 갖는다고$$ 주장한다$$.^[7]

Candès and Tao find that when ${\displaystyle r}$ is ${\displaystyle O(1)}$ and the number of observed entries is on the order of ${\displaystyle \mu _{3}^{4}n(\log n)^{2}}$, the rank minimization problem has a unique solution which also happens to be the solution of its convex relaxationwith probability ${\displaystyle 1-{\frac {c}{n^{3}}}}$ for some constant ${\displaystyle c}$. For arbitrary ${\displaystyle r}$, the number of observed entries sufficient for this assertion hold true is on the order of ${\displaystyle \mu _{3}^{2}nr(\log n)^{6}}$

그라데이션 강하

Keshavan, Montanari, Oh는^[11] 매트릭스 완료의 변형으로 간주되며$,$ $여기$서 회수될 $매트릭스{\displaystyle }$ $M$의 등급은 $n{\displaystyle }$ ${\displaystyle$ $n$$}$ 매트릭스$$ M ${\\displaystyle$ $r}$인 것으로 알려져 있다$.$They assume Bernoulli sampling of entries, constant aspect ratio ${\displaystyle {\frac {m}{n}}}$, bounded magnitude of entries of ${\displaystyle M}$ (let the upper bound be ${\displaystyle M_{\text{max}}}$), and constant condition number ${\displaystyle {\frac {\sigma _{1}}{\sigma _$${{r}}}}($여기서 $\sigma {\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$ $_{$$1}$및$$ ${\displaystyle {\sigma }_{}}$ r ${\$ _${r$})은$$ 각각$$ $M{\displaystyle }$ ${\displaystyle M}$의 가장 크고 작은 단수 값이다.또한$$, 그들은 두 개의 불순성 조건이 $\mu {\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$ 및$$ $\mu {\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}\frac{{}_{}}{}}$ ${\displaystyle \frac{{1\mathrm{}}_{}}{}}$ ${\displaystyle \frac{{}_{}}{{}_{}}}$ ${\displaystyle \frac{r_{}}{}}$ ${\$$1$}{1$}{\sigma _{1$}{${\displaystyle {1\mathrm{}}_{}}$$}}{$1$}}{\$로 만족한다고 가정한다.$M{\displaystyle {}^{}}$ ${\displaystyle E^{}}$ ${\$ M$^{E}$를 관측된 항목의$$ 설정 $E{\displaystyle }$ ${\displaystyle E}$에 있는 $M{\displaystyle }$ ${\displaystyle M}$과(와) 일치시키고 다른 곳에 0이 되도록 한다$$.그런 다음 다음과 같은 알고리즘을 제안한다.

1. ${\displaystyle \frac{2En}{}}$ ${\$보다 큰 열의 모든 관측치를 제거하여$$ $열의{\displaystyle {}^{}}$ 항목을 0으로 설정하여$$ 잘라내십시오.마찬가지로 ${\displaystyle \frac{2En}{}}$ ${\$보다 큰 행에서 모든 관측치를 제거하십시오$.$
2. 첫$$ $번째{\displaystyle }$ r ${\$$displaystyle$ $r}$$$주성분에 프로젝트 M E {\$displaystyle$ M^{$E}.$결과 행렬 Tr (${\displaystyle \text{M}}$ ${\displaystyle E^{}}$ ) $displaystyle {\text{Tr}}(M^{E})$을 호출하십시오$.$
3. Solve ${\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)}$ where ${\displaystyle G(X,Y)}$ is some regularizati선 검색과 함께 구배 강하로 기능하는.$X{\displaystyle {}_{}}$ ${\displaystyle 0_{}}$에서 $X{\displaystyle }$, ${\displaystyle Y}$ ${\displaystyle X,\;Y}$ 초기화${\displaystyle {}_{}}$ ${\displaystyle {Y\mathrm{}}_{}}$ ${\displaystyle 0{}_{}}$ ${\$${\displaystyle \text{여기}}$서 $Tr($${\displaystyle M_{}}$$$E${\displaystyle {}_{}}$)${\displaystyle }$= ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}{}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle {}_{}{}_{}^{}}$ ${\displaystyle {0\mathrm{}}_{}^{}}$ {\$displaystyle {\text${Tr$}}(M_{E})=$X_{$0}$$S_{0}Y_{0}^{\dagger }}$. Set ${\displaystyle G(X,Y)}$ as some function forcing ${\displaystyle X,\;Y}$ to remain incoherent throughout gradient descent if ${\displaystyle X_{0}}$ and ${\displaystyle Y_{0}}$ are incoherent.
4. $매트릭스{\displaystyle }$ X $†{\$}{\displaystyle $XSY^{\dager }}}$을(를) 반환하십시오$.$

알고리즘의 1단계와 2단계에서는 높은 확률로 Tr (${\displaystyle {}^{}}$ ${\displaystyle E^{}}$) ${\displaystyle {\Tr}(M^{E})$이 참 행렬 $M{\displaystyle }$ ${\displaystyle M}($RMSE(루트 평균 제곱 오차)에 매우$$ 가까운 매트릭스 ${\displaystyle \text{Tr}}$ (M${\displaystyle }$E ) {\displaystystystyle M}을 산출한다.In particular, with probability ${\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}}}}$ for some constant ${\displaystyle }$${\displaystyle C}$ ${\displaystyle C}.$${\displaystyle \Vert }$ ${\displaystyle {}_{}}$ ${\displaystyle F_{}}$ ${\$\$_{F}}$는 프로베니우스 규범을 나타낸다.이 결과를 유지하려면 전체 가정 집합이 필요하지 않다는 점에 유의하십시오.예를 들어, 일관성이 없는 상태는 정확한 재구성에만 작용한다.마지막으로, 트리밍은 정보를 버려야 하므로 직관적으로 보이지 않을 수 있지만, M$E{\displaystyle {}^{}}$ {\$displaystyle$M^{E$}$를 첫 $번째{\displaystyle }$ r ${\displaystyle r}$에 투영하면 관찰된 항목보다$$ ${\displaystyle {기본}^{}}$ 매트릭스 $M{\displaystyle }$ ${\displaystyle M}$에 대한 정보가 더 많이 제공됨을 보장한다.

3단계에서 내부 최소화 문제가${\displaystyle }$(${\displaystyle X}$${\displaystyle Q}$, ${\displaystyle Y}$ )${\$디스플레이 $스타일$ (X, Y) {\디스플레이 스타일 (X$,Y)}$에 대해$$ (${\displaystyle X}$ Q , Y ${\displaystyle R}$) ${\디스플레이$ 스타일 (X, XQ)에 대해 동일한 솔루션을 가지고 있다는 것을 확인함으로써 후보 $행렬{\displaystyle }$ X${\displaystyle }$, ${\displaystyle Y}$ ${\디스플레이 스타일$ ($XQ,$ X, Y$)$의 공간을 줄일 수 있다$$.$Q$ ${\displaystyle Q}$ 및$$ $R{\displaystyle }$ ${\displaystyle R}$은(는) r ${\displaystyle$ r$}$ $행렬$에 의한$$ 정형 $r{\displaystyle }$ ${\displaystyle$ $r$$}$이다$.$그런 다음 두 개의 그래스맨 다지관의 교차 생산물에 걸쳐 그라데이션 강하를 수행할 수 있다.${\displaystyle r}$ ${\displaystyle \ll }$ ${\displaystyle m,}$ n ${\displaystyle r\ll$ m$,\;n}$과(와$)$ 관찰된 $항목{\displaystyle }$ ${\displaystyle \mathrm{세트}}$가 n r ${\displaystyle \log }$ ${\displaystyle n}$ {\$displaystyle nr\log n}$의 순서인 경우$,$ 3단계에서 반환된 매트릭스는 $정확히{\displaystyle }$ M ${\displaystyle M}$이다$.$ 그렇다면 매트릭스 완료 문제가 진입 횟수에 대해 충분히 결정되지 않는 것으로 알고 있기 때문에 알고리즘이 최적이다.s는 $n{\displaystyle }$ ${\displaystyle r}$ ${\displaystyle \log }$ ${\displaystyle n}$ ${\displaystyle nr\log n}$의 순서로 되어 있어야 한다$.$

교대 최소 제곱 최소화

교번 최소화는 주어진 데이터에 가장 적합한 낮은 등급 매트릭스를 찾는 데 광범위하게 적용 가능하고 경험적으로 성공적인 접근방식을 나타낸다.예를 들어 하위 매트릭스 완성 문제에 대해서는 이 방법이 가장 정확하고 효율적인 방법 중 하나로 여겨지며 넷플릭스 문제에서 우승 엔트리의 주요 구성요소를 형성했다.교번 최소화 접근방식에서 낮은 순위의 목표 행렬은 이선 형태로 다음과 같이 기록된다.

${\displaystyle X}$= ${\displaystyle U}$ ${\displaystyle {}^{}}$ ${\displaystyle T^{}}$ ${\$;

그런 다음 알고리즘은 최상의 $U{\displaystyle }${\$displaystyle$ U$}$과 $최고$의$$V {\$displaystyle$ V$} 사이$에서 번갈아 나타난다$.$ 전체적인 문제가 비콘벡스인 반면, 각 하위 문제는 전형적으로 볼록하며 효율적으로 해결될 수 있다.Jain, Netrapalli 및 Sanghavi는 매트릭스 완료와 매트릭스 감지 모두에 대해 교대 최소화의 성능에 대한 최초의 보증 중 하나를 제공했다.

교번 최소화 알고리즘은 다음과 같은 비 컨벡스 문제를 해결하기 위한 근사적인 방법으로 볼 수 있다.

${\displaystyle {\begin{aigned}&{\underset {U,V\in}\\mathb {R}^{n\\text{min}}}&\ P_\\Oba }(UV^{T}-P)\{F}^{2}\end}}$

Jain, Netrapalli 및 Sanghavi가 제안한 AltMinComplete 알고리즘은 다음과 같다.^[12]

1. 입력: 관측된 집합 $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega},$값 $P{\displaystyle {}_{}}$ ${\displaystyle {\Omega \mathrm{}}_{}M}$) ${\displaystyle P_{\Oomega}(M)}$
2. 파티션 $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega }$을(를) $2{\displaystyle \mathrm{}}$T + ${\displaystyle 1}$ ${\displaystyle$ ${\displaystyle {\mathrm{2T}}_{}}$$+1}$ 하위 집합$$ $\Omega {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\displaystyle \cdots ,{\mathrm{}}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ T ${\$$\Omega {\displaystyle \mathrm{}}$ t ${\displaystyle \Oomega }$의 각 요소가 동일한 확률의$$ $\Omega {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle t_{}}$ ${\$에 속하는$$$$ T$}}}$
3. ${\displaystyle {\hat {U}}^{0}=SVD({\frac {1}{p}}P_{\Omega _{0}}(M),k)}$ i.e., top-${\displaystyle k}$ left singular vectors of ${\displaystyle {\frac {1}{p}}P_{\Omega _{0}}(M)}$
4. 클리핑:크기가 ${\displaystyle \frac{2\mu k}{}}$보다 큰 $U$ ${\displaystyle {\stackrel{}{^}}^{}}$ ${\displaystyle 0^{\mathrm{}}}$ ${\$$displaystyle$ ${\u}^{0$$}{\$${\displaystyle {displaystyle}^{\mathrm{}}}$ ${\frac$ {2\mu ${\$$sqrt{k}}{\sqrt$${$n$}}}}}}$의 모든 요소를 0으로$$ 설정하고 $U{\displaystyle {\stackrel{}{}}^{}}$ $^{\$ {$U}^{0}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$의 열을 직교정렬로 한다.
5. 을 위해 ${\displaystyle t=0,\cdots,T-1}$ 하다
6. ${\displaystyle \quad {\v}^{{t+1}\왼쪽 화살표 {\text{argmin}_{V\in \mathb {R}^{n\t\time k}\P_{\Oomega_{t+1}{{{{{U}V^{T}-M)\{F}^{2}}:$
7. ${\displaystyle \quad {\hat {U}^{t+1}\왼쪽 화살표 {\text{argmin}}_{{{{}}}U\in \mathb{R} ^{m\time k}\ P_{\Oomega_{T+t+1}:{T+1}(U({\hat{V}^{V}^{t+1})^{T}-M)\ _{F}^{2}}$
8. 을 위해 끝나다.
9. 반품 ${\displaystyle X={\hat{U}^{T}({\hat {V}}^{\hat){V}^{T}^{T}}$

They showed that by observing ${\displaystyle \Omega =O(({\frac {\sigma _{1}^{*}}{\sigma _{k}^{*}}})^{6}k^{7}\log n\log(k\ M\ _{F}/\epsilon ))}$ random entries of an incoherent matrix ${\displaystyle M}$, AltMinComplete algorithm ca$n{\displaystyle }$ M ${\displaystyle M}$을(를) $O{\displaystyle (\mathrm{로그}}$ ${\displaystyle }$( 1${\displaystyle }$/ ${\displaystyle ϵ))}$ ${\displaystyle$ O$(\log(1/\epsilon ))}$ 단계로 복구한다.샘플 복잡성(${\displaystyle \Omega \mathrm{}}$ $displaystyle \Oomega$})$$ 측면에서 이론적으로 교류 최소화에는 볼록한 이완보다$$ 더 큰 $\Omega {\displaystyle \mathrm{}}$ ${\displaystyle \Oomega }$이(가) 필요할 수 있다.그러나 경험상으로는 표본 복잡성 한계가 더 강화될 수 있다는 것을 암시하는 경우가 아닌 것 같다.시간의 복잡성 측면에서, 그들은 AltMinComplete가 시간이 필요하다는 것을 보여주었다.

${\displaystyle O(\Omega \mathrm{}}$ ${\displaystyle k{}^{}}$ 2 ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$(${\displaystyle 1}$/ ${\displaystyle ϵ}$ )${\displaystyle }$)${\displaystyle O(\Oomega$ k$^{2}\log(1/\epsilon$ $)\}).$

볼록한 이완에 기반한 방법에는 엄격한 분석이 있지만, 교대 최소화에 기반한 알고리즘이 실제로 더 성공적이라는 점에 주목할 필요가 있다.^{[citation needed]}

적용들

매트릭스 완료의 몇 가지 적용은 다음과 같이 Candés와 Plan에^[9] 의해 요약된다.

협업 필터링

협업 필터링은 많은 사용자로부터 맛 정보를 수집하여 사용자의 관심사에 대해 자동 예측하는 작업이다.애플, 아마존, 반스앤노블, 넷플릭스 같은 회사들은 부분적인 지식에서 사용자 선호도를 예측하려고 애쓰고 있다.이러한 종류의 매트릭스 완성 문제에서, 알려지지 않은 완전 매트릭스는 일반적으로 몇 가지 요인만이 개인의 취향이나 선호도에 기여하기 때문에 낮은 순위로 간주되는 경우가 많다.

시스템 식별

제어에서 이산 시간 선형 변동 시간 상태-공간 모델을 적합시키려 함

${\displaystyle {\begin}x(t+1)&=Ax(t)+Bu(t)\\y(t)&=Cx(t)+Du(t)\end{aigned}}}}}$

to a sequence of inputs ${\displaystyle u(t)\in \mathbb {R} ^{m}}$ and outputs ${\displaystyle y(t)\in \mathbb {R} ^{p},t=0,\ldots ,N}$. The vector ${\displaystyle x(t)\in \mathbb {R} ^{n}}$ is the state of the system at time ${\displaystyle t}$ and $n{\displaystyle }$ $[\displaystyle n}$은(는) 시스템 모델의 순서다.입력/출력 쌍에서 행렬 $A{\displaystyle ,}$ ${\displaystyle B,}$ ${\displaystyle C,}$ D ${\디스플레이$ 스타일 $A,B,C,D}$ 및$$ 초기 $상태{\displaystyle }$ x (${\displaystyle }$0${\displaystyle }$) ${\디스플레이$ 스타일 $x (0)}$을(를) 복구하려고 한다$.$이 문제는 또한 낮은 순위의 매트릭스 완성 문제로 볼 수 있다.

사물인터넷(IoT) 현지화

IoT 센서 네트워크에서는 국산화(또는 글로벌 포지셔닝) 문제가 자연스럽게 발생한다.문제는 페어웨이즈 거리의 국부적 또는 부분적 집합에서 유클리드 공간의 센서 맵을 복구하는 것이다.따라서 센서가 2-D 평면에 위치할 경우 2등급, 3-D 공간에 위치할 경우 3등급의 매트릭스 완료 문제가 된다.^[14]

소셜 네트워크 복구

대부분의 실제 소셜 네트워크는 낮은 거리 매트릭스를 가지고 있다.사설 노드, 제한된 스토리지 또는 계산 리소스 등의 이유로 인해 전체 네트워크를 측정할 수 없을 때, 알려진 거리 항목의 극히 일부만 갖게 된다.범죄 네트워크는 그러한 네트워크의 좋은 예다.낮은 순위의 매트릭스 완료를 사용하여 이러한 관측되지 않은 거리를 복구할 수 있다.^[15]

참고 항목

참조