2025-11-24T15:25:16.688425

A stronger Sylvester's criterion for positive semidefinite matrices

Zhang, Ding
Sylvester's criterion characterizes positive definite (PD) and positive semidefinite (PSD) matrices without the need of eigendecomposition. It states that a symmetric matrix is PD if and only if all of its leading principal minors are positive, and a symmetric matrix is PSD if and only if all of its principal minors are nonnegative. For an $m\times m$ symmetric matrix, Sylvester's criterion requires computing $m$ and $2^m-1$ determinants to verify it is PD and PSD, respectively. Therefore, it is less useful for PSD matrices due to the exponential growth in the number of principal submatrices as the matrix dimension increases. We provide a stronger Sylvester's criterion for PSD matrices which only requires to verify the nonnegativity of $m(m+1)/2$ determinants. Based on the new criterion, we provide a method to derive elementwise criteria for PD and PSD matrices. We illustrate the applications of our results in PD or PSD matrix completion and highlight their statistics applications via nonlinear semidefinite program.
academic

ধনাত্মক অর্ধ-নির্দিষ্ট ম্যাট্রিক্সের জন্য একটি শক্তিশালী সিলভেস্টার মানদণ্ড

মৌলিক তথ্য

  • পেপার আইডি: 2501.00894
  • শিরোনাম: ধনাত্মক অর্ধ-নির্দিষ্ট ম্যাট্রিক্সের জন্য একটি শক্তিশালী সিলভেস্টার মানদণ্ড
  • লেখক: মিংগ্রুই ঝাং (ইউসি বার্কলে), পেং ডিং (ইউসি বার্কলে)
  • শ্রেণীবিভাগ: math.RA (রিং এবং বীজগণিত), math.ST (পরিসংখ্যান তত্ত্ব), stat.TH (পরিসংখ্যান তত্ত্ব)
  • প্রকাশনার সময়: ২০২৫ সালের ১ জানুয়ারি (arXiv প্রাক-প্রিন্ট)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2501.00894

সারসংক্ষেপ

সিলভেস্টার মানদণ্ড হল ধনাত্মক নির্দিষ্ট (PD) এবং অর্ধ-নির্দিষ্ট (PSD) ম্যাট্রিক্স নির্ধারণের একটি ক্লাসিক পদ্ধতি, যার জন্য আইগেনভ্যালু বিয়োজনের প্রয়োজন নেই। ক্লাসিক মানদণ্ড অনুযায়ী: একটি প্রতিসম ম্যাট্রিক্স ধনাত্মক নির্দিষ্ট যদি এবং শুধুমাত্র যদি সমস্ত প্রধান প্রধান মাইনর ধনাত্মক হয়; একটি প্রতিসম ম্যাট্রিক্স অর্ধ-নির্দিষ্ট যদি এবং শুধুমাত্র যদি সমস্ত মাইনর অ-ঋণাত্মক হয়। একটি m×mm\times m প্রতিসম ম্যাট্রিক্সের জন্য, সিলভেস্টার মানদণ্ড ধনাত্মক নির্দিষ্টতা এবং অর্ধ-নির্দিষ্টতা যাচাই করার জন্য mm এবং 2m−12^m-1 টি নির্ধারক গণনা করতে হয়। প্রধান সাব-ম্যাট্রিক্সের সংখ্যার সূচকীয় বৃদ্ধির কারণে, এই মানদণ্ডটি অর্ধ-নির্দিষ্ট ম্যাট্রিক্সের জন্য সীমিত ব্যবহারিক মূল্য রাখে। এই পেপারটি অর্ধ-নির্দিষ্ট ম্যাট্রিক্সের জন্য একটি শক্তিশালী সিলভেস্টার মানদণ্ড প্রস্তাব করে, যা শুধুমাত্র m(m+1)/2m(m+1)/2 টি নির্ধারকের অ-ঋণাত্মকতা যাচাই করতে প্রয়োজন। নতুন মানদণ্ডের উপর ভিত্তি করে, লেখকরা ধনাত্মক নির্দিষ্ট এবং অর্ধ-নির্দিষ্ট ম্যাট্রিক্সের উপাদান-অনুযায়ী মানদণ্ড প্রাপ্ত করার পদ্ধতি প্রদান করেন এবং ম্যাট্রিক্স সমাপ্তি এবং অ-রৈখিক অর্ধ-নির্দিষ্ট প্রোগ্রামিংয়ে প্রয়োগ প্রদর্শন করেন।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যা সংজ্ঞা

