희소 근사치

희소 근사(희소 표현이라고도 함) 이론은 선형 방정식의 시스템에 대한 희소성 솔루션을 다룬다. 이러한 솔루션을 찾아 애플리케이션에서 활용하기 위한 기술은 이미지 처리, 신호 처리, 머신러닝, 의료 이미징 등에 광범위하게 사용되고 있다.

희소 분해

무소음 관측치

Consider a linear system of equations ${\displaystyle x=D\alpha }$, where ${\displaystyle D}$ is an underdetermined ${\displaystyle m\times p}$ matrix ${\displaystyle (m<p)}$ and ${\displaystyle x\in \mathbb {R} ^{m},\alpha \in \mathbb {R} ^{p}}$. 행렬 $D{\displaystyle }$ ${\displaystyle D}($일반적으로 전체 순위라고 가정함)을 사전이라고 하며, $x{\displaystyle }$ ${\displaystyle x}$은 관심 신호다. 핵심 희소성 표현 문제는 가장 빠른 표현${\displaystyle \alpha }$ ${\displaystyle \alpha }$을(를) ${\displaystyle \mathrm{만족}}$시키는 x$$= D$α$ {\$displaystyle$ x=D\$alpha }}}$을(를) 위한 탐색으로 정의된다$.$ $D{\displaystyle }${\$displaystystyle$D}의 불충분한 성격 때문에 이 선형 시스템은 일반적으로 가능한 해결책들을 무한히 인정하고 있다.0이 가장 적은 자를 찾아라 정식으로 말하면, 우리는 해결한다.

${\displaystyle \min _{\alpha \in \mathb {R} ^{p}\ \alpha \{0}{\text{}}}}}의 적용을 받는다.$

