🔢 mathematics

Randomized Tensor Krylov Subspace Methods via Sketched Einstein Product with Applications to Image and Video Restoration

यह शोध पत्र रैंडमाइज्ड टेंसर ग्लोबल GMRES (RTG-GMRES) विधि प्रस्तुत करता है, जो इमेज और वीडियो रिस्टोरेशन के लिए बड़े पैमाने के मल्टीलिनियर सिस्टम को कुशलतापूर्वक हल करने हेतु स्केच्ड आइंस्टीन उत्पादों और मोड-वाइज रैंडम प्रोजेक्शन का उपयोग करता है, जिससे अभिसरण (कन्वर्जेंस) बनाए रखते हुए ऑर्थोगोनलाइजेशन की कम्प्यूटेशनल लागत को काफी कम किया जा सके।

मूल लेखक: Achraf Badahmane

प्रकाशित 2026-03-03

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC0 1.0

मूल लेखक: Achraf Badahmane

मूल पेपर CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/) के तहत सार्वजनिक डोमेन को समर्पित है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक सुंदर, पुरानी पारिवारिक फोटो को ठीक करने की कोशिश कर रहे हैं जो बारिश से धुंधली हो गई है और स्टैटिक शोर (static noise) से ढकी हुई है। या शायद आप फुटबॉल के एक मैच के धुंधले, हिलते हुए वीडियो को ठीक करने की कोशिश कर रहे हैं। इमेज और वीडियो रेस्टोरेशन (Image and Video Restoration) इसी बारे में है: एक बिखरी हुई, क्षतिग्रस्त तस्वीर को लेना और गणित का उपयोग करके यह अनुमान लगाना कि मूल, पूर्ण तस्वीर कैसी दिखती थी।

लंबे समय तक, कंप्यूटरों ने इसे एक तस्वीर को संख्याओं की एक विशाल, सपाट सूची में बदलकर हल करने की कोशिश की है (जैसे ऊन के एक 3D गोले को एक लंबी सिंगल स्ट्रिंग में खोल देना)। लेकिन यह छवि की प्राकृतिक संरचना को नष्ट कर देता है (जैसे यह भूल जाना कि रेड चैनल ब्लू चैनल से अलग है) और गणित को अविश्वसनीय रूप से धीमा और भारी बना देता है।

यह शोध पत्र इस काम को तेजी से करने का एक चतुर नया तरीका पेश करता है, जो "स्केच्ड आइंस्टीन प्रोडक्ट के माध्यम से रैंडमाइज्ड टेंसर क्रायलोव सबस्पेस मेथड्स" (Randomized Tensor Krylov Subspace Methods via Sketched Einstein Product) की अवधारणा का उपयोग करता है।

यह सुनने में बहुत कठिन लग सकता है! आइए इसे सरल उपमाओं (analogies) के साथ एक कहानी में तोड़ते हैं।

1. समस्या: "विशाल पुस्तकालय" की उपमा

कल्पना कीजिए कि आपकी छवि एक विशाल, बहु-मंजिला पुस्तकालय है।

पुराना तरीका (शास्त्रीय विधियाँ): एक विशिष्ट पुस्तक (समाधान) खोजने के लिए, एक लाइब्रेरियन को हर एक मंजिल पर हर एक गलियारे से गुजरना होगा, और यह सुनिश्चित करने के लिए हर एक किताब की जांच करनी होगी कि वे उन्हें पूरी तरह से व्यवस्थित कर रहे हैं। यह सटीक है, लेकिन इसमें बहुत समय लगता है। यदि पुस्तकालय बहुत बड़ा है (जैसे कि 4K वीडियो), तो लाइब्रेरियन पहला फ्लोर खत्म करने से पहले ही थक जाएगा।
"टेंसर" वाला हिस्सा: पुस्तकालय को एक लंबे गलियारे में खोलने के बजाय, यह शोध पत्र पुस्तकालय को एक 3D इमारत के रूप में रखता है। यह मंजिलों, विंग्स और सेक्शनों का सम्मान करता है। यह बहुत अधिक कुशल है, लेकिन इस 3D इमारत में हर किताब की जांच करना अभी भी बहुत धीमा है।

