카츠마르스법

Kaczmarz 방법 또는 Kaczmarz의 알고리즘은 선형 방정식 시스템 $A{\displaystyle }$ ${\displaystyle x}$= ${\displaystyle b}$ ${\displaystyle Ax=b}$을(를) 풀기 위한 반복 알고리즘이다$.$폴란드 수학자 스테판 카츠마르즈에 의해 처음 발견되었으며,^[1] 1970년 리처드 고든, 로버트 벤더, 가보르 헤르만의 투영으로부터 이미지 재구성 분야에서 재발견되어 대수학재건기법(ART)으로 불린다.^[2]ART는 긍정의 제약을 포함시켜 비선형적으로 만든다.^[3]

Kaczmarz 방법은 방정식의 어떤 선형 시스템에도 적용 가능하지만, 다른 방법에 비해 계산상의 우위는 시스템이 희박한지에 따라 달라진다.일부 생물의학 영상 애플리케이션에서는 필터링된 백프로젝션 방법과 같은 다른 방법보다 우수하다는 것이 입증되었다.^[4]

컴퓨터단층촬영(CT)부터 신호처리까지 응용 분야가 다양하다.또한 선형 시스템에서 설명하는 하이퍼플레인에 적용하여 볼록 세트(POCS)에 연속 투영하는 방법을 얻을 수 있다.^[5][6]

알고리즘 1: Kaczmarz 알고리즘

