불꽃 제거: 제3장 추적 알고리즘

3835 단어 Python

제3장 추적 알고리즘의 알고리즘은 Python에서 실현된다.
불꽃이 사방으로 튀다 ．
다음과 같은 탐욕법과 완화 수법을 실시한다. IRLS가 수상한데..

탐욕법

OMP

직교 일치 추적

일치 추적(matching pursuit, MP)

약한 일치 추적(weak matching pursuit, WMP)

임계값 알고리즘

완만하고 돌출된 수법

중복 가중권의 최소 2승법(iterative reweightted-lease-sqaurs;IRLS)

탐욕법의 개요

초기화

$k=0$으로

$\mathbf{x}^{0}=\mathbf{0}달러

초기 해제

초기 잔차 $\mathbf{r}^{0} =\mathbf{b}달러

풀기 초기 지원 $S^{0} =\emptyset 달러

주 순환

다음 단계를 수행합니다.

오차 계산, 업데이트 지원: $\mathbf{A}에서 최잔차 $\mathbf{r}^{k}달러의 열을 빼기$\mathbf{a}$S^k달러

에 달러 추가

잠정계 업데이트:\$|mathbf{Ax]-\mathbf{b]\^{2}{2}\,\rm{subject}\,rm{to}\,\rm{Support}\{mathbf{x}=^{k}달러의 최적 해설은 $\mathbf{x}^{k}달러

잔차 업데이트: $\mathbf{r}^{k}=\mathbf{b]-\mathbf{Ax}^{k}달러 계산

중지 조건:{0} 달러 종료, 그렇지 않으면 중복
계산 오류, 업데이트 지원 $\mathbf{A}모든 열$\mathbf{a}내적 $\mathbf{r}과 잔차 $\mathbf{r}의 내적을 계산하여 내적의 절대값을 지원에 추가합니다.

탐욕법 알고리즘의 차이

OMP
유지

이상

$\mathbf{A}달러\mathbf{a} 대신 새로운 지원 추가j달러만 업데이트 잠정 해제

WMP

$t\, (0

오차 계산 및 업데이트 지원 $\mathbf{r]^{k-1} 및 내적의 절대값은 $t\|\mathbf{r}^{k-1}\|$\mathbf{a}j$를 찾으면 계산을 중지합니다

한도값 알고리즘

지원에 포함된 기본 함수 개수 $k$k를 슈퍼 매개 변수

에 추가

와 $\mathbf{b}달러의 내적 절대치의 큰 $\mathbf{a}j$k에서 $k$를 지원합니다. 그리고 최소 2 곱하기 문제를 해결하십시오 $\mathbf{x}.

IRLS의 개요

$\left(P{0}\right)$문제가 아니라 문제 해결

가중 $L달러 할당량 $L{1}근사정액구해$\left(P{1}\right)$문제

해석을 얻기 위해 반복적으로 진행해야 한다

초기화

$k=0$으로

초기 근사해\mathbf{x]^{0}=\mathbf{1}$(전체 1개 벡터)

초기 가중치 매트릭스 $\mathbf{X}^{0} =\mathbf{I}달러

주 순환

다음 단계를 수행합니다.

최소 2승법: 선형 연립 방정식 $\mathbf{x}{k} =\mathbf{X}_{k-1]^{2}\mathbf{A}(\mathbf{A}\mathbf{X] {k-1}^{2}\mathbf{A})^{+}\mathbf{b}직접 또는 중복법으로 $, 근사해 $\mathbf{x}득k$.

가중치 업데이트: $X{k}(j,j)=|x_{k}(j)|^{0.5} 가중 대각선 행렬 업데이트 $\mathbf{X}달러

중지 조건: $\\\mathbf{x}{k}-\mathbf{x}_{k-1}\|_${2}이 미리 정해진 한도값보다 작으면 끝납니다.

실험

모방하다

50차원 벡터
30 차원 벡터
$\mathbf{A}$ 30×50차원 행렬, $[1,1)$의 균일 무작위 수열 귀일화

달러\mathbf{x}는 비영원소의 수량 $k로 $[-2,-1]\cup[1,2]달러 범위의 고른 분포에서 id를 추출한다.

$k=1,...,10달러당 200회 시뮬레이션

지표

예상 $\mathbf{\hat{x} 및 실제 $\mathbf{x}의 $L2달러 기준

예상 $\mathbf{\hat{x}와 실제 $\mathbf{x} 사이의 지원 거리 $dist(\hat{S}, S)=\racc{max\{{{{{{{{{{{{{{|hat{S}|,|S|||||S|||||||||||||||||||||||||||||||||||||||||||||hat{S}\cap S||||||||||||||||||||

200회 아날로그 평균 획득