2. समाधान: "स्केचिंग" का शॉर्टकट

लेखक एक नया तरीका प्रस्तावित करते हैं जिसे "स्केचिंग" (Sketching) कहा जाता है।

कल्पना कीजिए कि आप उस विशाल पुस्तकालय में अपराध सुलझाने की कोशिश कर रहे हैं एक जासूस हैं। उस इमारत के हर व्यक्ति का इंटरव्यू लेने के बजाय, आप रैंडम स्केच आर्टिस्ट्स (random sketch artists) की एक टीम को काम पर रखते हैं।

ये कलाकार हर किसी को नहीं देखते। वे जल्दी से लोगों के रैंडम समूहों पर एक नज़र डालते हैं और भीड़ के सामान्य मिजाज का एक मोटा, त्वरित "स्कैच" बनाते हैं।
जादू: भले ही स्केच छोटे और कच्चे हों, वे भीड़ के अनिवार्य आकार को पकड़ लेते हैं। आप हजारों लोगों का इंटरव्यू लेने के बजाय इन छोटे स्केच का उपयोग करके अपना रहस्य सुलझा सकते हैं।

शोध पत्र में, यह "रैंडमाइज्ड स्केचिंग" (Randomized Sketching) है। यह विशाल, जटिल गणितीय समस्या को अपने ही एक बहुत छोटे, सरल संस्करण पर प्रोजेक्ट करता है। यह एक हाई-रिज़ॉल्यूशन फोटो को थंबनेल में छोटा करने जैसा है ताकि गणना की जा सके, और फिर परिणाम प्राप्त करने के लिए वापस ज़ूम किया जा सके।

3. "आइंस्टीन प्रोडक्ट": विशेष गोंद

3D छवियों (जैसे रंगीन फोटो या वीडियो) के साथ काम करने के लिए, गणित को चीजों को एक साथ गुणा करने का एक विशेष तरीका चाहिए।

मानक गणित: आमतौर पर सब कुछ एक सपाट शीट के रूप में मानता है।
आइंस्टीन प्रोडक्ट: इसे एक विशेष 3D गोंद के रूप में सोचें। यह कंप्यूटर को छवि की परतों (लाल, हरा, नीला और वीडियो के लिए समय) को इस तरह से आपस में गुणा करने की अनुमति देता है जिससे उनके 3D संबंध बरकरार रहें। यह सुनिश्चित करता है कि छवि का "लाल" हिस्सा "नीले" हिस्से के साथ मिक्स होने के बजाय, ब्लर के "लाल" हिस्से से जुड़ा रहे।

4. नया एल्गोरिदम: "फास्ट-फॉरवर्ड" बटन

यह शोध पत्र इन विचारों को एक नए एल्गोरिदम (जिसे RTG-GMRES कहा जाता है) में जोड़ता है।

यह कैसे काम करता है: पूरे पुस्तकालय में घूमने के (पूर्ण गणित) बजाय, यह एल्गोरिदम पुस्तकालय का एक छोटा, प्रबंधनीय मॉडल बनाने के लिए "स्केच आर्टिस्ट्स" (रैंडम प्रोजेक्शन) का उपयोग करता है।
परिणाम: यह इस छोटे मॉडल पर रेस्टोरेशन की समस्या को हल करता है। क्योंकि मॉडल बहुत छोटा है, कंप्यूटर सेकंडों में काम पूरा कर लेता है बजाय मिनटों के।
क्या यह गुणवत्ता खो देता है? आश्चर्यजनक रूप से, नहीं। शोध पत्र यह सिद्ध करता है कि भले ही हम "स्केच" का उपयोग कर रहे हों, अंतिम बहाल की गई छवि उतनी ही स्पष्ट और साफ होती है जितनी कि धीमी, पूर्ण गणना करने से होती। वास्तव में, उनके परीक्षणों में, "स्केच" विधि अक्सर तेज थी और इसने बेहतर परिणाम दिए क्योंकि इसने शोर (noise) में फंसने से बचाव किया।