$A{\displaystyle }$ ${\displaystyle x}$= b ${\$$displaystyle$ $Ax=b}$을(를) 선형 방정식의 시스템으로 하고$$, $m{\displaystyle }$ ${\displaystyle m}$을(를) A 행의 개수로 하고$$, ${\displaystyle i_{}}$ ${\$$displaystyle a_$${i}$을(를$)$ 복합 $매트릭스$ $A{\displaystyle }$ 행의$$i {\$displaystytyle$$$$^{0}$을 초기에$$ 임의로 한다.$A{\displaystyle }$ ${\displaystyle x}$= ${\displaystyle b}$ ${\displaystyle Ax=b}$의 솔루션에 대한 pproximation$.$ $k{\displaystyle }$= ${\displaystyle 0,}$ 1,${\displaystyle }$… ${\displaystyle k=0,1,\ldots }$ 계산의$$ 경우:

${\displaystyle x^{k+1}=x^{k}+{\frac {b_{i}-\langle a_{i},x^{k}\rangele }{\\}{\}}{a_{i}}}}}}}{2}}:{\overline{a_{i}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

(1)

여기서 $i{\displaystyle }$= k ${\displaystyle m,}$ i${\displaystyle }$= ${\displaystyle 1}$,${\displaystyle 2}$,${\displaystyle }$…${\displaystyle m}$ ${\displaystyle$ i$=k{\bmod},i=1,2,\ldots$ m$}$및 ${\displaystyle \stackrel{}{i_{}}}$ $}{\$는 ${\displaystyle i_{}}$ ${\$i}}의 복잡한 결합을 의미한다$.$

시스템이 일관성이 있는 경우, 반복이 0 벡터로부터 시작된다는 전제하에 ${\displaystyle x^{}}$ k ${\$x^{$k}}$는 최소 표준 용액으로$$ 수렴한다.

이완 파라미터 $parameter{\displaystyle {}^{}}$ ${\displaystyle k^{}}$ ${\$을 사용하여 보다 일반적인 알고리즘을 정의할 수 있다.

${\displaystyle x^{k+1}=x^{k}+\frac{b_{i}-\langle a_{i}},x^{k}\rangele }{\\a_{i}}}}}{{2}}:}{\overline{a_{i}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

일관되지 않은 방정식의 시스템에 적용되었을 때 정규화된 가중 최소 제곱 용액에 수렴하는 방법의 버전이 있으며, 적어도 초기 동작에 관한 한, 결합 구배법과 같은 다른 반복적 방법보다 적은 비용으로 사용된다.^[7]

알고리즘 2: 랜덤화 Kaczmarz 알고리즘

2009년에 토마스 스트로머와 로마 베르시닌에^[8] 의해 지나치게 결정된 선형 시스템에 대한 Kaczmarz 방법의 무작위 버전이 도입되었는데, 여기서 i번째 방정식은 i${\displaystyle {}_{}{}^{a\mathrm{}}}$ 2 . ${\displaystyle \_{i}\ ^{2$}에 비례하는 확률로 무작위로 선택된다$.$$}$

이 방법은 확률적 경사 강하의 특별한 경우로 볼 수 있다.^[9]

이러한 상황에서 $x{\displaystyle {}_{}}$ ${\displaystyle k}$ ${\$는 $A{\displaystyle }$ x = b${\displaystyle ,}$ ${\displaystyle Ax=b,}$의 솔루션으로 기하급수적으로 빠르게 수렴되며$$ 수렴$$ 속도는 스케일 조건 번호 $number{\displaystyle }$ (${\displaystyle A}$) ${\displaystyle \kappa (A)}$에만 의존한다$.$

정리.$x{\displaystyle }$ ${\displaystyle x}$을(를) $A{\displaystyle }$ ${\displaystyle x}$= ${\displaystyle b}$. ${\displaystyle Ax=b$의 솔루션이 되도록$$ 한다$.$$}$ 그러면$$ 알고리즘 2가 예상 $x$ ${\displaystyle x}$에 수렴되고 평균 오류:

${\displaystyle \mathb {E} \ x_{k}-x\^{2}\leq \left(1-\kappa (A)^{-2}\오른쪽)^{k}\cdot \x_-x\ ^{2}.}$

증명

우리는 가지고 있다.

${\displaystyle \forall z\in \mathb {C}^{n}:\quad \sum _{j=1}^{m} \langle z,a_\\nangle ^{2}\geck {\\\\\{2}}:\A^{-1}{2}}:$

(2)

사용.

${\displaystyle \ A\ ^{2}=\sum _{j=1}^{m}\ a_{j}\{2}}:$

다음과 같이 쓸 수 있다(2).

${\displaystyle \forall z\in \mathbb {C} ^{n}:\quad \sum _{j=1}^{m}{\frac {\ a_{j}\ ^{2}}{\ A\ ^{2}}}\left \left\langle z,{\frac {a_{j}}{\ a_{j}\ }}\right\rangle \right ^{2}\geq \kappa (A)^{-2}{\ z\ ^{2}}}$

(3)

증거의 요지는 (3)의 왼쪽 측면을 어떤 무작위 변수에 대한 예상으로 보는 것이다.$즉$, $A{\displaystyle }$${\displaystyle }$${\displaystyle x}$= ${\displaystyle b}$ ${\displaystyle j-th}$ 방정식의$$ 솔루션 공간이 하이퍼플레인임을$$ 기억하십시오.

${\displaystyle \{y:\langle y,a_{j}\angle =b_{j}\}}$

white normal is ${\displaystyle \frac{j_{}}{}}$ ${\displaystyle \frac{{}_{}}{}}$ ${\displaystyle \frac{{}_{}}{}}$ ${\displaystyle \frac{j_{}}{}}$ ${\displaystyle \frac{{}_{}{}^{}}{}}$ ${\displaystyle \frac{{2\mathrm{}}^{}}{}}$. ${\displaystyle${\$tfrac {a_{j}{{j}\{j}\{2}}.}}}$${\displaystyle A}$ x${\displaystyle }$= ${\displaystyle b}$ ${\displaysty Ax=b}$의 모든 방정식에 대한 정규 값인 랜덤 벡터 Z를 정의하십시오$.$

${\displaystyle Z={\frac {a_{j}}{\ a_{j}\ }}}$ with probability ${\displaystyle {\frac {\ a_{j}\ ^{2}}{\ A\ ^{2}}}\qquad \qquad \qquad j=1,\ldots ,m}$

그러면 (3)은 그렇게 말한다.

${\displaystyle \forall z\in \mathb {C} ^{n}:\quad \mathb {E} \langle z, {2}\geq \kappa(A)^{-2}{\ z\{2}}:}$

(4)

$A{\displaystyle }$ ${\displaystyle x}$= ${\displaystyle b}$ ${\displaystyle Ax=b}$의 랜덤 방정식의 솔루션 공간에 대한$$ 직교 투영 $P{\displaystyle }$ ${\displaystyle$ P$}$은(는) ${\displaystyle P}$ ${\displaystyle z}$= z${\displaystyle }$- ${\displaystyle ⟨}$ z${\displaystyle }$- ${\displaystyle x,}$ ${\displaystyle Z}$ ${\displaystyle ⟩}$ ${\displaystyle Z.}$ ${\displaystyle Pz=z-\langle z-x,Z\angle Z$에 의해 주어진다$$$.$$}$

이제 우리의 알고리즘을 분석할 준비가 되었다.오류${\displaystyle {}_{}}$ ${\displaystyle x_{}}$k -$$${\displaystyle x{}^{2\mathrm{}}}$ 2 ${\$^{$2}}:$ 각 단계(${\displaystyle {\mathrm{이전}}^{}}$ 단계에 조건화됨)에서 최소한 $({\displaystyle 1}$ -${\displaystyle {}^{}}$ (${\displaystyle A{}^{}}$) - 2${\displaystyle {}^{})}$의$$인수만큼 (1-$$\$displaystyle (A)^{-2})$가 감소한다는 것을 보여주고자 한다.$}$ The next approximation ${\displaystyle x_{k}}$ is computed from ${\displaystyle x_{k-1}}$ as ${\displaystyle x_{k}=P_{k}x_{k-1},}$ where ${\displaystyle P_{1},P_{2},\ldots }$ are independent realizations of the random projection ${\display$$style P.}$ The vector ${\displaystyle x_{k-1}-x_{k}}$ is in the kernel of ${\displaystyle P_{k}.}$ It is orthogonal to the solution space of the equation onto which ${\displaystyle P_{k}}$ projects, which contains the vector ${\displaystyle x_{k}-x}$ (recall that ${$$\displaystyle x}$은(는) 모든 방정식의 해법이다.그러면 이 두 벡터의 직교성은

${\displaystyle \ x_{k}-x\ ^{2}=\ x_{k-1}-x\ ^{2}-\x_{k-1}-\{k}\{2}.}$

증빙을 완료하려면${\displaystyle {below}_{}}$ x$$ ${\displaystyle {}_{}}$- 1${\displaystyle {}_{}}$- ${\displaystyle {x\mathrm{}}^{}}$ ${\displaystyle k_{}}$ ${\displaystyle {}_{}{}^{}}$ 2 ${\$\$x_{k-1$}-x_${k}\{$2}}개를 $아래$에서 묶어야 한다.$x{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$의 정의에 따라$,$

${\displaystyle \x_{k-1}-x_{k}\ =\langle x_{k-1}-x,Z_{k}\angle }$

여기서 $Z{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{Z\mathrm{}}_{}}$ ${\displaystyle {}_{}}$… ${\displaystyle Z_{1}, Z_{2},\ldots$$$$}$은 랜덤 벡터 $Z{\displaystyle }$. ${\displaystyle$ Z의 $독립$된 실현이다.$}$

그러므로

${\displaystyle \ x_{k}-x\ ^{2}=\좌측(1-\좌측 \좌측 \langle{x_{k-1}-x}{\x_{x_{k-1}-x}{\}{\}},Z_{k}\rigle \right ^2}}.}$

Now we take the expectation of both sides conditional upon the choice of the random vectors ${\displaystyle Z_{1},\ldots ,Z_{k-1}}$ (hence we fix the choice of the random projections ${\displaystyle P_{1},\ldots ,P_{k-1}}$ and thus the random vectors ${\d$$isplaystyle x_{1},\ldots,x_{k-1},$ 랜덤 벡터 Z ${\displaystyle k_{}}$ ${\$에 대해 평균을 구한다$$.$$그러면

${\displaystyle \mathbb {E} _{Z_{1},\ldots ,Z_{k-1}}{\ x_{k}-x\ ^{2}}=\left(1-\mathbb {E} _{Z_{1},\ldots ,Z_{k-1},Z_{k}}\left \left\langle {\frac {x_{k-1}-x}{\ x_{k-1}-x\ }},Z_{k}\right\rangle \right ^{2}\right){\ x_{k-1}-x\ ^{2}}.}$

(4)와 독립에 의해

${\displaystyle \mathb{E}_{Z_{1},\ldots, Z_{k-1}-x\{2}}\lq(1-\kappa(A)^{-2}{\}}\{k-1}-x\{2}.}$

쌍방의 모든 기대를 종합해 보면 다음과 같이 결론짓는다.

${\displaystyle \mathb {E} \ x_{k}-x\ ^{2}\leq(1-\kappa(A)^{-2}\mathb {E} {\x_{k-1}-x\ ^{2}.\블랙스퀘어 }$

이 선택의 우위는 균일하지 않은 간격의 샘플링 값에서 밴드 제한 함수의 재구성을 통해 설명되었다.그러나, 스트로머와 베르시닌의 보고된 성공은, 그 기하학적 성질이 하이퍼플레인의 공통점을 찾는 데 있는, 그 근본적인 문제를 대수 방정식의 체계로 번역하는 데 있어서, 거기서 이루어진 구체적인 선택에 달려 있다는 지적이^[10] 있어 왔다.의^[8] 선택 방법이 열등한 방식으로 수행될 기본 문제에 대한 합법적인 대수적 표현이 항상 존재할 것이다.^[8][10][11]

Kaczmarz 반복(1)은 순전히 기하학적 해석을 가지고 있는데, 알고리즘은 다음 방정식에 의해 정의된 하이퍼 평면에 전류 반복을 연속적으로 투영한다.따라서 방정식의 척도는 무관하며, (1)에서도 방정식의 (비영(0) 척도가 상쇄된다는 것을 알 수 있다.따라서 RK에서는 $\Vert {\displaystyle }$ ${\displaystyle a_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle$\$a_{i}\}$ 또는$$ 관련될 수 있는 다른 가중치를 사용할 수 있다.구체적으로 위에서 언급한 재건 사례에서 방정식은 가장 가까운 두 이웃으로부터 각 샘플 포인트의 평균 거리에 비례하는 확률로 선택되었다. 즉, 페이칭거와 그뢰케니그가 도입한 개념이다.이 항목에 대한 자세한 내용은 ^[12][13]및 관련 참조를 참조하십시오.

알고리즘 3: Gower-Richtarik 알고리즘

2015년에는 로버트 M.Gower와 Peter Richtarik은^[14] 임의화된 Kaczmarz 알고리즘을 특수 사례로 포함하는$$ A ${\displaystyle x}$ =$$b $displaystyle Ax=b}$의 일관성 있는 시스템을 해결하기 위해 다용도 무작위 반복 방법을 개발했다.다른 특별한 경우로는 무작위 좌표 강하, 무작위 가우스 강하, 무작위 뉴턴 방법이 있다.이러한 모든 방법의 중요도 샘플링이 있는 블록 버전과 버전도 특별한 경우로 발생한다.이 방법은 무작위성이 알고리즘에 진입하는 방식에 있어 매우 온화한 조건 하에서 선형 수렴이라고도 알려진 기하급수적인 비율 붕괴(예상치)를 즐기는 것으로 나타난다.고워-리치타리크 방법은 이들 방법들 사이의 "시블링" 관계를 밝혀내는 첫 번째 알고리즘으로, 그 중 일부는 이전에 독자적으로 제안된 반면, 많은 것들은 새로운 것이었다.

랜덤화된 Kaczmarz에 대한 통찰력

방법의 분석을 통해 얻을 수 있는 무작위화된 Kaczmarz 방법에 대한 흥미로운 새로운 통찰력은 다음과 같다.

• Gower-Richtarik 알고리즘의 일반 비율은 특수 케이스에서 무작위화된 Kaczmarz 방법의 비율을 그것으로 줄였을 때 정밀하게 회복한다.
• 무작위화된 Kaczmarz 알고리즘이 원래 공식화 및 분석된 확률(행 규범의 제곱에 비례하는 확률)의 선택은 최적이 아니다.최적 확률은 특정 반물질 프로그램의 해결책이다.최적의 확률을 가진 무작위화된 Kaczmarz의 이론적 복잡성은 표준 확률의 복잡성보다 임의로 더 좋을 수 있다.그러나 더 나은 양은 매트릭스 $A{\displaystyle }$ ${\displaystyle A}$에 따라 달라진다$.$ 표준 확률을 최적화하는 문제가 있다.
• When applied to a system with matrix ${\displaystyle A}$ which is positive definite, Randomized Kaczmarz method is equivalent to the Stochastic Gradient Descent (SGD) method (with a very special stepsize) for minimizing the strongly convex quadratic function ${\displaystyle f(x)={\tfrac {1}$${2}}:x^{T}}Ax-b^{T}x.}$ $f{\displaystyle }${\$displaystyle f$$}$이(가) $볼록하므로{\displaystyle }$ f ${\displaystyle$ f}의 최소제는 A ${\displaystyle x}$= ${\displaystyle b.}$ ${\displaysty Ax=b$$\}$에 해당하는${\displaystyle \mathrm{}}$equivalent ${\displaystyle f(x}$ ${\displaystyle )}$= ${\displaystyle 0}$ ${\displaystysty$ f}를 만족해야 한다는$$ 점에$$ 유의하십시오$.$$}}$ "특수 단계화"는$$ 확률적 경사로 확장된 1차원 선에서 $f{\displaystyle }$ ${\displaystyle {\{\backslash }^{}}$$displaystyle f$의 알 수 없는(!) 최소제, 즉 $x{\displaystyle {}^{}}$ucl = A - 1${\displaystyle {}^{}}$. ${\displaystyle x^{*}=A^{-1}b.}$로부터의 유클리드 거리를 최소화하는 단계로 이어지는 단계화다.$$ 이러한 통찰력은 반복 프로세스의 이중적 관점(이하 "최적화 관점:구속 및 근사치").

6개의 등가 공식

Gower-Richtarik 방법은 겉보기에는 다르지만 동등한 여섯 가지의 제형을 즐기며, 이를 해석하는 방법(그리고 결과적으로 무작위화된 Kaczmarz를 포함한 여러 변형을 해석하는 방법)을 추가로 조명한다.

• 1. 관점 스케치:스케치 & 프로젝트
• 2. 최적화 관점:구속 및 근사치
• 3. 기하학적 관점: 무작위 교차
• 4. 대수학적 관점 1: 무작위 선형 해결
• 5. 대수학적 관점 2: 무작위 업데이트
• 6. 분석적 관점: 무작위 고정점

우리는 이제 이러한 관점의 일부를 설명한다.방법은 다음 두 가지 파라미터에 따라 달라진다.

• ${\displaystyle \mathrm{가중<img\; alt="B"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a"\; style="vertical-align:\; -0.338ex;\; width:1.764ex;\; height:2.176ex;"\; papago-attr-id="205">}}$ 유클리드 내측 제품$$$⟨{\displaystyle }$ x${\displaystyle }$, y ${\displaystyle {}_{}}$ ${\displaystyle B_{}}$ ${\displaystyle :=}$ ${\displaystyle x^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle y}$ ${\displaystyle \langle$ x$,y\rangele _{B}=x^{$$T}By}$ 및 유도$$ 규범

${\displaystyle \ x\ _{B}=\왼쪽(\langle x,x\rangele _{B}\오른쪽)^{\frac {1}{1},}$

• 및 $행$이 A$${\$displaystyle A$}($$및 열 수의 랜덤)만큼$$ 많은 $랜덤{\displaystyle }$ 행렬$$S {\$displaystyle S}$

1. 스케치와 프로젝트

$이전$에 x $k{\displaystyle {}^{}}$ , ${\displaystyle x^{$k}를$$반복한$$ 경우, 새로운 포인트 x ${\displaystyle {\mathrm{k}}^{}}$+ ${\displaystyle 1^{}}$ ${\$ x$^{k$+1}}는 랜덤$행렬$ $S{\displaystyle }$ ${\displaystyle S}($일부 고정된 분포에서 iid 방식으로)를 그리고 설정을 통해 계산된다$$.

${\displaystyle x^{k+1}={\underset {x}{x}{\opername {arg\min}}}}}\x^{k}\{B}{\text{}{}}}}}}}}}}{S^{T}b의 적용을 받는다.}$

That is, ${\displaystyle x^{k+1}}$ is obtained as the projection of ${\displaystyle x^{k}}$ onto the randomly sketched system ${\displaystyle S^{T}Ax=S^{T}b}$. The idea behind this method is to pick ${\displaystyle S}$ in such a way that a projection onto the sketched system is s원래 시스템 $A{\displaystyle }$ ${\displaystyle x}$= b ${\displaystyle Ax=b}$의 솔루션보다 실질적으로 간단하다$.$ 무작위화된 Kaczmarz 방법은 $B{\displaystyle }$ ${\displaystyle B}$을(를) ID 매트릭스로$,$ $S{\displaystyle }$ {\$displaystyle$ $S$$}$을(를) $i{\displaystyle {}^{}}$ t ${\displaystyle h^{}}$ {\$displaystystyle$ i$^{{th}$ ${\displaystyle {확률}_{}}$p${\displaystyle }$= ${\displaystyle i_{}}$}와$$ 함께 단위 좌표 벡터로 선택하여 얻는다.${\displaystyle {}_{}{\Vert }_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ /${\displaystyle {}_{}^{}\Vert }$ ${\displaystyle A}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ 2${\displaystyle {}_{}^{}}$. ${\displaystyle p_{i}=\a_{i}\{2}^{2$}/\{2}^{2$}/\$ A$\$ $_$${$$F$}^{$F{\displaystyle }$}^{$2}}}}}}}$$B$와 S {\$displaystystyle S}$의 서로 다른 선택은 방법의 다른 변형으로 이어진다$$.

