के-एसवीडी

व्यावहारिक गणित में, k-SVD एकल मूल्य अपघटन दृष्टिकोण के माध्यम से, विरल प्रतिनिधित्व के लिए शब्दकोश बनाने के लिए शब्दकोश सीखने का एल्गोरिदम है। k-SVD, k-मीन्स क्लस्टरिंग|k-मीन्स क्लस्टरिंग विधि का सामान्यीकरण है, और यह वर्तमान शब्दकोश के आधार पर इनपुट डेटा को विरल कोडिंग के बीच पुनरावृत्त रूप से बदलकर और डेटा को बेहतर ढंग से फिट करने के लिए शब्दकोश में परमाणुओं को अपडेट करके काम करता है। यह संरचनात्मक रूप से अपेक्षा अधिकतमकरण (ईएम) एल्गोरिदम से संबंधित है। के-एसवीडी को इमेज प्रोसेसिंग, ऑडियो प्रोसेसिंग, जीव विज्ञान और दस्तावेज़ विश्लेषण जैसे अनुप्रयोगों में व्यापक रूप से उपयोग में पाया जा सकता है।

के-एसवीडी एल्गोरिथ्म

k-SVD, k-साधनों का प्रकार का सामान्यीकरण है, जो इस प्रकार है। K-मीन्स क्लस्टरिंग|k-मीन्स क्लस्टरिंग को विरल प्रतिनिधित्व की विधि के रूप में भी माना जा सकता है। अर्थात्, डेटा नमूनों का प्रतिनिधित्व करने के लिए सर्वोत्तम संभव कोडबुक ढूंढना $\{y_{i}\}_{i=1}^{M}$ निकटतम पड़ोसी खोज द्वारा, हल करके

$\quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\forall i,x_{i}=e_{k}{\text{ for some }}k.$

जो लगभग बराबर है

$\quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i,\|x_{i}\|_{0}=1$

जो कि k-मीन्स है जो वज़न की अनुमति देता है।

अक्षर F फ्रोबेनियस मानदंड को दर्शाता है। विरल प्रतिनिधित्व शब्द $x_{i}=e_{k}$ शब्दकोश में केवल परमाणु (स्तंभ) का उपयोग करने के लिए k-मीन्स एल्गोरिदम लागू करता है $D$. इस बाधा को कम करने के लिए, के-एसवीडी एल्गोरिदम का लक्ष्य सिग्नल को परमाणुओं के रैखिक संयोजन के रूप में प्रस्तुत करना है $D$.

के-एसवीडी एल्गोरिदम के-मीन्स एल्गोरिदम के निर्माण प्रवाह का अनुसरण करता है। हालाँकि, k-साधनों के विपरीत, परमाणुओं के रैखिक संयोजन को प्राप्त करने के लिए $D$, बाधा के विरल पद को शिथिल कर दिया गया है ताकि प्रत्येक कॉलम की गैर-शून्य प्रविष्टियों की संख्या हो $x_{i}$ 1 से अधिक, लेकिन संख्या से कम हो सकता है $T_{0}$.

तो, वस्तुनिष्ठ फलन बन जाता है

$\quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i\;,\|x_{i}\|_{0}\leq T_{0}.$

या किसी अन्य वस्तुनिष्ठ रूप में

$\quad \min \limits _{D,X}\sum _{i}\|x_{i}\|_{0}\qquad {\text{subject to }}\quad \forall i\;,\|Y-DX\|_{F}^{2}\leq \epsilon .$

K-SVD एल्गोरिथम में, $D$ पहला निश्चित और सर्वोत्तम गुणांक मैट्रिक्स है $X$ पाया जाता है। वास्तव में इष्टतम खोजने के रूप में $X$ कठिन है, हम सन्निकटन खोज पद्धति का उपयोग करते हैं। ओएमपी जैसे किसी भी एल्गोरिदम, ऑर्थोगोनल मिलान खोज का उपयोग गुणांक की गणना के लिए किया जा सकता है, जब तक कि यह गैर-शून्य प्रविष्टियों की निश्चित और पूर्व निर्धारित संख्या के साथ समाधान प्रदान कर सकता है $T_{0}$.

विरल कोडिंग कार्य के बाद, अगला कार्य बेहतर शब्दकोश की खोज करना है $D$. हालाँकि, समय में संपूर्ण शब्दकोश ढूँढना असंभव है, इसलिए प्रक्रिया शब्दकोश के केवल कॉलम को अद्यतन करने की है $D$ हर बार, ठीक करते समय $X$. का अद्यतन $k$-वें कॉलम को दंड अवधि के रूप में फिर से लिखकर किया जाता है