এই গবেষণাটি অর্ধ-নির্দিষ্ট ম্যাট্রিক্স নির্ধারণে ক্লাসিক সিলভেস্টার মানদণ্ডের অত্যধিক গণনামূলক জটিলতার সমস্যা সমাধানের লক্ষ্য রাখে। বিশেষভাবে:

  1. গণনামূলক জটিলতার সমস্যা: একটি m×mm\times m ম্যাট্রিক্সের জন্য, অর্ধ-নির্দিষ্টতা যাচাই করার জন্য 2m−12^m-1 টি প্রধান মাইনর পরীক্ষা করতে হয়, যা ম্যাট্রিক্সের মাত্রা বৃদ্ধির সাথে সূচকীয়ভাবে বৃদ্ধি পায়
  2. ব্যবহারিক সীমাবদ্ধতা: সূচকীয় স্তরের গণনা পরিমাণ উচ্চ-মাত্রার ম্যাট্রিক্সের অর্ধ-নির্দিষ্টতা নির্ধারণে ক্লাসিক মানদণ্ডকে অব্যবহারিক করে তোলে
  3. তাত্ত্বিক সম্পূর্ণতার প্রয়োজন: বিদ্যমান সাহিত্যে সিলভেস্টার মানদণ্ডের অপব্যবহার এবং অনুপযুক্ত সম্প্রসারণ রয়েছে

গবেষণার গুরুত্ব

অর্ধ-নির্দিষ্ট ম্যাট্রিক্স গণিত, পরিসংখ্যান, অপ্টিমাইজেশন এবং অন্যান্য ক্ষেত্রে গুরুত্বপূর্ণ অবস্থান রাখে:

  • সহ-পরিবর্তন ম্যাট্রিক্স অবশ্যই অর্ধ-নির্দিষ্ট হতে হবে
  • অর্ধ-নির্দিষ্ট প্রোগ্রামিং সমস্যার মূল সীমাবদ্ধতা
  • ম্যাট্রিক্স সমাপ্তি সমস্যার মূল বৈশিষ্ট্য
  • পরিসংখ্যানগত অনুমানে মৌলিক সরঞ্জাম

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

  1. ক্লাসিক সিলভেস্টার মানদণ্ড: অর্ধ-নির্দিষ্ট ম্যাট্রিক্সের জন্য O(2m)O(2^m) নির্ধারক গণনা প্রয়োজন
  2. আইগেনভ্যালু বিয়োজন পদ্ধতি: উচ্চ গণনামূলক জটিলতা এবং নির্দিষ্ট প্রয়োগে অপর্যাপ্ত স্বজ্ঞা
  3. গ্রাফ তত্ত্ব পদ্ধতি: শুধুমাত্র নির্দিষ্ট কাঠামোর জন্য প্রযোজ্য (যেমন জ্যা গ্রাফ), সর্বজনীনতা সীমিত

মূল অবদান

  1. শক্তিশালী অর্ধ-নির্দিষ্ট সিলভেস্টার মানদণ্ড প্রস্তাব: প্রয়োজনীয় নির্ধারক গণনা 2m−12^m-1 থেকে m(m+1)/2m(m+1)/2 এ হ্রাস করা
  2. অভ্যন্তরীণ সম্পৃক্ত সাব-ম্যাট্রিক্স ধারণা প্রবর্তন: নতুন মানদণ্ডের জন্য তাত্ত্বিক ভিত্তি প্রদান
  3. উপাদান-অনুযায়ী নির্ধারণ পদ্ধতি স্থাপন: ম্যাট্রিক্স উপাদান পরিসীমা নির্ধারণের পদ্ধতিগত পদ্ধতি প্রদান
  4. ব্যবহারিক প্রয়োগ প্রদর্শন: ম্যাট্রিক্স সমাপ্তি এবং অ-রৈখিক অর্ধ-নির্দিষ্ট প্রোগ্রামিংয়ে পদ্ধতির কার্যকারিতা যাচাই
  5. সম্পূর্ণ তাত্ত্বিক প্রমাণ প্রদান: কঠোর গাণিতিক প্রমাণ এবং লেম্মা সমর্থন অন্তর্ভুক্ত

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

মূল ধারণা সংজ্ঞা

ক্রমাগত প্রধান সাব-ম্যাট্রিক্স

সংজ্ঞা ২: একটি m×mm\times m ম্যাট্রিক্স XX এবং পূর্ণসংখ্যা a≤ba \leq b এর জন্য, Xa:b,a:bX_{a:b,a:b} কে XX এর ক্রমাগত প্রধান সাব-ম্যাট্রিক্স বলা হয়।

