2025-11-22T06:46:16.153487

A hierarchy of convex relaxations for the total variation distance

Lasserre
Given two measures $μ$, $ν$ on Rd that satisfy Carleman's condition, we provide a numerical scheme to approximate as closely as desired the total variation distance between $μ$ and $ν$. It consists of solving a sequence (hierarchy) of convex relaxations whose associated sequence of optimal values converges to the total variation distance, an additional illustration of the versatility of the Moment-SOS hierarchy. Indeed each relaxation in the hierarchy is a semidefinite program whose size increases with the number of involved moments. It has an optimal solution which is a couple of degree-2n pseudo-moments which converge, as n grows, to moments of the Hahn-Jordan decomposition of $μ$-$ν$.
academic

कुल भिन्नता दूरी के लिए उत्तल विश्लेषण का एक पदानुक्रम

मौलिक जानकारी

  • पेपर ID: 2401.01086
  • शीर्षक: कुल भिन्नता दूरी के लिए उत्तल विश्लेषण का एक पदानुक्रम
  • लेखक: Jean B. Lasserre
  • वर्गीकरण: math.OC (अनुकूलन और नियंत्रण)
  • प्रकाशन समय: जनवरी 2024 (arXiv v3: 16 अक्टूबर 2025)
  • पेपर लिंक: https://arxiv.org/abs/2401.01086

सारांश

यह पेपर Carleman शर्त को संतुष्ट करने वाले दो मापों μ और ν के बीच कुल भिन्नता दूरी को मनमाने ढंग से सटीकता के साथ अनुमानित करने के लिए एक संख्यात्मक योजना प्रस्तावित करता है। यह योजना (पदानुक्रमित) उत्तल विश्लेषण समस्याओं की एक श्रृंखला को हल करके कार्य करती है, जिसके इष्टतम मान अनुक्रम कुल भिन्नता दूरी में परिवर्तित होते हैं, जो Moment-SOS पदानुक्रम की बहुमुखी प्रकृति को प्रदर्शित करता है। पदानुक्रम में प्रत्येक विश्लेषण एक अर्धनिश्चित प्रोग्रामिंग समस्या है, जिसका आकार शामिल क्षणों की संख्या के साथ बढ़ता है, जिसमें डिग्री 2n के छद्म-क्षणों की एक इष्टतम जोड़ी होती है, जो n के बढ़ने पर μ-ν के Hahn-Jordan विघटन के क्षणों में परिवर्तित होती है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की महत्ता

कुल भिन्नता (Total Variation, TV) दूरी की संख्यात्मक गणना एक महत्वपूर्ण और चुनौतीपूर्ण समस्या है, जिसके निम्नलिखित क्षेत्रों में व्यापक अनुप्रयोग हैं:

  1. सांख्यिकीय परीक्षण: समरूपता परीक्षण और स्वतंत्रता परीक्षण के लिए
  2. वितरण-मजबूत अनुकूलन: अनिश्चितता समुच्चय को परिभाषित करने के लिए
  3. डेटा विज्ञान और मशीन लर्निंग: मापों के बीच दूरी माप के लिए

मौजूदा विधियों की सीमाएं

  1. अनुभवजन्य अनुमानक समस्या: यादृच्छिक नमूनों पर आधारित अनुभवजन्य अनुमानक अक्सर असंगत होते हैं, विशेषकर TV दूरी के लिए
  2. गणनात्मक चुनौतियां: TV दूरी "खराब" लागत फलन c(x,y) = 1_{x≠y} का उपयोग करके Wasserstein दूरी के बराबर है, जिसे प्रभावी ढंग से गणना करना कठिन है
  3. फलन स्थान बहुत बड़ा: मानक द्वैत सूत्र में परिबद्ध मापनीय फलनों का स्थान बहुत बड़ा है, जिसे प्रभावी ढंग से मूल्यांकन करना कठिन है
  4. समर्थन समुच्चय प्रतिबंध: मौजूदा विधियां आमतौर पर कॉम्पैक्ट समर्थन की मांग करती हैं

अनुसंधान प्रेरणा

मौजूदा योगदान मुख्य रूप से विशिष्ट वितरण वर्गों के लिए विश्लेषणात्मक ऊपरी और निचली सीमाएं प्रदान करने पर केंद्रित हैं, जिसमें सामान्य संख्यात्मक गणना विधि का अभाव है। यह पेपर अपेक्षाकृत कमजोर मान्यताओं के तहत एक व्यावहारिक गणना योजना प्रदान करने का लक्ष्य रखता है।

