크라우드 내 알고리즘

크라우드 내 알고리즘은 크고 희박한 문제에 대한 다른 알고리즘보다 빠르게 디노잉된 기본 추구를 해결하기 위한 숫자 방법이다.^[1]이 알고리즘은 능동적인 세트 방식으로, 다음과 같이 디노잉되는 글로벌 베이시스 추구의 하위 문제를 최소화한다.

${\displaystyle \min _{x}{\frac {1}{1}:{2}}\ y-Ax\ _{2}^{2}+\lambda \ x\ _{1}.}$

여기서 $y{\displaystyle }$ ${\displaystyle y}$은(는) 관측된 신호, $x{\displaystyle }${\$displaystyle x$}은$$(는) 복구해야 할 스파스 신호, ${\displaystyle a}$ $x{\displaystyle }$ ${\displaystyle Ax}$은(는) $x{\displaystyle }$ ${\displaystyle x}$에서 예상되는 신호,$$$\lambda }$은 신호 충실성과 단순성을 트레이딩하는 정규화 매개 변수다.단순성은 솔루션 $x{\displaystyle }$ ${\displaystyle x}$의 sparsity를 사용하여 측정하며,$$$its{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$-norm을$$ 통해 측정한다.활성 세트 전략은 0이 아닌 계수가 거의 예상되지 않기 때문에 이 맥락에서 매우 효율적이다.따라서 이러한 계수에 제한된 문제를 해결할 수 있다면 해결책이 나온다.여기서 형상은 현재 추정치에서 구배 절대값을 기준으로 탐욕스럽게 선택된다.

기본 추구 디노잉을 위한 다른 활성 설정 방법으로는 문제의 이중성 갭을 사용하여 활성 세트를 선택하는 ^[2]BLITZ와 그 신호의 추정에 따라 형상이 포함되는 The Feature Sign Search가 있다.^[3]

알고리즘.

다음과 같이 구성된다.

1. $x{\displaystyle }$ ${\displaystyle x}$을(를) 0으로 선언하여 설명할 수 없는 ${\displaystyle \mathrm{잔차}}$ $r{\displaystyle }$= y ${\displaystyle r=y}$
2. 활성 집합 $I{\displaystyle }$ ${\displaystyle I}$을(를) 빈 집합으로 선언
3. $I{\displaystyle {}^{}}$ ${\displaystyle c^{}}$ ${\$ I$^{c}$의 각 구성 요소에 대해$$ 유용성 $u{\displaystyle {}_{}}$ ${\displaystyle j_{}}$= ${\displaystyle ⟨}$ ${\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\displaystyle {}_{}}$ $displaystyle u_{j}= \langle rA_{j}\angle }}}$을(를) 계산하십시오.
4. $I{\displaystyle {}^{}}$ ${\displaystyle c^{}}$ ${\$에서 j >{\$displaystyle u_{j}>\lambda$ 종료되지 않는 경우
5. 그렇지 않으면 $L{\displaystyle }$≈ ${\displaystyle 25}$ ${\displaystyle L\$약$25}$개의 구성요소를$$ $그{\displaystyle }$ 유용성에 따라$$ I ${\displaystyle I}$에 추가하십시오.
6. $I{\displaystyle }$ ${\displaystyle I$에서 정확하게 식별되는 기본 추적을 해결하고 값이 정확히 0에 도달하는$$ $I{\displaystyle }$ ${\displaystyle I}$의 모든 구성 요소를 폐기하십시오.이 문제는 밀도가 높기 때문에 2차 프로그래밍 기법이 이 하위 문제에 매우 효과적이다.
7. 업데이트 $r{\displaystyle }$= ${\displaystyle y}$- a ${\displaystyle x}$ ${\displaystyle r=y-Ax}$ $$- n.b.는 $I{\displaystyle }$ ${\displaystyle I}$ 외부의 모든 요소가 0이므로$$ 하위 문제에서 계산할 수 있다.
8. 3단계로 이동하십시오.

크라우드 내 알고리즘이 전역 검색을 수행할 때마다 $L{\displaystyle }$ ${\displaystyle$ L$} 구성요소$를 활성$$ 집합에 추가하므로, 이 검색이 계산적으로 비쌀 때 최상의 대체 알고리즘보다 $L{\displaystyle }$ ${\displaystyle L}$의 요인이 될 수 있다.정리는^[1] 크라우드 내 알고리즘의 많은 시간 속성에도 불구하고 글로벌 최적화에 도달함을 보장한다.

메모들

이 응용 수학 관련 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.

• v
• t