অভ্যন্তরীণ সম্পৃক্ত সাব-ম্যাট্রিক্স

সংজ্ঞা ৩: একটি প্রতিসম m×mm\times m ম্যাট্রিক্স XX এর জন্য, XI,IX_{I,I} কে অভ্যন্তরীণ সম্পৃক্ত সাব-ম্যাট্রিক্স হিসাবে সংজ্ঞায়িত করুন, যেখানে I={1,m}∪JI = \{1,m\} \cup J, সূচক সেট JJ সন্তুষ্ট করে:

  • যখন m≤2m \leq 2 হয়, J=∅J = \emptyset
  • যখন m≥3m \geq 3 হয়, {X2:(m−1),j:j∈J}\{X_{2:(m-1),j} : j \in J\} হল X2:(m−1),2:(m−1)X_{2:(m-1),2:(m-1)} এর কলাম ভেক্টরের সর্বাধিক রৈখিকভাবে স্বাধীন সেট

প্রধান উপপাদ্য

উপপাদ্য ২ (নতুন সিলভেস্টার মানদণ্ড): একটি প্রতিসম m×mm\times m ম্যাট্রিক্স XX এর জন্য, নিম্নলিখিত শর্তগুলি সমতুল্য:

  1. XX একটি অর্ধ-নির্দিষ্ট ম্যাট্রিক্স
  2. XX এর যেকোনো ক্রমাগত প্রধান সাব-ম্যাট্রিক্সের জন্য, এর কোনো অভ্যন্তরীণ সম্পৃক্ত সাব-ম্যাট্রিক্সের অ-ঋণাত্মক নির্ধারক রয়েছে
  3. XX এর যেকোনো ক্রমাগত প্রধান সাব-ম্যাট্রিক্সের জন্য, এর সমস্ত অভ্যন্তরীণ সম্পৃক্ত সাব-ম্যাট্রিক্সের অ-ঋণাত্মক নির্ধারক রয়েছে

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

  1. জটিলতা অপ্টিমাইজেশন: O(2m)O(2^m) থেকে O(m2)O(m^2) এ হ্রাস
  2. সমতুল্যতা প্রমাণ: শর্ত (ii) এবং (iii) এর সমতুল্যতা মূল উদ্ভাবন
  3. গঠনমূলক পদ্ধতি: ম্যাট্রিক্স উপাদান পরিসীমা নির্ধারণের জন্য সুনির্দিষ্ট অ্যালগরিদম প্রদান

উপাদান-অনুযায়ী নির্ধারণ পদ্ধতি

আংশিক ক্রম সম্পর্ক

উপরের ত্রিভুজ উপাদানের আংশিক ক্রম সম্পর্ক ⪯\preceq সংজ্ঞায়িত করুন: Xi′,j′⪯Xi,jX_{i',j'} \preceq X_{i,j} যদি এবং শুধুমাত্র যদি i≤i′≤j′≤ji \leq i' \leq j' \leq j হয়।

নির্ধারণ প্রক্রিয়া

  1. কর্ণ উপাদান: অবশ্যই অ-ঋণাত্মক হতে হবে
  2. k-কর্ণ উপাদান: আংশিক ক্রম সম্পর্ক অনুযায়ী ক্রমান্বয়ে পরিসীমা নির্ধারণ করুন
  3. পুনরাবৃত্তিমূলক নির্ধারণ: ক্রমাগত প্রধান সাব-ম্যাট্রিক্সের অভ্যন্তরীণ সম্পৃক্ত সাব-ম্যাট্রিক্স নির্ধারক সীমাবদ্ধতা ব্যবহার করুন

পরীক্ষামূলক সেটআপ

তাত্ত্বিক যাচাইকরণ

পেপারটি প্রধানত গাণিতিক প্রমাণের মাধ্যমে তাত্ত্বিক সঠিকতা যাচাই করে, যার মধ্যে রয়েছে:

  • তিনটি মূল লেম্মার প্রমাণ
  • প্রধান উপপাদ্যের আবেগপ্রবণ প্রমাণ
  • প্রস্তাব ১ এবং ২ এর গঠনমূলক প্রমাণ

প্রয়োগ উদাহরণ

ম্যাট্রিক্স সমাপ্তি সমস্যা