वास्तविक दुनिया पर प्रभाव

आपको इसकी परवाह क्यों होनी चाहिए?

तेजी से बहाली (Faster Restoration): यदि आपके पास सुरक्षा कैमरे का धुंधला वीडियो या कोई क्षतिग्रस्त पुरानी घरेलू फिल्म है, तो यह तरीका इसे आधे समय में ठीक कर सकता है।
बेहतर गुणवत्ता: यह "इल-पोज़्ड" (ill-posed) समस्याओं (जहाँ नुकसान इतना अधिक हो कि उत्तर स्पष्ट न हो) को बहुत अच्छी तरह से संभालता है, जिसमें टिखोनोव रेगुलराइजेशन (Tikhonov Regularization) नामक तकनीक का उपयोग किया जाता है (इसे एक "स्टेबलाइज़र" के रूप में सोचें जो कंप्यूटर को अजीब, बेतुके समाधानों का अनुमान लगाने से रोकता है)।
दक्षता (Efficiency): यह आपके लैपटॉप की बैटरी लाइफ बचाता है और वैज्ञानिकों को विशाल डेटासेट (जैसे सैटेलाइट इमेज या मेडिकल स्कैन) को प्रोसेस करने की अनुमति देता है जो पहले बहुत धीमे थे।

सारांश

इस शोध पत्र के लेखकों ने एक स्मार्ट शॉर्टकट का आविष्कार किया है। उन्होंने महसूस किया कि एक धुंधली, शोर वाली 3D छवि को ठीक करने के लिए, आपको हर एक गणना को पूरी तरह से करने की आवश्यकता नहीं है। आपको बस गणित के कुछ "रैंडम स्केच" की आवश्यकता है जो सबसे महत्वपूर्ण हिस्सों को पकड़ सकें।

उपमा:

पुराना तरीका: उद्धरण खोजने के लिए पुस्तकालय की हर किताब के हर पन्ने को पढ़ना।
नया तरीका: किताबों का सारांश देने के लिए रैंडम लोगों के एक समूह से पूछना, और फिर उनके सारांशों में उद्धरण ढूंढना।
परिणाम: आप उद्धरण को उतनी ही तेजी से प्राप्त करते हैं, लेकिन आपने इसे करने में 60% कम समय खर्च किया।

यह हमारी अनमोल यादों (फोटो और वीडियो) को बहाल करना तेज़, सस्ता और सभी के लिए सुलभ बनाता है।

यहाँ शोध पत्र "Randomized Tensor Krylov Subspace Methods via Sketched Einstein Product with Applications to Image and Video Restoration" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र इमेज और वीडियो रिस्टोरेशन (जैसे: डिब्लरिंग, डिनोइजिंग) में आने वाली बड़े पैमाने की मल्टीलीनियर प्रणालियों (multilinear systems) को हल करने की चुनौती को संबोधित करता है। इन समस्याओं को निम्नलिखित रैखिक टेंसर समीकरणों के रूप में मॉडल किया जाता है:
$\Phi(X) = C$
या लीस्ट-स्क्वायर्स वेरिएंट के रूप में:
$\min_X \| \Phi(X) - C \|_F$
जहाँ:

$X$ एक अज्ञात उच्च-आयामी टेंसर (जैसे: एक कलर इमेज या वीडियो सीक्वेंस) है।
$C$ प्रेक्षित डिग्रेडेड डेटा (observed degraded data) है।
$\Phi$ एक रैखिक टेंसर ऑपरेटर है (अक्सर ब्लरिंग या सबसैंपलिंग से संबंधित) जिसे आइंस्टीन प्रोडक्ट ( $*_N$ ) के माध्यम से परिभाषित किया गया है।