मुख्य योगदान

  1. संख्यात्मक गणना योजना: Moment-SOS पदानुक्रम पर आधारित अर्धनिश्चित प्रोग्रामिंग विश्लेषण अनुक्रम प्रस्तावित करता है, जो TV दूरी को मनमाने ढंग से सटीकता के साथ अनुमानित कर सकता है
  2. सैद्धांतिक गारंटी: विश्लेषण अनुक्रम की एकरसता और अभिसरण को सिद्ध करता है, इष्टतम मान नीचे से वास्तविक TV दूरी में परिवर्तित होते हैं
  3. गैर-कॉम्पैक्ट समर्थन प्रबंधन: विधि गैर-कॉम्पैक्ट समर्थन वाले मापों पर लागू होती है, केवल Carleman शर्त को संतुष्ट करने की आवश्यकता है
  4. विशेष मामलों का सटीक समाधान: वास्तविक अक्ष पर परमाणु मापों के लिए, जब विश्लेषण डिग्री n ≥ maxm₁,m₂ हो तो सटीक समाधान प्राप्त किया जा सकता है
  5. द्वैत सिद्धांत: द्वैत अर्धनिश्चित प्रोग्रामिंग प्रदान करता है, जो यह प्रकट करता है कि बहुपद तक सीमित करके और दंड पद जोड़कर शास्त्रीय TV दूरी द्वैत सूत्र को कैसे मजबूत किया जाए

विधि विवरण

कार्य परिभाषा

दो परिमित Borel माप μ, ν ∈ M(ℝᵈ)₊ दिए गए हैं, उनकी कुल भिन्नता दूरी की गणना करें: ∥μ−ν∥TV=sup⁡f{∫fdμ−∫fdν:∥f∥∞≤1}\|\mu - \nu\|_{TV} = \sup_f \left\{\int f d\mu - \int f d\nu : \|f\|_\infty \leq 1\right\}

मुख्य मान्यताएं

मान्यता 2.5:

  1. μ और ν के सभी क्षण परिमित हैं
  2. μ और ν शर्त को संतुष्ट करते हैं: ∫exp⁡(c∣xi∣)dμ<∞\int \exp(c|x_i|) d\mu < \infty, किसी c > 0 और सभी i = 1,...,d के लिए

विधि आर्किटेक्चर

1. अनंत-आयामी रैखिक प्रोग्रामिंग पुनर्निर्माण

TV दूरी को अनंत-आयामी LP में पुनर्निर्मित करें: τ=inf⁡ϕ+,ϕ−∈M(Rd)+{ϕ+(1)+ϕ−(1):ϕ+−ϕ−=μ−ν}\tau = \inf_{\phi_+,\phi_- \in M(\mathbb{R}^d)_+} \{\phi_+(1) + \phi_-(1) : \phi_+ - \phi_- = \mu - \nu\}

2. मुख्य बाधा वृद्धि

प्रभुत्व बाधा जोड़कर समतुल्य समस्या प्राप्त करें: ρ=inf⁡ϕ+,ϕ−∈M(Rd)+{ϕ+(1)+ϕ−(1):ϕ+−ϕ−=μ−ν;ϕ+≤μ;ϕ−≤ν}\rho = \inf_{\phi_+,\phi_- \in M(\mathbb{R}^d)_+} \{\phi_+(1) + \phi_-(1) : \phi_+ - \phi_- = \mu - \nu; \phi_+ \leq \mu; \phi_- \leq \nu\}

3. क्षण स्थिति रूपांतरण

लेम्मा 2.2 का उपयोग करके, प्रभुत्व बाधा क्षण मैट्रिक्स स्थिति के बराबर है: ϕ≤μ⇔Mn(ϕ)⪯Mn(μ),∀n∈N\phi \leq \mu \Leftrightarrow M_n(\phi) \preceq M_n(\mu), \forall n \in \mathbb{N}

4. अर्धनिश्चित प्रोग्रामिंग विश्लेषण

n-वां स्तर विश्लेषण समस्या: ρn=min⁡ϕ,ψ{ϕ(1)+ψ(1):ϕα−ψα=μα−να,∀α∈N2nd;\rho_n = \min_{\phi,\psi} \{\phi(1) + \psi(1) : \phi_\alpha - \psi_\alpha = \mu_\alpha - \nu_\alpha, \forall \alpha \in \mathbb{N}^d_{2n};0⪯Mn(ϕ)⪯Mn(μ);0⪯Mn(ψ)⪯Mn(ν)}0 \preceq M_n(\phi) \preceq M_n(\mu); 0 \preceq M_n(\psi) \preceq M_n(\nu)\}

