낮은 순위 근사치

수학에서 낮은 순위 근사치는 비용 함수가 주어진 행렬(데이터)과 근사 행렬(최적화 변수) 사이의 적합성을 측정하는 최소화 문제로 근사 행렬이 순위를 줄였다는 제약이 따른다.이 문제는 수학적 모델링과 데이터 압축에 사용된다.순위 제약조건은 데이터에 적합한 모형의 복잡성에 대한 제약조건과 관련이 있다.응용 프로그램의 경우, 종종 순위 제약 조건과 별개로 근사 행렬에 다른 제약 조건이 있다. 예를 들어, 비부정성 및 행클 구조.

낮은 순위 근사치는 다음과 밀접한 관련이 있다.

• 주성분 분석,
• 요인 분석,
• 총 최소 제곱,
• 잠재 의미 분석 및
• 직교 회귀

• 동적 모드 분해

주어진

• $구조{\displaystyle \mathcal{}}$ 사양 S${\displaystyle }$: R ${\displaystyle {}^{}}$ ${\displaystyle {{}_{}}^{}}$→ ${\displaystyle R^{}}$ ${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {\times }^{}}$ n ${\$ n$\},$
• 구조 매개변수 벡터 $p{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {{Rn}_{}}^{}}$ p ${\$
• 표준 $\Vert {\displaystyle }$ ${\displaystyle \cdot }$ ${\displaystyle \{}$ ${\displaystyle \cdot$ 및
• 원하는 $순위{\displaystyle }$ r ${\displaystyle$ r$\},$

${\displaystyle {\textimize}\quad{\cHB{minimize}\quad{p}}}{\widehat{p}\quad \p-}\p-{p}\widehat{p}}{big}\colleq r}}}$

적용들

• 선형 시스템 식별, 이 경우 근사 행렬이 Hankel 구조로 되어 있다.^[1][2]
• 기계 학습, 이 경우 근사 행렬이 비선형 구조로 되어 있다.^[3]
• 권장자 시스템. 이 경우 데이터 행렬에 결측값이 있고 근사치가 범주형인 경우.
• 거리 행렬 완료, 이 경우 양의 정의 제약 조건이 있다.
• 자연 언어 처리, 이 경우 근사치가 음수가 아닌 경우.
• 컴퓨터 대수, 이 경우 근사치는 실베스터 구조로 되어 있다.

기본 하위 순위 근사 문제

프로베니우스 표준에 의해 측정된 적합성에 대한 구조화되지 않은 문제, 즉,

${\displaystyle {\textimize}\quad {\text{minimize}}}{\widehat {D}\d-{\widehat}\{\text{}}}}}}}{\text{\text}}}}}{\text}}}}}}}{\data.F}}\quad {\text{data.}}\quad \operatorname {rank} {\big (}{\widehat{D}{\big )}\leq r}$

데이터 행렬의 단수 값 분해에 대한 분석 솔루션을 가지고 있다.그 결과를 매트릭스 근사 보조정리 또는 에카르트-라고 한다.영-미르스키 정리.^[4] 내버려두다

$\displaystyle D=U\Sigma V^{\top }\in \mathb {R} ^{m\time n},\quad m\geqn}$

be the singular value decomposition of ${\displaystyle D}$ and partition ${\displaystyle U}$, ${\displaystyle \Sigma =:\operatorname {diag} (\sigma _{1},\ldots ,\sigma _{m})}$, and ${\displaystyle V}$ as follows:

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

where ${\displaystyle U_{1}}$ is ${\displaystyle m\times r}$, ${\displaystyle \Sigma _{1}}$ is ${\displaystyle r\times r}$, and ${\displaystyle V_{1}}$ is ${\displaystyle n\times r}$. Then the rank-${\displaystyle r}$ matrix, obtained from the truncated singular v해열 분해

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