मुख्य चुनौती:
क्लासिकल टेंसर क्रिलोव सबस्पेस मेथड्स (जैसे: Tensor Global GMRES या Golub–Kahan) फ्रोबेनिअस इनर प्रोडक्ट (Frobenius inner product) और पूर्ण ऑर्थोगोनलाइजेशन (full orthogonalization) पर निर्भर करते हैं। उच्च-क्रम के टेंसरों (जैसे: RGB इमेजेस के लिए $N \times N \times 3$ या वीडियो के लिए उच्च आयाम) के लिए, ऑर्थोगोनलाइजेशन और इनर प्रोडक्ट गणना की कम्प्यूटेशनल लागत अत्यधिक (prohibitive) हो जाती है क्योंकि आयामीता ( $n = \prod I_k$ ) बहुत विशाल होती है। इसके अलावा, इन टेंसरों को वेक्टराइज (vectorize) करने से उनकी अंतर्निहित मल्टीडायमेंशनल संरचना नष्ट हो जाती है, जिससे मेमोरी बॉटलनैक (memory bottlenecks) उत्पन्न होते हैं।

2. कार्यप्रणाली (Methodology)

लेखक एक रैंडमाइज्ड टेंसर क्रिलोव सबस्पेस मेथड प्रस्तावित करते हैं जो स्केचिंग (रैंडमाइज्ड डायमेंशनलिटी रिडक्शन) को सीधे आइंस्टीन प्रोडक्ट फ्रेमवर्क में एकीकृत करता है।

A. स्केच्ड आइंस्टीन इनर प्रोडक्ट (Sketched Einstein Inner Product)

सटीक फ्रोबेनिअस इनर प्रोडक्ट $\langle X, Y \rangle_F$ की गणना करने के बजाय, यह विधि एक स्केच्ड इनर प्रोडक्ट $\langle X, Y \rangle_\Theta$ पेश करती है:
$\langle X, Y \rangle_\Theta = \langle S(X), S(Y) \rangle_F$
जहाँ $S(\cdot)$ एक रैंड टेंसर एम्बेडिंग ऑपरेटर है।

तंत्र (Mechanism): ऑपरेटर $S$ , टेंसर $X$ पर मोड-वाइज (mode-wise) रैंड प्रोजेक्शन मैट्रिसेस ( $\Theta_k$ ) लागू करता है, जिससे इसे कम-आयामी स्थान में संकुचित (compress) किया जाता है, जबकि उच्च संभावना के साथ सबस्पेस ज्योमेट्री को संरक्षित रखा जाता है।
सैद्धांतिक गारंटी: $\epsilon$ -सबस्पेस एम्बेडिंग की धारणा के तहत, स्केच्ड प्रोडक्ट वास्तविक इनर प्रोडक्ट का इस प्रकार अनुमान लगाता है:
$(1-\epsilon)\|X\|_F^2 \leq \|S(X)\|_F^2 \leq (1+\epsilon)\|X\|_F^2$
यह सुनिश्चित करता है कि सिंगुलर वैल्यूज और ऑर्थोगोनैलिटी एक सीमित त्रुटि के भीतर संरक्षित रहती हैं।

B. रैंडमाइज्ड टेंसर ग्लोबल आर्नोल्ड प्रोसेस (Randomized Tensor Global Arnoldi Process)

लेखक टेंसर क्रिलोव सबस्पेस के लिए एक ऑर्थोनॉर्मल बेसिस (orthonormal basis) बनाने के लिए एक स्केच्ड ग्लोबल आर्नोल्ड एल्गोरिदम विकसित करते हैं।