where ${\displaystyle \ \alpha \ _{0}=\#\{i:\alpha _{i}\neq 0,\,i=1,\ldots ,p\}}$ is the ${\displaystyle \ell _{0}}$ pseudo-norm, which counts the number of non-zero components of ${\displaystyle \alpha }$. This problem is known to be NP-hard with a reduction to NP-com조합 최적화에 부분 집합 선택 문제를 제기한다.

$\alpha {\displaystyle }$ ${\displaystyle \alpha$}의 sparsity는 그 안에 있는 일부( m < ${\displaystyle k\ll m<p$ 성분만 0이 아님을 의미한다$$. 그러한 희박한 분해의 근본적인 동기는 원자라고도 하는$$$D{\displaystyle }$ ${\displaystyle$ D$}$에서 가능한 한 적은 수의 열의 선형 결합으로서 x$$ ${\displaystyle x}$의 가능한 가장 간단한 설명을 제공하고자 하는 욕망이다. 이와 같이 신호 $x{\displaystyle }$ ${\displaystyle x}$은(는$)$ D {\$displaystyle D}$에서 가져온 몇 가지 기본 원소로 구성된 분자로 볼 수 있다$$$.$

위와 같은 문제가 실제로 NP-Hard인 반면, 그것의 해결책은 근사 알고리즘을 사용하여 종종 찾을 수 있다. 그러한 옵션 중 하나는 문제의 볼록한 완화로서,$$${\displaystyle {\ell \mathrm{}}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$$ell _{$1}-norm을$$ 사용하여 { 0 {\$displaystyle$ \$ell$$_$${0$$}$ 대신 ℓ${\displaystyle \alpha }$ α$\alpha {\displaystyle }$${\displaystyle {}_{}}$1 ${\$$displaystystyle \alpha \{$$1}{$1}의 입력의 절대값을 단순하게$$ 요약하여 얻음. p. p. 이를 근거로 알려져 있다$.$선형 프로그래밍 해결기를 사용하여 처리할 수 있는 BP 알고리즘. 대안적 근사법은 0이 아닌 사람의 위치를 한 번에 하나씩 찾아내는 매칭추적(MP)과 같은 탐욕스러운 기법이다.

놀랍게도 $D{\displaystyle }$ ${\displaystyle D}($스파크(수학) 사용, 상호 일관성 또는 제한된 등거리 측정 속성)의 가벼운 조건 하에서 용액의 첨사성 수준, $k{\displaystyle }$ ${\displaysty k$ 희소 표현 문제는 독특한 해결책이 있음을 보여줄 수 있으며, BP와 MP는 완벽함을 보장받을 수 있다.리의^[1]

잡음 관측치

관측된 신호 $x{\displaystyle }$ ${\displaystyle x}$은(는) 노이즈가 있는 경우가$$ 많다. ${\displaystyle {데이터\mathrm{}}_{}}$ 적합 용어에 $display$ 2 {\displaystyle$\ell _{2$}} -노orm을$$ 부과함으로써 희박한 분해 문제가 된다.

${\displaystyle \min _{\alpha \in \mathb {R} ^{p}\ \alpha \{0}{0}{\text{{2}\^{2}\leq \epsilon ^{2},}의 적용을 받는다.$

아니면 라그랑쥬의 형태를 취하거나

${\displaystyle \min _{\alpha \in \mathb {R} ^{p}\lambda \ \alpha \ \{0}+{1}{1}{1}}\x-D\alpha \ _{2}^{2},}}}}$

여기서 $\lambda {\displaystyle }$ ${\displaystyle \lambda }$은(는) $ϵ{\displaystyle }$ ${\displaystyle \epsilon }$을(를) 대체하고 있다$$$.$

무소음 사례에서와 마찬가지로 이 두 가지 문제는 일반적으로 NP-Hard이지만 추적 알고리즘을 사용하여 근사치를 산출할 수 있다. 구체적으로는 $\ell {\displaystyle {}_{}}$ ${\$을 $\ell {\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$-normal로$$ 변경하면 얻을 수 있다.

${\displaystyle \min _{\alpha \in \mathb {R} ^{p}\lambda \ \alpha \ \{1}+{1}{1}{1}:{1}}\\x-D\alpha \ _{2}^{2},}}}}$

'근거 추구의 폄하'로 알려져 있다. 이와 유사하게, 일치 추구는 오류 임계값이 충족될 때까지 한 번에 하나씩 비 0의 위치를 찾으면서 위의 문제 해결책의 근사치를 위해 사용될 수 있다. 여기서도 이론적 보증은 BP와 MP가 $D{\displaystyle }$ ${\displaystyle D}$의 특성과 솔루션 $k{\displaystyle }$ ${\displaystyle k}$의 카디널리티에 따라 거의 최적의 솔루션으로 이어진다는 것을 시사한다$.$ $또{\displaystyle }$ 다른^[5][6] 흥미로운 이론적 결과는 D ${\displaystyle D}$이 단일 매트릭스인 경우를 가리킨다. 이러한 가정 하에서 위에서 제기된 문제들( ( ${\displaystyle {0\mathrm{}}_{}}$ ${\$ 또는$$ $\ell {\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$은 비선형 수축 형태의 폐쇄형 솔루션을 인정한다.^[4]

변형

기본적인 희박한 근사 문제에는 몇 가지 변화가 있다.

구조화된 첨탑성: 문제의 원판에서는 사전의 원자를 어느 것이나 고를 수 있다. 구조화된 (블록형) 첨사성 모델에서는 원자를 개별적으로 고르는 대신 그 그룹들을 고르게 된다. 이러한 그룹은 중복될 수 있고 크기가 다양할 수 있다. $목표$는 이 블록 구조를 강제하는 동안 희박하게 x ${\displaystyle x}$을(를) 표시하는 것이다.^[7]

협업(공동) 스파스 코딩: 문제의 원래 버전은 단일 신호 $x{\displaystyle }$ ${\displaystyle x}$에 대해 정의된다$.$ 협업(공동) 희소 코딩 모델에서는 $각각{\displaystyle }$ D ${\displaystyle$ D$}$의 동일한 원자 집합에서 (근접하게) 나오는 것으로 여겨지는 일련의 신호를 사용할 수 있다$.$ 이 경우, 추적 작업은 일련의 희소 표현을 복구하는 것을 목표로 한다. 데이터를 가장 잘 설명하는 동시에 동일(또는 근접 지원) 지원을 공유하도록 강요하는 것.^[8]

기타 구조: 보다 광범위하게, 희박한 근사 문제는 $\alpha {\displaystyle }$ ${\displaystyle \alpha }$의 비 영점 위치 패턴에 특정 원하는 구조를 강요하면서 주조될 수 있다$.$ 광범위하게 연구된 두 가지 관심 사례는 나무 기반 구조, 그리고 더 일반적으로 볼츠만 분산 지원이다.^[9]

알고리즘

위에서 이미 언급했듯이, 희박한 표현 문제를 해결하기 위해 개발된 다양한 근사치(추적이라고도 함) 알고리즘이 있다.

${\displaystyle \min _{\alpha \in \mathb {R} ^{p}\ \alpha \{0}{0}{\text{{2}\^{2}\leq \epsilon ^{2}의 적용을 받는다.}$

우리는 아래 몇 가지 주요 방법을 언급한다.

• 매칭추구는 위의 문제를 대략적으로 해결하기 위한 욕심 많은 반복 알고리즘이다. $\alpha {\displaystyle }$ ${\displaystyle \alpha }$에서 비 0의 위치를 한 번에 하나씩$$ 점진적으로 찾아내는 방식으로 작동한다. 핵심 아이디어는 각 단계에서 $D{\displaystyle }$ ${\displaystyle$ $D$$}$의 열(원자)과 현재 잔차($x{\displaystyle }$ ${\displaystyle$ x$}$로 초기화됨)$$와 가장 잘 상관관계가 있는 것을$$ 찾은 다음 이 잔차를 업데이트하여 새 원자와 그 계수를 고려하는 것이다. 일치하는 추적은 동일한 원자를 여러 번 선택할 수 있다.
• 직교 일치 추구는 일치하는 추구와 매우 유사하며, 하나의 큰 차이점이 있다: 각 알고리즘 단계에서 0이 아닌 계수는 최소 제곱으로 업데이트된다. 그 결과 잔차는 이미 선택된 원자와 직교하므로 원자는 한 번 이상 선택할 수 없다.
• 단계별 탐욕스러운 방법: 위에 비해 개선된 편차는 (i) 한 번에 0이 아닌 0의 그룹을 추가할 수 있는 기능, (ii) 여러 개의 원자가 지지대에서 폐기되는 각 라운드에서 가지치기 단계를 포함하는 두 가지 중요한 특징을 추가하면서 탐욕스럽게 작동하는 알고리즘이다. 이 접근방식의 대표자는 Subspace-Pursuit 알고리즘과 CoSaMP이다.^[10]

• 베이시스 추구는 $\ell {\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$을 ${\displaystyle {\ell \mathrm{}}_{}}$ 1 ${\$} -norm로$$$$ 대체함으로써 문제의 볼록한 완화된 버전을 해결한다. 이는 새로운 목표만 정의하며, 원하는 솔루션을 얻기 위해 사용할 알고리즘의 문제는 열어둔다는 점에 유의하십시오. 일반적으로 그러한 알고리즘은 IRLS, LARS 및 반복 소프트 수축 방법이다.^[11]

• 희박한 분해 문제를 해결하는 방법으로는 호모토피법, 좌표강하법, 반복적 하드리스홀딩법, 1차 근위법 등이 있는데, 이는 위에서 언급한 반복적 소프트 수축 알고리즘과 관련된 것으로, 단치히 선택기와 관련이 있다.

적용들

희박한 근사 아이디어와 알고리즘은 신호 처리, 이미지 처리, 기계 학습, 의료 영상 처리, 배열 처리, 데이터 마이닝 등에 광범위하게 사용되어 왔다. 이러한 어플리케이션의 대부분에서, 관심의 알 수 없는 신호는 주어진 사전에서 나온 몇 개의 원자의 희박한 조합으로 모델링되며, 이것은 문제의 정규화로 사용된다. 이러한 문제에는 일반적으로 $D{\displaystyle }$ {\$displaystyle D}$을(를$)$ 해당 데이터와 가장 잘 일치시키는$$ 것을 목표로 하는 사전 학습 메커니즘이 수반된다. 첨탑에 영감을 받은 모델의 사용으로 인해 다양한 어플리케이션에서 최첨단 결과가 나왔다.^[12][13][14] 최근의 연구는 희박한 표현 모델과 딥러닝 사이에는 밀접한 관계가 있음을 시사한다.^[15]

참고 항목

• 압축 감지
• 희소 사전 학습
• K-SVD
• 라소(통계)
• 정규화(수학) 및 역문제

참조