तकनीकी नवाचार बिंदु

  1. प्रभुत्व बाधा की मुख्य भूमिका: हालांकि अनंत-आयामी सूत्र में अनावश्यक है, विश्लेषण योजना में यह कॉम्पैक्टिफिकेशन उपकरण के रूप में अत्यंत उपयोगी है
  2. Carleman शर्त का चतुर उपयोग: माप की विशिष्टता सुनिश्चित करता है, जिससे क्षण बाधा प्रभुत्व बाधा के बराबर हो जाती है
  3. Hahn-Jordan विघटन का प्राकृतिक उदय: इष्टतम समाधान μ-ν के Hahn-Jordan विघटन में परिवर्तित होता है
  4. द्वैत समस्या का बहुपद प्रतिबंध: बहुपद स्थान तक सीमित करके और दंड पद जोड़कर ‖f‖∞ ≤ 1 बाधा के उल्लंघन को संभालता है

प्रायोगिक सेटअप

कार्यान्वयन उपकरण

  • सॉफ्टवेयर: बहुपद अनुकूलन के लिए GloptiPoly 3
  • समाधानकर्ता: अर्धनिश्चित प्रोग्रामिंग समाधानकर्ता SeDuMi 1.03
  • मंच: HP Elitebook Ubuntu 24 नोटबुक

परीक्षण मामले

1. असतत माप

  • परस्पर असंबद्ध समर्थन: X = {-1.0, 0.0, 1.0, 2.0}, Y = {-0.7, 0.3, 1.3, 2.3}
  • एक सामान्य बिंदु: X ∩ Y = {-1.0}
  • निकटवर्ती परमाणु: संख्यात्मक स्थिरता का परीक्षण

2. गाऊसी माप

  • विभिन्न माध्य और विचरण वाले गाऊसी वितरण N(m₁,σ₁) और N(m₂,σ₂)
  • क्षण संख्या 2n = 4 से 2n = 8 तक

मूल्यांकन संकेतक

  • विश्लेषण इष्टतम मान ρₙ और वास्तविक TV दूरी की निकटता
  • अभिसरण गति और संख्यात्मक स्थिरता
  • गणना समय (सभी परिणाम 0.35 सेकंड में पूर्ण)

प्रायोगिक परिणाम

मुख्य परिणाम

1. सैद्धांतिक सत्यापन (प्रमेय 3.4)

वास्तविक अक्ष पर परमाणु मापों के लिए, जब n ≥ maxm₁,m₂ हो तो सटीक समाधान प्राप्त करें:

  • उदाहरण 1: μ = δ₀, ν = δₑ, ρ₁ = 2 (सटीक)
  • उदाहरण 2: चार परमाणु, एक सामान्य बिंदु, ρ₄ = 1.499 ≈ 1.5
  • उदाहरण 3: परस्पर असंबद्ध परमाणु, ρ₄ = 1.9999 ≈ 2

2. गाऊसी माप परिणाम

(m₁,σ₁)(m₂,σ₂)ρ₁ρ₂ρ₃ρ₄
(0,0.1)(1,0.1)1.92311.99361.99911.9997
(0,0.2)(1,0.2)1.72411.90491.93761.939
(0,0.5)(1,0.5)1.00001.00001.16531.1897

3. महत्वपूर्ण निष्कर्ष

  • ρ₁ साहित्य 1 में विश्लेषणात्मक निचली सीमा के साथ पूरी तरह मेल खाता है
  • n=2 से शुरू करके महत्वपूर्ण सुधार, n=3,4 पर बेहतर प्रभाव
  • छोटे विचरण पर परस्पर विलक्षण मापों के व्यवहार के निकट (TV दूरी 2 के निकट)

अभिसरण विश्लेषण

प्रमेय 3.1 गारंटी देता है:

  1. प्रत्येक विश्लेषण का एक इष्टतम समाधान है
  2. ρₙ ↑ ‖μ-ν‖_ एकरस अभिसरण
  3. इष्टतम समाधान Hahn-Jordan विघटन के क्षणों में परिवर्तित होते हैं

संबंधित कार्य

मुख्य अनुसंधान दिशाएं

  1. अनुभवजन्य अनुमानक: नमूना-आधारित दूरी अनुमान, लेकिन TV दूरी के अनुमानक अक्सर असंगत होते हैं
  2. विश्लेषणात्मक सीमाएं: विशिष्ट वितरण वर्गों (जैसे उच्च-आयामी गाऊसी, गाऊसी मिश्रण) के लिए ऊपरी और निचली सीमाएं
  3. असमानता विधियां: Pinsker असमानता, Hellinger दूरी सीमाएं
  4. इष्टतम परिवहन: Kantorovich मेट्रिक के लिए विशेष एल्गोरिदम (जैसे Sinkhorn एल्गोरिदम)