प्रक्रिया: प्रत्येक इटरेशन में, टेंसर ऑपरेटर $\Phi$ को लागू किया जाता है, और परिणाम को तुरंत स्केच ( $S(\Phi(V_j))$ ) किया जाता है।
ऑर्थोगोनलाइजेशन: ग्राम-श्मिट प्रक्रिया (Gram-Schmidt process) फ्रोबेनिअस प्रोडक्ट के बजाय स्केच्ड इनर प्रोडक्ट $\langle \cdot, \cdot \rangle_\Theta$ का उपयोग करती है।
परिणाम: यह एक रिड्यूस्ड हेसेनबर्ग मैट्रिक्स $\tilde{H}_m$ उत्पन्न करता है जो सबस्पेस पर $\Phi$ की क्रिया का अनुमान लगाता है, जिससे टेंसर-टेंसर उत्पादों और ऑर्थोगोनलाइजेशन की लागत काफी कम हो जाती है।

C. स्केच्ड टिखोनोव रेगुलराइजेशन (Sketched Tikhonov Regularization)

इल-पोज्ड (ill-posed) समस्याओं (शोर/नॉइज़) को संभालने के लिए, यह विधि रिड्यूस्ड सबस्पेस के भीतर टिखोनोव रेगुलराइजेशन को शामिल करती है:
$\min_y \| \beta e_{m+1} - \tilde{H}_m y \|_2^2 + \mu \|y\|_2^2$
रेगुलराइजेशन पैरामीटर $\mu$ को छोटे प्रोजेक्टेड प्रॉब्लम पर जनरलाइज्ड क्रॉस-वैलिडेशन (GCV) का उपयोग करके चुना जाता है, जिससे पूर्ण उच्च-आयामी सिस्टम को हल करने की आवश्यकता नहीं होती।

D. ब्लॉक एल्गोरिदम (Block Algorithms)

इस फ्रेमवर्क को ब्लॉक क्रिलोव सबस्पेस मेथड्स तक विस्तारित किया गया है, विशेष रूप से:

स्केच्ड आइंस्टीन ब्लॉक GMRES: रैखिक टेंसर समीकरणों को हल करने के लिए।
स्केच्ड आइंस्टीन ब्लॉक गोलुब-काहन (Golub–Kahan): लीस्ट-स्क्वायर्स समस्याओं (बिडायगोनलाइजेशन) को हल करने के लिए।
दोनों एल्गोरिदम सभी ऑर्थोगोनैलिटी चेक्स और नॉर्म गणनाओं के लिए स्केच्ड इनर प्रोडक्ट का उपयोग करते हैं।

3. मुख्य योगदान (Key Contributions)

नया फ्रेमवर्क: रैंडमाइज्ड टेंसर ग्लोबल GMRES (RTG-GMRES) और स्केच्ड ब्लॉक गोलुब-काहन विधियों का परिचय, जो टेंसर समीकरणों के लिए आइंस्टीन उत्पादों के साथ रैंडमाइज्ड स्केचिंग को संयोजित करने वाले पहले तरीके हैं।
जटिलता में कमी: यह विधि वेक्टराइजेशन के बिना टेंसरों को निम्न-आयामी स्थानों में प्रोजेक्ट करके ऑर्थोगोनलाइजेशन और इनर प्रोडक्ट गणनाओं की कम्प्यूटेशनल जटिलता को नाटकीय रूप से कम करती है।
सैद्धांतिक विश्लेषण: शोध पत्र निम्नलिखित के लिए कठोर प्रमाण प्रदान करता है:
- टेंसर सबस्पेस एम्बेडिंग: स्केच्ड इनर प्रोडक्ट के एप्रोक्सीमेशन एरर पर सीमाएं स्थापित करना।
- सिंगुलर वैल्यू बाउंड्स: यह सिद्ध करना कि स्केच्ड टेंसर अनफोल्डिंग्स की सिंगुलर वैल्यूज मूल के करीब रहती हैं।
- रेसिडुअल बाउंड्स: प्रोजेक्टेड टिखोनोव समाधान के लिए एरर बाउंड्स प्राप्त करना।
संरचना का संरक्षण: वेक्टराइजेशन-आधारित विधियों के विपरीत, यह दृष्टिकोण डेटा की मल्टीलीनर संरचना (जैसे: इमेजेस में स्थानिक और चैनल सहसंबंध) को बनाए रखता है, जिससे अधिक सटीक मॉडलिंग संभव होती है।

