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

সম্পূর্ণ ভেরিয়েশন দূরত্বের জন্য উত্তল শিথিলকরণের একটি শ্রেণিবিন্যাস

মৌলিক তথ্য

  • পেপার আইডি: 2401.01086
  • শিরোনাম: সম্পূর্ণ ভেরিয়েশন দূরত্বের জন্য উত্তল শিথিলকরণের একটি শ্রেণিবিন্যাস
  • লেখক: Jean B. Lasserre
  • শ্রেণীবিভাগ: math.OC (অপ্টিমাইজেশন এবং নিয়ন্ত্রণ)
  • প্রকাশনার সময়: ২০২৪ সালের জানুয়ারি (arXiv v3: ২০২৫ সালের অক্টোবর ১৬)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2401.01086

সারসংক্ষেপ

এই পেপারটি কার্লেম্যান শর্ত সন্তুষ্টকারী দুটি পরিমাপ μ এবং ν এর মধ্যে সম্পূর্ণ ভেরিয়েশন দূরত্বকে নির্বিচারে নির্ভুলভাবে অনুমান করার জন্য একটি সংখ্যাসূচক স্কিম প্রস্তাব করে। এই স্কিমটি শ্রেণিবদ্ধ উত্তল শিথিলকরণ সমস্যাগুলির একটি সিরিজ সমাধানের মাধ্যমে কাজ করে, যার সর্বোত্তম মানের ক্রম সম্পূর্ণ ভেরিয়েশন দূরত্বে রূপান্তরিত হয়, যা Moment-SOS শ্রেণিবিন্যাসের বহুমুখিতা প্রদর্শন করে। শ্রেণিবিন্যাসের প্রতিটি শিথিলকরণ একটি আধা-নির্দিষ্ট প্রোগ্রামিং সমস্যা, যার আকার জড়িত মুহূর্তের পরিমাণের সাথে বৃদ্ধি পায়, যার সর্বোত্তম সমাধান হল ডিগ্রি ২n এর একটি সিউডো-মোমেন্ট জোড়া, যা 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. অ-কমপ্যাক্ট সমর্থন প্রক্রিয়াকরণ: পদ্ধতি অ-কমপ্যাক্ট সমর্থনের পরিমাপের জন্য প্রযোজ্য, শুধুমাত্র কার্লেম্যান শর্ত সন্তুষ্ট করা প্রয়োজন
  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. কার্লেম্যান শর্তের চতুর ব্যবহার: পরিমাপের অনন্যতা নিশ্চিত করে, মুহূর্ত সীমাবদ্ধতাকে আধিপত্য সীমাবদ্ধতার সমতুল্য করে তোলে
  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. সর্বজনীনতা: কার্লেম্যান শর্ত সন্তুষ্টকারী সাধারণ পরিমাপের জন্য প্রযোজ্য
  2. অ-কমপ্যাক্ট সমর্থন: কমপ্যাক্ট সমর্থন সেট প্রয়োজন নেই
  3. গ্যারান্টিযুক্ত রূপান্তর: তাত্ত্বিক গ্যারান্টিযুক্ত একঘেয়ে রূপান্তর
  4. ব্যবহারিকতা: বন্ধ-ফর্ম মুহূর্ত এবং অভিজ্ঞতামূলক মুহূর্ত উভয় ক্ষেত্রে পরিচালনা করতে পারে

উপসংহার এবং আলোচনা

প্রধান সিদ্ধান্ত

  1. TV দূরত্ব গণনার জন্য একটি সর্বজনীন সংখ্যাসূচক স্কিম প্রদান করা হয়েছে
  2. তুলনামূলকভাবে দুর্বল অনুমানের অধীনে নির্বিচার নির্ভুলতা অনুমান অর্জন করা হয়েছে
  3. প্রতিটি শিথিলকরণ গ্যারান্টিযুক্ত নিম্ন সীমা প্রদান করে
  4. বিচ্ছিন্ন পরিমাপের জন্য সঠিক সমাধান পাওয়া যায়