উদাহরণ ৩: আংশিকভাবে পর্যবেক্ষণ করা একটি 5×55\times 5 প্রতিসম ম্যাট্রিক্স বিবেচনা করুন, যার মধ্যে ৩টি অনুপস্থিত উপাদান x1,x2,x3x_1, x_2, x_3 রয়েছে। নতুন মানদণ্ড ব্যবহার করে অনুপস্থিত উপাদানের সম্ভাব্য অঞ্চল নির্ধারণ করুন, ম্যাট্রিক্সের একটি ধনাত্মক নির্দিষ্ট সমাপ্তি বিদ্যমান কিনা তা যাচাই করুন।

অ-রৈখিক অর্ধ-নির্দিষ্ট প্রোগ্রামিং

উদাহরণ ৪: অপ্টিমাইজেশন সমস্যা max⁡X112+X222+X332+X442−X12X23X34−X13X24+X14\max X_{11}^2 + X_{22}^2 + X_{33}^2 + X_{44}^2 - X_{12}X_{23}X_{34} - X_{13}X_{24} + X_{14} সীমাবদ্ধতা: XX অর্ধ-নির্দিষ্ট, 0≤Xii≤10 \leq X_{ii} \leq 1

পরীক্ষামূলক ফলাফল

জটিলতা তুলনা

  • ক্লাসিক পদ্ধতি: 2m−12^m-1 নির্ধারক গণনা
  • নতুন পদ্ধতি: m(m+1)/2m(m+1)/2 নির্ধারক গণনা
  • উন্নতির মাত্রা: সূচকীয় জটিলতা থেকে বহুপদী জটিলতায় হ্রাস

প্রয়োগের কার্যকারিতা

  1. ম্যাট্রিক্স সমাপ্তি: অ-জ্যা গ্রাফ ক্ষেত্রে সমাপ্তির সম্ভাব্যতা সফলভাবে নির্ধারণ করা
  2. অর্ধ-নির্দিষ্ট প্রোগ্রামিং: উপাদান-অনুযায়ী সীমাবদ্ধতার পুনঃপ্যারামিটারাইজেশন পদ্ধতি প্রদান করা
  3. গণনামূলক দক্ষতা: প্রয়োজনীয় নির্ধারক গণনা উল্লেখযোগ্যভাবে হ্রাস করা

সম্পর্কিত কাজ

ক্লাসিক তত্ত্ব

  • সিলভেস্টার মানদণ্ড: জেমস জোসেফ সিলভেস্টার (১৮১৪-১৮৯৭) দ্বারা প্রস্তাবিত ধনাত্মক নির্দিষ্ট ম্যাট্রিক্স নির্ধারণ মানদণ্ড
  • অর্ধ-নির্দিষ্ট সম্প্রসারণ: প্রুসিং (১৯৮৬) দ্বারা প্রথম অর্ধ-নির্দিষ্ট ম্যাট্রিক্সের সঠিক সিলভেস্টার মানদণ্ড প্রদান করা

ম্যাট্রিক্স সমাপ্তি

  • গ্রোন এবং অন্যান্য (১৯৮৪): জ্যা গ্রাফে ধনাত্মক নির্দিষ্ট/অর্ধ-নির্দিষ্ট ম্যাট্রিক্স সমাপ্তি তত্ত্ব
  • ব্যারেট এবং অন্যান্য (১৯৮৯): জ্যা গ্রাফের সাথে সম্পর্কিত ম্যাট্রিক্স সমাপ্তি নির্ধারক সূত্র
  • জনসন (১৯৯০): ম্যাট্রিক্স সমাপ্তি সমস্যা সমীক্ষা

অর্ধ-নির্দিষ্ট প্রোগ্রামিং

  • ইয়ামাশিতা এবং ইয়াবে (২০১৫): অ-রৈখিক অর্ধ-নির্দিষ্ট প্রোগ্রামিং সংখ্যাগত পদ্ধতি সমীক্ষা

সিদ্ধান্ত এবং আলোচনা

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

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