4. संख्यात्मक परिणाम (Numerical Results)

इन विधियों का परीक्षण गॉसियन ब्लर और एडिटिव गॉसियन नॉइज़ के तहत RGB इमेज डिब्लरिंग और वीडियो रिस्टोरेशन कार्यों पर किया गया।

परफॉरमेंस मेट्रिक्स: रिलेटिव एरर (RE) और पीक सिग्नल-टू-नॉइज़ रेशियो (PSNR)।
तुलना: प्रस्तावित स्केच्ड मेथड्स की तुलना क्लासिकल टेंसर GKB (बिना स्केचिंग के) और स्टैंडर्ड आइंस्टीन ब्लॉक GMRES से की गई।
निष्कर्ष:
- सटीकता (Accuracy): स्केच्ड मेथड्स ने नॉन-स्केच्ड मेथड्स की तुलना में समान या थोड़ा बेहतर PSNR और रिलेटिव एरर प्राप्त किया। उदाहरण के लिए, $10^{-3}$ के नॉइज़ लेवल पर, स्केच्ड ब्लॉक गोलुब-काहन ने 24.42 का PSNR प्राप्त किया, जबकि क्लासिकल GKB का PSNR 24.22 था।
- दक्षता (Efficiency): सबसे महत्वपूर्ण लाभ CPU समय में था। स्केच्ड मेथड्स ने कम्प्यूटेशन टाइम में 40–60% की कमी की।
  - उदाहरण: लो नॉइज़ लेवल पर, क्लासिकल GKB के 18.45s के मुकाबले स्केच्ड ब्लॉक गोलुब-काहन ने केवल 3.32s लिए।
- स्केलेबिलिटी (Scalability): स्पीड-अप विभिन्न नॉइज़ लेवल्स में सुसंगत था, जो इस विधि को बड़े पैमाने के, समय-संवेदनशील अनुप्रयोगों के लिए अत्यधिक उपयुक्त बनाता है।

5. महत्व (Significance)

यह शोध पत्र इमेजिंग अनुप्रयोगों के लिए बड़े पैमाने के टेंसर कंप्यूटेशन में एक बड़ी सफलता प्रस्तुत करता है।

व्यावहारिक प्रभाव: यह उच्च-रिज़ॉल्यूशन वाली कलर इमेजेस और वीडियो सीक्वेंस के रेस्टोरेशन को सक्षम बनाता है जो मेमोरी और समय की सीमाओं के कारण पहले कम्प्यूटेशनल रूप से कठिन थे।
एल्गोरिद्मिक नवाचार: रैंडमाइज्ड स्केचिंग को टेंसर बीजगणित (tensor algebra) के साथ सफलतापूर्वक एकीकृत करके, लेखक प्रदर्शित करते हैं कि एक मामूली सटीकता (जिसे $\epsilon$ द्वारा नियंत्रित किया जाता है) का त्याग करके भारी कम्प्यूटेशनल दक्षता प्राप्त की जा सकती है।
भविष्य के अनुप्रयोग: यह फ्रेमवर्क केवल इमेज रिस्टोरेशन तक सीमित नहीं है; यह उच्च-आयामी PDEs, हाइपरस्पेक्ट्रल इमेजिंग और अन्य मल्टीडायमेंशनल इनवर्स प्रॉब्लम्स को हल करने के लिए एक सामान्य उपकरण प्रदान करता है जहाँ टेंसर संरचना को बनाए रखना महत्वपूर्ण है।

निष्कर्षतः, प्रस्तावित स्केच्ड आइंस्टीन ब्लॉक क्रिलोव मेथड्स दक्षता और सटीकता के बीच एक उत्कृष्ट संतुलन प्रदान करते हैं, जो आधुनिक मल्टीडायमेंशनल डेटा रिस्टोरेशन चुनौतियों के लिए एक मजबूत और स्केलेबल समाधान पेश करते हैं।