2. 구속과 근사

외관상 다르지만 전적으로 동등한 방법의 공식화(라그랑지안 이중성을 통해 확인됨)는 다음과 같다.

${\displaystyle x^{k+1}={\underset {x}{\operatorname {arg\min}}}}}}}}}}}}}}****}\right\ _{B}{\text{}{}}}}{}}}}}}}}{-1}A^{{}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}T}Sy,}$

여기서 $y{\displaystyle }$ ${\displaystyle y}$도 변경할 수 있으며, $여기$서 x${\displaystyle {}^{}}$∗ ${\$ x$^{*}$는 시스템$$ $A{\displaystyle }$ ${\displaystyle x}$= ${\displaystyle b.}$ ${\displaysty Ax=b$의 솔루션이다$.$$}$ 따라서$$ $랜덤{\displaystyle {}^{}}$ 행렬 $B{\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\displaystyle {\mathrm{A}}^{}}$ ${\displaystyle {}^{}}$ ${\$displaystyle x$^{k+1}{$n1}A^{{\$displaystyle$ B$^{-1}{$n1}$A^{$ 랜덤 행렬 B - 1 ${\displaystyle A^{}}$의 열로 확장되는 선형 하위 공간에 대한 업데이트를 먼저 구속함으로써 x ${\displaystyle k^{}}$+ 1 ${\$x^{1}를 얻는다$$.$T}S$ 즉, to.

${\displaystyle \left\{h:h=B^{-1}A^{T}Sy,\quad y{\text{}은(는) 다를 수 있음 }}}$

그리고 이 서브스페이스에서$$ 가장 근사하게 x ${\$에 해당하는 $point{\displaystyle }$ x$${\$displaystyle$ $x$$^\{*\}$를 선택하면 $x{\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$ ${\$ x$^{*}$가 알려져 있지$$ 않기 때문에 근사 단계를 수행하는 것이 불가능해 보여서 이 공식은 놀라워 보일 수 있다(결국, 이것이 우리가 시도하고 있다).pute!). 그러나 단순히 x ${\displaystyle k^{}}$${\displaystyle {}^{}}$+ 1 ${\$ x$^{k+1} 이렇게$ 계산한$$ 것이 스케치와 프로젝트 제형을 통해 계산한$$ x $k{\displaystyle {}^{}}$+ ${\displaystyle 1^{}}$ ${\$와 같고, $x{\displaystyle {}^{}}$ $∗{\$는 거기에 나타나지$$ 않기 때문에 여전히 이 작업이 가능하다.

5. 임의 업데이트

또한 업데이트는 다음과 같이 명시적으로 기록될 수 있다.

${\displaystyle x^{k+1}=x^{k}-B^{-1}A^{T}S\left(S^{T}AB^{-1}A^{T}S\right)^{}^{{T}\왼쪽(Ax^{k}-b\right),}$

where by ${\displaystyle M^{\dagger }}$ we denote the Moore-Penrose pseudo-inverse of matrix ${\displaystyle M}$. Hence, the method can be written in the form ${\displaystyle x^{k+1}=x^{k}+h^{k}}$, where ${\displaystyle h^{k}}$ is a random update vector.

$허용{\displaystyle }$ M${\displaystyle }$= ${\displaystyle {}^{}}$ T ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$- 1 ${\displaystyle {}^{}{}^{}}$ T ${\displaystyle {}^{},}$ ${\displaystyle M=S^{T}$$AB^{-1}A^{T}S,}$ it can be shown that the system ${\displaystyle My=S^{T}(Ax^{k}-b)}$ always has a solution ${\displaystyle y^{k}}$, and that for all such solutions the vector ${\displaystyle x^{k+1}-B^{-1}A^{$$T}Sy^{k}}}$도 같다.따라서 이들 솔루션 중 어느 것을 선택하든 상관 없으며, 방법 또한 x ${\displaystyle k^{}}$+ ${\displaystyle 1^{}}$= ${\displaystyle {}^{}}$ k${\displaystyle {}^{}}$- B${\displaystyle {}^{}}$- 1 ${\displaystyle {\mathrm{A}}^{}}$ ${\displaystyle {}^{}{}^{}}$ ${\displaystyle S^{}}$ ${\displaystyle y^{}}$ k ${\$ x$^{k+1}=x^{k}-B^{-1}A^{$로 작성할 수 있다.$T}Sy^{k$ .사이비-반복은 단지 하나의 특정한 해결책으로 이어진다.의사-반복의 역할은 두 가지다.

• 상기 명시적인 "랜덤 업데이트" 양식으로 방법을 작성할 수 있다.
• 최종, 6차 공식화를 통해 분석을 단순화한다.

6. 무작위 고정점

랜덤 업데이트 공식의 양쪽에서$$ $∗{\$ x$^{*}$를 빼면

$[\displaystyle Z:=A^{T}S\왼쪽(S^{T}AB^{-1}A^{T}S\오른쪽)^{{\doger }S^{T}A,}$

$그리고{\displaystyle }$ A ${\displaystyle {}^{}}$ ${\displaystyle {\ast }^{}}$= ${\displaystyle b}$, ${\displaystyle Ax^{*}=b,}$이(가) 마지막 공식에 도달한다는 사실을 사용한다.

${\displaystyle x^{k+1}-x^{*}=\왼쪽(I-B^{-1}Z\오른쪽)\왼쪽(x^{k}-x^{*}\오른쪽),}$

$여기$서 I ${\displaystyle I}$은(는) ID 행렬이다.반복 매트릭스 $I{\displaystyle }$- ${\displaystyle {}^{}}$- ${\displaystyle {}^{}}$ Z${\displaystyle ,}$ ${\displaystyle I-B^{-1}Z,}$은(는) 임의로$$, 이 공식의 이름을 말한다.

수렴

6번째 공식($x{\displaystyle {}^{}}$ ${\displaystyle k^{}}$ ${\$에서 조건부 기대치를 취함으로써 얻는다.$$

$\displaystyle \mathb {E} \왼쪽.\왼쪽[x^{k+1}-x^{*}\오른쪽 x^{k}\오른쪽]=\왼쪽(I-B^{-1}\mathb {E}[Z]\오른쪽)\왼쪽[x^{k}-x^{*}\오른쪽]}$

다시 기대를 걸고, 기대의 탑 속성을 이용하여, 우리는 그것을 얻는다.

${\displaystyle \mathb {E} \left[x^{k+1}-x^{*}\right]=(I-B^{-1}\mathb {E}[Z])\mathb {E} \e} \left[x^{k}-x^{x^{*}\}\rig}\rig}\rig}\rig}\right].}$

Gower와 Richtarik은^[14] 그것을 보여준다.

${\displaystyle \rho :=\left\ I-B^{-{\frac {1}{2}}}\mathbb {E} [Z]B^{-{\frac {1}{2}}}\right\ _{B}=\lambda _{\max }\left(I-B^{-1}\mathbb {E} [Z]\right),}$

여기서 행렬 표준은 다음과 같이 정의된다.

${\displaystyle \ M\ _{B}=\max _{x\neq 0}{\frac {\mx\ _{B}}.}$

더구나 $S{\displaystyle }$ ${\displaystyle S}$에 대한 가정 없이 1은$$ $0{\displaystyle \mathrm{}}$ ${\displaystyle \le }$ ${\displaystyle \mathrm{\rho }\le }$ 1. ${\displaystyle$ 0$\leq \rho \leq 1.}$규범을 취하고 재발을 해제함으로써 우리는$$ 얻는다.

정리 [Gower & Richtarik 2015]

${\displaystyle \left\\\\mathb {E}\left[x^{k}-x^{*}\right\_{B}\{B}\leq \rho ^{k}\x^{0}-x^{*}\ _{B}.}$

레마르크. 예상되는 나머지에 충분한 조건 0으로 융합하는 것이다ρ<>1.{\displaystyle \rho<>1.}.A{A\displaystyle}완전한 칼럼 계급이 있고 S에서 매우 경미한 조건에 따라{S.\displaystyle}메서드의 수렴도에 완전한 칼럼 계급 가정 없이 설정될 수 있는 달성될 수 있다.다른 ^[15]방법

보다 강력한 결과를 보여줄 수도 있다.

정리 [Gower & Richtarik 2015]

(기대 규범이 아닌) 기대 제곱 규범은 같은 비율로 수렴한다.

${\displaystyle \mathb {E}\left\ \left[x^{k}-x^{*}\right\{B}^{2}\leq \rho^\leq \req \{k}\{0}-x^{*}\right\{B}^{2}.}$

비고. 이 두 번째 유형의 수렴은 임의 벡터 $x{\displaystyle }$ ${\displaystyle$ x$}$과(와) $고정{\displaystyle {}^{}}$ 벡터 x$$∗{\$displaystyle$ x$^{*}$에 대해 다음과 같은 정체성^[14] 때문에 더욱 강력하다$.$

${\displaystyle \left\\\mathb {E} \left[\좌]\right\^{2}=\mathb {E} \좌측[\ x-x^{}\우측]-\mathb {E} \좌측[\x]\mathb {E}\{2}\우측.}$

랜덤화 카츠마르의 수렴

We have seen that the randomized Kaczmarz method appears as a special case of the Gower-Richtarik method for ${\displaystyle B=I}$ and ${\displaystyle S}$ being the ${\displaystyle i^{th}}$ unit coordinate vector with probability ${\displaystyle p_{i}=\ a$$_{i}\ _{2}^{2}/\ A\ _{F}^{2}}}$ $여기$서 ${\displaystyle i_{}}$ ${\$는 a . ${\displaystyle$ $i^{th}$ 행의$$ ${\displaystyle i^{}}$ h ${\$displaystystyle $A.}$라고 직접 계산하여 확인할 수 있다.

${\displaystyle \rho =\ I-B^{-1}\mathb {E}[Z]\ _{B}=1-{\frac {\lambda {\\lambda _{\min }(A^{T}A)}{\A\ _{F}^{2}}.}$

추가 특수 사례

메모들

참조

• Kaczmarz, Stefan (1937), "Angenäherte Auflösung von Systemen linearer Gleichungen" (PDF), Bulletin International de l'Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques, vol. 35, pp. 355–357
• Chong, Edwin K. P.; Zak, Stanislaw H. (2008), An Introduction to Optimization (3rd ed.), John Wiley & Sons, pp. 226–230
• Gordon, Richard; Bender, Robert; Herman, Gabor (1970), "Algebraic reconstruction techniques (ART) for threedimensional electron microscopy and x-ray photography", Journal of Theoretical Biology, 29 (3): 471–481, Bibcode:1970JThBi..29..471G, doi:10.1016/0022-5193(70)90109-8, PMID 5492997
• Gordon, Richard (2011), Stop breast cancer now! Imagining imaging pathways towards search, destroy, cure and watchful waiting of premetastasis breast cancer. In: Breast Cancer - A Lobar Disease, editor: Tibor Tot, Springer, pp. 167–203
• Herman, Gabor (2009), Fundamentals of computerized tomography: Image reconstruction from projection (2nd ed.), Springer, ISBN 9781846287237
• Censor, Yair; Zenios, S.A. (1997), Parallel optimization: theory, algorithms, and applications, New York: Oxford University Press
• Aster, Richard; Borchers, Brian; Thurber, Clifford (2004), Parameter Estimation and Inverse Problems, Elsevier
• Strohmer, Thomas; Vershynin, Roman (2009), "A randomized Kaczmarz algorithm for linear systems with exponential convergence" (PDF), Journal of Fourier Analysis and Applications, 15 (2): 262–278, arXiv:math/0702226, doi:10.1007/s00041-008-9030-4, S2CID 1903919
• Needell, Deanna; Srebro, Nati; Ward, Rachel (2015), "Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm", Mathematical Programming, 155 (1–2): 549–573, arXiv:1310.5715, doi:10.1007/s10107-015-0864-7, S2CID 2370209
• Censor, Yair; Herman, Gabor; Jiang, M. (2009), "A note on the behavior of the randomized Kaczmarz algorithm of Strohmer and Vershynin", Journal of Fourier Analysis and Applications, 15 (4): 431–436, doi:10.1007/s00041-009-9077-x, PMC 2872793, PMID 20495623
• Strohmer, Thomas; Vershynin, Roman (2009b), "Comments on the randomized Kaczmarz method", Journal of Fourier Analysis and Applications, 15 (4): 437–440, doi:10.1007/s00041-009-9082-0, S2CID 14806325
• Bass, Richard F.; Gröchenig, Karlheinz (2013), "Relevant sampling of band-limited functions", Illinois Journal of Mathematics, 57 (1): 43–58, arXiv:1203.0146, doi:10.1215/ijm/1403534485, S2CID 42705738
• Gordon, Dan (2017), "A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates", Numerical Algorithms, 77 (4): 1141–1157, doi:10.1007/s11075-017-0356-3, S2CID 1794974
• Vinh Nguyen, Quang; Lumban Gaol, Ford (2011), Proceedings of the 2011 2nd International Congress on Computer Applications and Computational Science, vol. 2, Springer, pp. 465–469
• Gower, Robert; Richtarik, Peter (2015a), "Randomized iterative methods for linear systems", SIAM Journal on Matrix Analysis and Applications, 36 (4): 1660–1690, arXiv:1506.03296, doi:10.1137/15M1025487, S2CID 8215294
• Gower, Robert; Richtarik, Peter (2015b), "Stochastic dual ascent for solving linear systems", arXiv:1512.06890 [math.NA]

외부 링크

• [1] 지수 수렴을 갖는 임의의 Kaczmarz 알고리즘
• [2] 랜덤화 Kaczmarz 방법에 대한 의견