সীমাবদ্ধতা

  1. মাত্রা সংবেদনশীলতা: পদ্ধতি মাত্রার প্রতি সংবেদনশীল, বর্তমানে ছোট মাত্রার সমস্যায় সীমাবদ্ধ
  2. আধা-নির্দিষ্ট প্রোগ্রামিং সমাধানকারী সীমাবদ্ধতা: উচ্চ ডিগ্রি শিথিলকরণ সমস্যা সমাধানের প্রত্যাশা করা যায় না
  3. সংখ্যাগত নির্ভুলতা: যখন পরমাণু খুব কাছাকাছি থাকে তখন সংখ্যাগত সমস্যার সম্মুখীন হতে পারে
  4. নমুনা আকার প্রয়োজনীয়তা: অভিজ্ঞতামূলক মুহূর্ত ব্যবহার করার সময় যথেষ্ট বড় নমুনা প্রয়োজন

ভবিষ্যত দিকনির্দেশনা

  1. গণনা সস্তা বিকল্প নিম্ন সীমানা প্রদান করা
  2. উচ্চ-মাত্রিক সমস্যা প্রক্রিয়াকরণে সম্প্রসারণ
  3. সংখ্যাগত স্থিতিশীলতা উন্নত করা
  4. অন্যান্য দূরত্ব মেট্রিকের সাথে তুলনামূলক গবেষণা

গভীর মূল্যায়ন

শক্তি

  1. তাত্ত্বিক কঠোরতা: সম্পূর্ণ রূপান্তর প্রমাণ এবং দ্বৈত তত্ত্ব
  2. পদ্ধতি উদ্ভাবন: TV দূরত্ব গণনায় Moment-SOS শ্রেণিবিন্যাসের প্রথম প্রয়োগ
  3. ব্যবহারিক মূল্য: বন্ধ-ফর্ম এবং নমুনা উভয় ডেটা ফর্ম পরিচালনা করতে পারে
  4. নির্ভুলতা গ্যারান্টি: নির্দিষ্ট ক্ষেত্রে (পরমাণু পরিমাপ) সঠিক সমাধান পাওয়া যায়

অপূর্ণতা

  1. গণনা জটিলতা: আধা-নির্দিষ্ট প্রোগ্রামিং এর গণনা জটিলতা প্রয়োগের স্কেল সীমাবদ্ধ করে
  2. সীমিত পরীক্ষা: প্রধানত কম মাত্রা এবং সরল বিতরণে পরীক্ষা করা হয়েছে
  3. বিদ্যমান পদ্ধতির সাথে তুলনা অপর্যাপ্ত: TV দূরত্ব গণনার অন্যান্য পদ্ধতির সাথে সিস্টেমেটিক তুলনার অভাব

প্রভাব

  1. তাত্ত্বিক অবদান: TV দূরত্ব গণনার জন্য নতুন তাত্ত্বিক কাঠামো প্রদান করা হয়েছে
  2. পদ্ধতিগত মূল্য: সম্ভাব্য মেট্রিক গণনায় Moment-SOS শ্রেণিবিন্যাসের সম্ভাবনা প্রদর্শন করা হয়েছে
  3. ব্যবহারিক প্রয়োগ: বিতরণ-শক্তিশালী অপ্টিমাইজেশন ইত্যাদি ক্ষেত্রে নতুন সরঞ্জাম প্রদান করা হয়েছে

প্রযোজ্য পরিস্থিতি

  1. সঠিক গণনা প্রয়োজনীয়তা: তাত্ত্বিক গ্যারান্টিযুক্ত TV দূরত্ব নিম্ন সীমা প্রয়োজন
  2. ছোট মাত্রা সমস্যা: মাত্রা অপেক্ষাকৃত কম ব্যবহারিক প্রয়োগ
  3. বিশেষ বিতরণ: গাউসিয়ান, সূচকীয় বিতরণ এবং তাদের মিশ্রণ
  4. বিচ্ছিন্ন বিতরণ: সীমাবদ্ধ সমর্থনের পরমাণু পরিমাপ

সংদর্ভ

পেপারটি 28টি সম্পর্কিত সংদর্ভ উদ্ধৃত করে, যা সর্বোত্তম পরিবহন, মুহূর্ত সমস্যা, আধা-নির্দিষ্ট প্রোগ্রামিং এবং সম্ভাব্য মেট্রিক্স সহ একাধিক ক্ষেত্রের গুরুত্বপূর্ণ কাজ অন্তর্ভুক্ত করে, বিশেষত লেখকের Moment-SOS শ্রেণিবিন্যাসে নিজস্ব সিরিজ কাজ 21,24,26 এই পেপারের তাত্ত্বিক ভিত্তি গঠন করে।