इस पेपर के लाभ

  1. सामान्यता: Carleman शर्त को संतुष्ट करने वाले सामान्य मापों पर लागू
  2. गैर-कॉम्पैक्ट समर्थन: कॉम्पैक्ट समर्थन की मांग नहीं करता
  3. गारंटीकृत अभिसरण: सैद्धांतिक रूप से गारंटीकृत एकरस अभिसरण
  4. व्यावहारिकता: बंद-रूप क्षण और अनुभवजन्य क्षण दोनों को संभाल सकता है

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. TV दूरी गणना के लिए एक सामान्य संख्यात्मक योजना प्रदान करता है
  2. अपेक्षाकृत कमजोर मान्यताओं के तहत मनमानी सटीकता अनुमान प्राप्त करता है
  3. प्रत्येक विश्लेषण गारंटीकृत निचली सीमा प्रदान करता है
  4. असतत मापों के लिए सटीक समाधान प्राप्त कर सकता है

सीमाएं

  1. आयाम संवेदनशीलता: विधि आयाम के प्रति संवेदनशील है, वर्तमान में छोटे आयाम समस्याओं तक सीमित है
  2. अर्धनिश्चित प्रोग्रामिंग समाधानकर्ता सीमा: उच्च-डिग्री विश्लेषण समस्याओं को हल करने की अपेक्षा नहीं की जा सकती
  3. संख्यात्मक सटीकता: जब परमाणु बहुत निकट हों तो संख्यात्मक समस्याओं का सामना कर सकता है
  4. नमूना आकार आवश्यकता: अनुभवजन्य क्षणों का उपयोग करते समय पर्याप्त बड़े नमूने की आवश्यकता होती है

भविष्य की दिशाएं

  1. गणनात्मक रूप से सस्ती वैकल्पिक निचली सीमाएं प्रदान करना
  2. उच्च-आयामी समस्याओं के प्रबंधन तक विस्तार
  3. संख्यात्मक स्थिरता में सुधार
  4. अन्य दूरी मापों के साथ तुलनात्मक अनुसंधान

गहन मूल्यांकन

लाभ

  1. सैद्धांतिक कठोरता: पूर्ण अभिसरण प्रमाण और द्वैत सिद्धांत
  2. विधि नवीनता: पहली बार Moment-SOS पदानुक्रम को TV दूरी गणना पर लागू करता है
  3. व्यावहारिक मूल्य: बंद-रूप और नमूना दोनों डेटा रूपों को संभाल सकता है
  4. सटीकता गारंटी: विशिष्ट मामलों (परमाणु माप) के लिए सटीक समाधान प्राप्त कर सकता है

कमियां

  1. गणनात्मक जटिलता: अर्धनिश्चित प्रोग्रामिंग की गणनात्मक जटिलता अनुप्रयोग पैमाने को सीमित करती है
  2. सीमित प्रयोग: मुख्य रूप से कम आयाम और सरल वितरणों पर परीक्षण
  3. मौजूदा विधियों के साथ तुलना अपर्याप्त: अन्य TV दूरी गणना विधियों के साथ व्यवस्थित तुलना का अभाव

प्रभाव

  1. सैद्धांतिक योगदान: TV दूरी गणना के लिए नया सैद्धांतिक ढांचा प्रदान करता है
  2. पद्धति मूल्य: संभाव्य मेट्रिक्स गणना में Moment-SOS पदानुक्रम की क्षमता प्रदर्शित करता है
  3. व्यावहारिक अनुप्रयोग: वितरण-मजबूत अनुकूलन आदि क्षेत्रों के लिए नए उपकरण प्रदान करता है

लागू परिदृश्य

  1. सटीक गणना आवश्यकता: सैद्धांतिक गारंटीकृत TV दूरी निचली सीमा की आवश्यकता
  2. कम आयाम समस्याएं: अपेक्षाकृत कम आयाम वाली व्यावहारिक अनुप्रयोग
  3. विशेष वितरण: गाऊसी, घातांकीय वितरण और उनके मिश्रण
  4. असतत वितरण: परिमित समर्थन वाले परमाणु माप

संदर्भ

पेपर 28 संबंधित संदर्भों का हवाला देता है, जो इष्टतम परिवहन, क्षण समस्याएं, अर्धनिश्चित प्रोग्रामिंग और संभाव्य मेट्रिक्स आदि कई क्षेत्रों के महत्वपूर्ण कार्यों को कवर करता है, विशेषकर लेखक के Moment-SOS पदानुक्रम पर अपने स्वयं के श्रृंखला कार्य 21,24,26 इस पेपर का सैद्धांतिक आधार बनाते हैं।