미니마이저 $^{\$은(는) if ${\displaystyle r_{}}$+ ${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\$_{$r+1}\neq \sigma _${r$}$인 경우에만 고유하다$.$

에카르트 증명서-영-미르스키 정리(스펙트럼 노멀용)

$A{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle m^{}}$ ${\displaystyle {\times }^{}}$ n ${\$ n$}$을(를) m${\displaystyle \mathrm{nn}}${\$displaystyle$ m$\geq$ n$}$을(를) 가진 실제(직사각형) 행렬로$$ 두십시오$.$

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

is the singular value decomposition of ${\displaystyle A}$. Recall that ${\displaystyle U}$ and ${\displaystyle V}$ are orthogonal matrices, and ${\displaystyle \Sigma }$ is an ${\displaystyle m\times n}$ diagonal matrix with entries ${\displaystyle (\sigma _{1},\s$$igma$ ${\displaystyle {}_{}{}_{}}$$2},\cdots,\cdots$,\cdma $_$${n},$ ${\displaystyle {}_{}}$ $displaystyle \protma \{1}\geq \{2}\cdotgeq \cdotsgema \{n}\gq$ 0$\}).$

우리는 ‖${\displaystyle }$2${\displaystyle {}_{2\mathrm{}}}$ 2$${\$displaystyle \cdot \{2}}$로 표시된 스펙트럼 $표준$에서 A$${\$displaystyle$A}에 대한 최고의 $등급{\displaystyle }$ k$${\$displaystyle k$} 근사치가$$ 에 의해 주어졌다고 주장한다$.$

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

여기서 ${\$와 ${\displaystyle v_{}}$ ${\$는 $각각{\displaystyle }$ $U{\displaystyle }$ ${\displaystyle U}$와 V ${\displaystyle V}$의 i ${\displaystyle i}$ 열을 나타낸다$$$$$.$

첫째, 우리가 가지고 있는 것이

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

Therefore, we need to show that if ${\displaystyle B_{k}=XY^{\top }}$ where ${\displaystyle X}$ and ${\displaystyle Y}$ have ${\displaystyle k}$ columns then ${\displaystyle \ A-A_{k}\ _{2}=\sigma _{k+1}\leq \ A-B_{k}\ _{2}}$.

$Y{\displaystyle }$ ${\displaystyle Y}$에 $k{\displaystyle }$ ${\displaystyle k}$ 열이$$ 있으므로$$ $V{\displaystyle }$ ${\displaystyle V},$즉, $첫{\displaystyle \mathrm{번째}}$ k +$$1 {\$displaystyle k+$1} 열의$$ 비선형 선형 결합이 있어야 한다.

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

such that ${\displaystyle Y^{\top }w=0}$. Without loss of generality, we can scale ${\displaystyle w}$ so that ${\displaystyle \ w\ _{2}=1}$ or (equivalently) ${\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}.}$

그 결과는 위의 불평등 양쪽의 제곱근을 취함으로써 나타난다.

에카르트 증명서-영-미르스키 정리(프로베니우스 노르말용)

$A{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle m^{}}$ ${\displaystyle {\times }^{}}$ n ${\$ n$}$을(를) m${\displaystyle \mathrm{nn}}${\$displaystyle$ m$\geq$ n$}$을(를) 가진 실제(직사각형) 행렬로$$ 두십시오$.$

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

$A{\displaystyle }${\$displaystyle A}$의 단수 값 분해 입니다$.$

우리는${\displaystyle }$프로베니우스 $표준$의 A ${\displaystyle A}$에 ${\displaystyle {대한}_{}}$ 최고 등급 $k{\displaystyle }$ ${\$$displaystyle \cdot \ _{F$의 근사치가$$ 에 의해 주어졌다고 주장한다.

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

여기서 ${\$와 ${\displaystyle v_{}}$ ${\$는 $각각{\displaystyle }$ $U{\displaystyle }$ ${\displaystyle U}$와 V ${\displaystyle V}$의 i ${\displaystyle i}$ 열을 나타낸다$$$$$.$

첫째, 우리가 가지고 있는 것이

${\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 }$ $X{\displaystyle {}_{}}$ ${\displaystyle X}$ 및$$ $Y{\displaystyle }$ ${\$$displaystyle$ $Y}$이$($가) k {\displaystyle X}과(와) Y {\$displaystyle$ Y}이$$(가)$$k {\$displaystyle$ k$}$ 열로$$ 되어 있는 $경우$ 이 $때{\displaystyle }$ B${\displaystyle {}_{}}$k = $XY^{\displaystytype$ k$}$를 표시해야 한다.

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

By the triangle inequality with the spectral norm, if ${\displaystyle A=A'+A''}$ then ${\displaystyle \sigma _{1}(A)\leq \sigma _{1}(A')+\sigma _{1}(A'')}$. Suppose ${\displaystyle A'_{k}}$ and ${\displaystyle A''_{k}}$ respectively d위에서 설명한 SVD 방법으로 순위$$ $k{\displaystyle }$ ${\displaystyle k'}$ 근사치를$$ $A{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$ 및$$ $A{\displaystyle {}^{}}$ ${\displaystyle {″}^{}}$ ${\$ A$'}$에 부여한다.그런 다음${\displaystyle ,}$ $임의$의 i , ${\displaystyle \mathrm{j}}$ ${\displaystyle \ge }$ 1 ${\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{정렬}}}$

Since ${\displaystyle \sigma _{k+1}(B_{k})=0}$, when ${\displaystyle A'=A-B_{k}}$ and ${\displaystyle A''=B_{k}}$ we conclude that for ${\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\stackrel{}{}}$- D ${\displaystyle \stackrel{}{^}}$ ${\$의 모든 요소. 오류 분포에 대한 사전 지식은 가중 저위 근사 문제를 고려함으로써 고려할 수 있다$.$

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

여기서 ${\displaystyle \text{vec}}$( ${\displaystyle A}$) ${\displaystyle {\text{vec}(A)}$은 행렬 A ${\displaystyle A}$ 열을$$ 벡터링하며$$ $W{\displaystyle }${\$displaystyle$W}은$$ 주어진 양의(반미)확정 가중 행렬이다.

일반적인 가중 저위 근사치 문제는 단수 값 분해 측면에서 분석 솔루션을 인정하지 않으며, 전지구적으로 최적의 솔루션이 발견된다는 보증을 제공하지 않는 국소 최적화 방법으로 해결된다.

uncorrelated 무게의 경우low-rank 근사 문제 또한 이러한 방법으로 추진될 수 있습니다. 모르기는non-negative 행렬 W{W\displaystyle}과 행렬을 우리는 ∑ 나는, j(거나 책 읽어 나는, j(명확히 설명, j− B나는, j)x2{\displaystyle \sum_{i,j}(W_{i,j}(A_{i,j}-B_{i,j}을 최소화하고 싶은{A\displaystyle}에[5][6].))$^{2}}:$ $행렬{\displaystyle }$ 위에$$ B ${\displaystyle B},$ 최대 r ${\displaystyle r$

항목별 $L{\displaystyle {}_{}}$ ${\displaystyle p_{}}$ ${\$ 낮은 순위 근사 문제$$

Let ${\displaystyle \ A\ _{p}=\left(\sum _{i,j} A_{i,j}^{p} \right)^{1/p}}$. For ${\displaystyle p=2}$, the fastest algorithm runs in ${\displaystyle nnz(A)+n\cdot poly(k/\epsilon )}$ time,.^[7][8]사용된 중요한 아이디어들 중 하나는 의식 없는 서브스페이스 임베딩(OSE)으로 불리며, 그것은 Sarlos에 의해 처음 제안되었다.^[9]

$p{\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle p=1}$의 경우$,$ 이 항목별 L1 규범은 특이치가 있는 프로베니우스 규범보다 더 견고하다고 알려져 있으며, 노이즈에 대한 가우스 가정이 적용되지 않을 수 있는 모델에 표시된다.$\Vert {\displaystyle }$ ${\displaystyle B}$- ${\displaystyle A}$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$\$B-A\ _{1$}를 최소화하는 것이 당연하다$.$^[10] ${\displaystyle \mathrm{p}}$= 0 ${\displaystyle p=0}$ 및 ${\displaystyle \mathrm{p<img\; alt="p=0"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/b3e6ac10fa45fb984d886065f959a6bdd467b5e8"\; style="vertical-align:\; -0.671ex;\; margin-left:\; -0.089ex;\; width:5.52ex;\; height:2.509ex;"\; papago-attr-id="264">}}$ ${\displaystyle \ge }$ 1 ${\displaystyp p\geq 1$의 경우, 몇 가지 검증 가능한 알고리즘이 있다.^[11][12]

거리 낮은 순위 근사치 문제

$P{\displaystyle }$=${\displaystyle }${${\displaystyle {p\mathrm{}}_{}}$ 1,${\displaystyle }$… ,${\displaystyle p_{}}$ m ${\displaystyle {}_{}}$ ${\displaystyle$ P$=\{p_{1},\ldots, p_{m}\}\},$ $Q$ =${\displaystyle }${ ${\displaystyle {q\mathrm{}}_{}}$ 1,${\displaystyle {}_{}\dots ,q_{}}$ ${\displaystyle {}_{}}$ ${\displaysty Q=\{q_{1},\ldots, q_{$n}\}}}을 임의의 메트릭 공간에서 두 점 집합으로 설정하십시오$$.Let ${\displaystyle A}$ represent the ${\displaystyle m\times n}$ matrix where ${\displaystyle A_{i,j}=dist(p_{i},q_{i})}$. Such distances matrices are commonly computed in software packages and have applications to learning image manifolds, handwriting recognition, and multi-di마그네틱한 전개기술 크기를 줄이기 위해, 그러한 행렬의 낮은 순위 근사치를 연구할 수 있다.^[13][14]

분산/스트리밍 낮은 순위 근사치 문제

분배 및 스트리밍 설정에서 낮은 순위 근사치 문제가 다음에서 고려되었다.^[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 {\text{\text}\mathb {R}^{m-r\time m}{\text{}}{}R}{\wide {D}=0}}})\levelopergrowide.$

가중치가 낮은 순위 근사치 문제는 모수 최적화 문제와 동일해진다.

${\displaystyle {\textimize}\quad {\datad}{{D},P{\text{} 및 }L\quad \quad \operatorname {vec} ^{\top }(D-{\widehat {D})W\operatorname {vec}(D-{\widehat {D})\quad {\text{data.}}\quad {\widehat {D}=PL}$

, 그리고

${\displaystyle {\textimize}\quad {\text}{{D}{\widehat{D}{\d}R\quad \quad \operatorname {vec}^{\top }(D-{\widehat {D})W\operatorname {vec}(D-{\widehat {D})\quad {\datad{d}}}\quad R{d}=0\widehat {\datad {\text{and}\quad RR^{}\top }=I_{r}}}}}},}$

여기서 $I{\displaystyle {}_{}}$ ${\displaystyle r_{}}$ ${\$는 크기 $r{\displaystyle }$ ${\displaystyle r}$의 ID 매트릭스 입니다$.$

교대 투영 알고리즘

순위 제약 조건의 이미지 표현은 다른 변수(${\displaystyle }$ ${\displaystyle P}$ 또는$$ $L{\displaystyle }$ ${\displaystyle$ L$\})$ 중 $하나$에 대해 비용 함수를 대체하여 최소화하는 파라미터 최적화 방법을 제안한다.$P{\displaystyle }$ ${\displaystyle P}$과 $L{\displaystyle }$ ${\displaystyle L}$에 대한 동시 최소화는 어려운 바이콘벡스 최적화 문제지만$$ 변수 중 하나에 대한 최소화는 선형 최소 제곱 문제로서 전지구적이고 효율적으로 해결할 수 있다.

결과 최적화 알고리즘(교대 투영이라고 함)은 가중치가 낮은 저위 근사치 문제의 국소 최적 솔루션으로 선형 수렴률과 전역적으로 수렴된다.$P{\displaystyle }$ ${\displaystyle P}($또는 $L{\displaystyle }$ ${\displaystyle$ 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 = p * l; dd = d - dh; f(i) = dd(:) * w * dd(:); if(f(i - 1) - f(i) < toll, break, end for endf

가변 투영 알고리즘

교대 투영 알고리즘은 이미지 형태로 매개변수화된 낮은 순위 근사치 문제가 $변수{\displaystyle }$ P ${\displaystyle P}$ $또는$ L ${\displaystyle L}$에서 이선형이라는 사실을 이용한다$.$ 문제의 이선형 특성은 가변 투영이라는 대안적 접근법에서 효과적으로 사용된다.^[16]

이미지 양식에서 파라미터로 처리된 가중치가 낮은 순위 근사 문제를 다시 고려하십시오.$L{\displaystyle }$ ${\displaystyle L}$ 변수$$(선형 최소 제곱 문제)에 대한 최소화는 $P{\displaystyle }$ ${\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)}}.}$

따라서 원래의 문제는 $P{\displaystyle }$ ${\displaystyle P}$과 관련하여 f${\displaystyle }$( P $){\displaystyle f(P)}$을 최소화하는 비선형 최소 제곱 문제와 동등하다$.$ 이러한 목적을 위해 Levenberg-Marquardt 알고리즘을 사용할 수 있다.

가중치가 낮은 하위 순위 근사치를 위한 가변 투영 알고리즘의 Matlab 구현:

함수 [dh, f] = wlra_varpro(d, w, p, toll, maxiter) prob = optimset(); prob.solver = 'lsqnonlin', prob.options = optimset('MaxIter', maxiter', maxiter, '톨Fun', tol); pun, tol); pol).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);

가변 투영 접근방식은 커널 형태에서 매개변수화된 낮은 순위 근사 문제에도 적용될 수 있다.이 방법은 제거된 변수의 수가 비선형 최소 제곱 최소화 단계에 남아 있는 최적화 변수의 수보다 훨씬 클 때 효과적이다.이러한 문제는 커널 형태로 매개변수화된 시스템 식별에서 발생한다. 여기서 제거된 변수는 근사 궤적이고 나머지 변수는 모델 매개변수다.선형 시간 변화 시스템 맥락에서 제거 단계는 Kalman 평활과 동일하다.

A 변종: 볼록 제한 낮은 순위 근사치

통상적으로 우리는 우리의 새로운 솔루션이 낮은 등급일 뿐만 아니라 적용 요건으로 인한 다른 볼록한 제약을 충족시키기를 원한다.우리의 관심사는 다음과 같을 것이다.

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

이 문제는 부정확한 (비정상적인 프로그래밍) 완화로부터 좋은 해결책을 복구하는 것을 포함하여, 많은 실제 응용 프로그램을 가지고 있다.만약 추가적인 제약 조건 $g{\displaystyle }$ ${\displaystyle (p\stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$) ${\displaystyle \le }$ ${\displaystyle 0}$ ${\displaystyle$ g$({\widehat {p}})\leq$ 0$}$이(가) 모든 원소가 음성이 아니어야 하는 것처럼 선형이라면$$, 문제를 구조화 낮은 순위 근사라고 한다.^[17]더 일반적인 형태는 볼록한 낮은 계급 근사치로 명명된다.

이 문제는 많은 문제를 푸는 데 도움이 된다.다만 볼록한(저위) 제약과 비콘벡스(저위) 제약이 복합적으로 작용해 난항을 겪고 있다.다른 기술 g(≤ 0{\displaystyle g({\widehat{p}})\leq 0}의 다른 깨달음에 근거한다. 그러나 반복 방향 방법(ADMM)볼록 목표 함수와 함께nonconvex 문제를 해결하기 위해 적용할 수 있Multipliers의 따라서 suita 제약 조건과 다른 볼록 constraints,[18]에 개발되었다.ble위 문제를 해결하기 위해.더욱이, 일반적인 비 컨벡스 문제와 달리, ADMM은 그것의 이중 변수가 반복적으로 수렴되는 한 실현 가능한 해결책의 수렴을 보장할 것이다.

참고 항목

• CUR 행렬 근사치는 원래 행렬의 행과 열에서 만들어진다.

참조

• M. T. Chu, R. E. Funderlic, R. J. Plemmons, 구조화된 낮은 등급 근사치, 선형 대수 및 그 적용, 제366권, 2003년 6월 1일, 페이지 157–172 doi:10.1016/S0024-3795(02)00505-0

외부 링크

• 구조화 낮은 순위 근사치를 위한 C++ 패키지