$\|Y-DX\|_{F}^{2}=\left\|Y-\sum _{j=1}^{K}d_{j}x_{j}^{\text{T}}\right\|_{F}^{2}=\left\|\left(Y-\sum _{j\neq k}d_{j}x_{j}^{\text{T}}\right)-d_{k}x_{k}^{\text{T}}\right\|_{F}^{2}=\|E_{k}-d_{k}x_{k}^{\text{T}}\|_{F}^{2}$

कहाँ $x_{k}^{\text{T}}$ X की k-वीं पंक्ति को दर्शाता है।

गुणन विघटित करके $DX$ के योग में $K$ रैंक 1 मैट्रिक्स, हम दूसरे को मान सकते हैं $K-1$ शर्तों को निश्चित माना जाता है, और $k$-वह अज्ञात रहता है. इस चरण के बाद, हम न्यूनतमकरण समस्या को अनुमानित रूप से हल कर सकते हैं $E_{k}$ ए के साथ शब्द $rank-1$ मैट्रिक्स एकवचन मूल्य अपघटन का उपयोग कर, फिर अद्यतन करें $d_{k}$ इसके साथ। हालाँकि, वेक्टर का नया समाधान $x_{k}^{\text{T}}$ इसके भरे जाने की बहुत संभावना है, क्योंकि विरलता बाधा लागू नहीं की गई है।

इस समस्या को ठीक करने के लिए परिभाषित करें $\omega _{k}$ जैसा

$\omega _{k}=\{i\mid 1\leq i\leq N,x_{k}^{\text{T}}(i)\neq 0\},$

जो उदाहरणों की ओर इशारा करता है $\{y_{i}\}_{i=1}^{N}$ जो परमाणु का उपयोग करता है $d_{k}$ (की प्रविष्टियाँ भी $x_{i}$ वह शून्येतर है)। फिर, परिभाषित करें $\Omega _{k}$ आकार के मैट्रिक्स के रूप में $N\times |\omega _{k}|$, पर वालों के साथ $(i,\omega _{k}(i)){\text{th}}$ प्रविष्टियाँ और शून्य अन्यथा। गुणा करते समय ${\tilde {x}}_{k}^{\text{T}}=x_{k}^{\text{T}}\Omega _{k}$, इससे पंक्ति वेक्टर सिकुड़ जाता है $x_{k}^{\text{T}}$ शून्य प्रविष्टियों को त्यागकर। इसी प्रकार, गुणन ${\tilde {Y}}_{k}=Y\Omega _{k}$ उन उदाहरणों का सबसेट है जो वर्तमान में उपयोग किए जा रहे हैं $d_{k}$ परमाणु. पर भी वैसा ही असर देखने को मिल सकता है ${\tilde {E}}_{k}=E_{k}\Omega _{k}$.

तो जैसा कि पहले उल्लेख किया गया है न्यूनतमकरण समस्या बन जाती है

$\|E_{k}\Omega _{k}-d_{k}x_{k}^{\text{T}}\Omega _{k}\|_{F}^{2}=\|{\tilde {E}}_{k}-d_{k}{\tilde {x}}_{k}^{\text{T}}\|_{F}^{2}$

और सीधे एसवीडी का उपयोग करके किया जा सकता है। एसवीडी विघटित हो जाता है ${\tilde {E}}_{k}$ में $U\Delta V^{\text{T}}$. के लिए समाधान $d_{k}$ यू का पहला स्तंभ है, गुणांक वेक्टर ${\tilde {x}}_{k}^{\text{T}}$ के पहले कॉलम के रूप में $V\times \Delta (1,1)$. संपूर्ण शब्दकोश को अद्यतन करने के बाद, प्रक्रिया फिर X को पुनरावृत्तीय रूप से हल करने, फिर पुनरावृत्तीय रूप से D को हल करने की ओर मुड़ जाती है।

सीमाएँ

डेटासेट के लिए उपयुक्त शब्दकोश चुनना गैर-उत्तल समस्या है, और के-एसवीडी पुनरावृत्त अद्यतन द्वारा संचालित होता है जो वैश्विक इष्टतम खोजने की गारंटी नहीं देता है।हालाँकि, इस उद्देश्य के लिए यह अन्य एल्गोरिदम के लिए सामान्य है, और k-SVD व्यवहार में काफी अच्छी तरह से काम करता है।

यह भी देखें

• विरल सन्निकटन
• विलक्षण मान अपघटन
• मैट्रिक्स मानदंड
• k-मतलब क्लस्टरिंग|k-मतलब क्लस्टरिंग
• निम्न-श्रेणी सन्निकटन