সীমাবদ্ধতা

  1. বিশেষ ক্ষেত্রে পরিচালনা: যখন নির্দিষ্ট সাব-ম্যাট্রিক্স অ-বিপরীতযোগ্য হয়, অতিরিক্ত সীমানা ক্ষেত্রে বিশ্লেষণের প্রয়োজন
  2. গণনামূলক বাস্তবায়ন: যদিও তাত্ত্বিক জটিলতা হ্রাস পায়, নির্দিষ্ট বাস্তবায়ন এখনও সংখ্যাগত স্থিতিশীলতা বিবেচনা করতে হবে
  3. উচ্চ-মাত্রা সম্প্রসারণ: অত্যন্ত উচ্চ-মাত্রার ম্যাট্রিক্সের জন্য, O(m2)O(m^2) এর জটিলতা এখনও একটি বাধা হতে পারে

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

  1. সংখ্যাগত অ্যালগরিদম: দক্ষ এবং স্থিতিশীল সংখ্যাগত বাস্তবায়ন অ্যালগরিদম বিকাশ করা
  2. সমান্তরাল গণনা: সমান্তরাল গণনা ব্যবহার করে দক্ষতা আরও উন্নত করা
  3. প্রয়োগ সম্প্রসারণ: মেশিন লার্নিং, সিগন্যাল প্রসেসিং এবং অন্যান্য ক্ষেত্রে প্রয়োগ অন্বেষণ করা

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

সুবিধা

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

অপূর্ণতা

  1. বাস্তবায়ন বিবরণ অপর্যাপ্ত: নির্দিষ্ট সংখ্যাগত বাস্তবায়ন অ্যালগরিদম এবং জটিলতা বিশ্লেষণের অভাব
  2. বড় আকারের যাচাইকরণ অনুপস্থিত: তাত্ত্বিক সুবিধা যাচাই করার জন্য বড় আকারের সংখ্যাগত পরীক্ষা প্রদান করা হয়নি
  3. সীমানা ক্ষেত্রে জটিলতা: বিশেষ ক্ষেত্রের পরিচালনা বাস্তবায়ন জটিলতা বৃদ্ধি করে

প্রভাব

  1. বড় তাত্ত্বিক অবদান: ম্যাট্রিক্স তত্ত্বের জন্য গুরুত্বপূর্ণ তাত্ত্বিক সরঞ্জাম প্রদান করা
  2. বিস্তৃত প্রয়োগ সম্ভাবনা: অপ্টিমাইজেশন, পরিসংখ্যান, মেশিন লার্নিং এবং অন্যান্য ক্ষেত্রে প্রয়োগের সম্ভাবনা রয়েছে
  3. ভাল পুনরুৎপাদনযোগ্যতা: তাত্ত্বিক ফলাফল সম্পূর্ণরূপে পুনরুৎপাদনযোগ্য, পরবর্তী গবেষণার জন্য ভিত্তি স্থাপন করে

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

  1. উচ্চ-মাত্রার সহ-পরিবর্তন ম্যাট্রিক্স বিশ্লেষণ: পরিসংখ্যানে সহ-পরিবর্তন ম্যাট্রিক্স অর্ধ-নির্দিষ্টতা যাচাইকরণ
  2. অর্ধ-নির্দিষ্ট প্রোগ্রামিং সমাধান: অর্ধ-নির্দিষ্ট প্রোগ্রামিংয়ের জন্য নতুন সীমাবদ্ধতা পরিচালনা পদ্ধতি প্রদান করা
  3. ম্যাট্রিক্স সমাপ্তি সমস্যা: বিশেষত অ-জ্যা গ্রাফ কাঠামোর ম্যাট্রিক্স সমাপ্তির জন্য উপযুক্ত
  4. মেশিন লার্নিং: কার্নেল ম্যাট্রিক্স, সাদৃশ্য ম্যাট্রিক্সের অর্ধ-নির্দিষ্টতা যাচাইকরণ

রেফারেন্স

পেপারটি ১৮টি সম্পর্কিত রেফারেন্স উদ্ধৃত করে, যা ম্যাট্রিক্স তত্ত্ব, অর্ধ-নির্দিষ্ট প্রোগ্রামিং, ম্যাট্রিক্স সমাপ্তি এবং অন্যান্য সম্পর্কিত ক্ষেত্রের ক্লাসিক এবং অগ্রগামী কাজ অন্তর্ভুক্ত করে, গবেষণার জন্য একটি শক্তিশালী তাত্ত্বিক ভিত্তি প্রদান করে।

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ মানের তাত্ত্বিক গণিত পেপার যা ক্লাসিক সিলভেস্টার মানদণ্ডের ভিত্তিতে গুরুত্বপূর্ণ অগ্রগতি অর্জন করেছে। যদিও এটি বড় আকারের সংখ্যাগত পরীক্ষার অভাব রাখে, তবে এর তাত্ত্বিক অবদান এবং ব্যবহারিক মূল্য এটিকে ম্যাট্রিক্স তত্ত্ব ক্ষেত্রের একটি গুরুত্বপূর্ণ অগ্রগতি করে তোলে।