Matrix completion
ম্যাট্রিক্স সমাপ্তি হল আংশিকভাবে পর্যবেক্ষিত ম্যাট্রিক্সের অনুপস্থিত এন্ট্রিগুলি পূরণ করার কাজ, যা পরিসংখ্যানে ডেটা ইমপুটেশন সম্পাদনের সমতুল্য। ডেটাসেটের একটি বিস্তৃত পরিসর স্বাভাবিকভাবেই ম্যাট্রিক্স আকারে সংগঠিত হয়। একটি উদাহরণ হল মুভি-রেটিং ম্যাট্রিক্স, যা নেটফ্লিক্স সমস্যায় দেখা যায়ঃ একটি রেটিং ম্যাট্রিক্স দেওয়া হয়েছে যেখানে প্রতিটি এন্ট্রি গ্রাহকের দ্বারা চলচ্চিত্রের রেটিং উপস্থাপন করে, যদি গ্রাহক সিনেমা দেখে থাকেন এবং অন্যথায় অনুপস্থিত থাকেন, আমরা গ্রাহকদের পরবর্তী কী দেখতে হবে সে সম্পর্কে ভাল সুপারিশ করার জন্য অবশিষ্ট এন্ট্রিগুলির পূর্বাভাস দিতে চাই। আরেকটি উদাহরণ হল ডকুমেন্ট-টার্ম ম্যাট্রিক্সঃ নথির সংগ্রহে ব্যবহৃত শব্দের ফ্রিকোয়েন্সিগুলি ম্যাট্রিক্স হিসাবে উপস্থাপন করা যেতে পারে, যেখানে প্রতিটি এন্ট্রি নির্দেশিত নথিতে সংশ্লিষ্ট শব্দটি কতবার উপস্থিত হয় তার সাথে মিলে যায়। সম্পূর্ণ ম্যাট্রিক্সে স্বাধীনতার মাত্রার সংখ্যার উপর কোনও বিধিনিষেধ ছাড়াই এই সমস্যাটি অনির্ধারিত কারণ লুকানো এন্ট্রিগুলিকে নির্বিচারে মান বরাদ্দ করা যেতে পারে। সুতরাং একটি সুপ্রতিষ্ঠিত সমস্যা তৈরি করার জন্য ম্যাট্রিক্সের উপর আমাদের কিছু অনুমানের প্রয়োজন, যেমন এটির সর্বাধিক নির্ধারক রয়েছে, ধনাত্মক নির্দিষ্ট, বা নিম্ন-র্যাঙ্ক রয়েছে। উদাহরণস্বরূপ, কেউ ধরে নিতে পারে যে ম্যাট্রিক্সের নিম্ন-র্যাঙ্ক কাঠামো রয়েছে এবং তারপরে সর্বনিম্ন র্যাঙ্ক ম্যাট্রিক্স খুঁজে বের করার চেষ্টা করতে পারে বা, যদি সম্পূর্ণ ম্যাট্রিক্সের র্যাঙ্ক জানা থাকে, তবে পরিচিত এন্ট্রির সাথে মেলে এমন র্যাঙ্কের একটি ম্যাট্রিক্স। চিত্রটি দেখায় যে আংশিকভাবে প্রকাশিত র্যাঙ্ক-1 ম্যাট্রিক্স (বামদিকে) শূন্য-ত্রুটি (ডানদিকে) দিয়ে সম্পন্ন করা যেতে পারে কারণ অনুপস্থিত এন্ট্রি সহ সমস্ত সারি তৃতীয় সারির মতোই হওয়া উচিত। নেটফ্লিক্স সমস্যার ক্ষেত্রে রেটিং ম্যাট্রিক্স কম র্যাঙ্কের হবে বলে আশা করা হচ্ছে কারণ ব্যবহারকারীর পছন্দগুলি প্রায়শই কয়েকটি কারণ দ্বারা বর্ণনা করা যেতে পারে, যেমন চলচ্চিত্রের ধারা এবং মুক্তির সময়। অন্যান্য প্রয়োগগুলির মধ্যে রয়েছে কম্পিউটার দৃষ্টি, যেখানে চিত্রগুলিতে অনুপস্থিত পিক্সেলগুলি পুনর্গঠন করা প্রয়োজন, আংশিক দূরত্বের তথ্য থেকে একটি নেটওয়ার্কে সেন্সরগুলির বিশ্বব্যাপী অবস্থান সনাক্ত করা এবং মাল্টিক্লাস লার্নিং। ম্যাট্রিক্স সমাপ্তির সমস্যাটি সাধারণভাবে এনপি-হার্ড, তবে অতিরিক্ত অনুমানের অধীনে দক্ষ অ্যালগরিদম রয়েছে যা উচ্চ সম্ভাবনার সাথে সঠিক পুনর্গঠন অর্জন করে। পরিসংখ্যানগত শিক্ষার দৃষ্টিকোণ থেকে, ম্যাট্রিক্স সমাপ্তি সমস্যা হল ম্যাট্রিক্স নিয়মিতকরণের একটি প্রয়োগ যা ভেক্টর নিয়মিতকরণের একটি সাধারণীকরণ। উদাহরণস্বরূপ, নিম্ন-পদমর্যাদার ম্যাট্রিক্স সমাপ্তির সমস্যায় কেউ পারমাণবিক আদর্শ নিম্ন-পদমর্যাদার ম্যাট্রিক্স সমাপ্তির রূপ নিয়ে নিয়মিতকরণ জরিমানা প্রয়োগ করতে পারে ম্যাট্রিক্স সমাপ্তির সমস্যার একটি রূপ হল ম্যাট্রিক্সের সাথে মেলে এমন সর্বনিম্ন র্যাঙ্ক ম্যাট্রিক্স খুঁজে বের করা, যা আমরা পুনরুদ্ধার করতে চাই, পর্যবেক্ষিত এন্ট্রির সেটের সমস্ত এন্ট্রির জন্য। এই সমস্যার গাণিতিক সূত্রটি নিম্নরূপঃ ক্যান্ডেস এবং রেক্ট প্রমাণ করেছেন যে পর্যবেক্ষিত এন্ট্রিগুলির নমুনা এবং পর্যাপ্ত সংখ্যক নমুনা এন্ট্রিগুলির অনুমানের সাথে এই সমস্যার উচ্চ সম্ভাব্যতা সহ একটি অনন্য সমাধান রয়েছে। একটি সমতুল্য সূত্র, যে ম্যাট্রিক্সটি পুনরুদ্ধার করা হবে তা র্যাঙ্ক হিসাবে পরিচিত, যেখানে অনুমানের জন্য সমাধান করা হয় পর্যবেক্ষণ করা এন্ট্রিগুলির নমুনা এবং নমুনা এন্ট্রিগুলির সংখ্যা সম্পর্কে বেশ কয়েকটি অনুমান বিশ্লেষণকে সহজতর করার জন্য এবং সমস্যাটি নিশ্চিত করার জন্য ঘন ঘন করা হয়। পর্যবেক্ষিত এন্ট্রিগুলির অভিন্ন নমুনা বিশ্লেষণকে ট্র্যাক্টেবল করার জন্য, প্রায়শই ধরে নেওয়া হয় যে পর্যবেক্ষিত এন্ট্রিগুলির সেট এবং নির্দিষ্ট কার্ডিনালিটি কার্ডিনালিটির সমস্ত উপসেটগুলির সংগ্রহ থেকে এলোমেলোভাবে সমানভাবে নমুনা নেওয়া হয়। বিশ্লেষণকে আরও সহজ করার জন্য, এটি ধারণা করা হয় যে এটি বার্নৌলি স্যাম্পলিং দ্বারা নির্মিত, অর্থাৎ। যে প্রতিটি এন্ট্রি সম্ভাব্যতা সঙ্গে পালন করা হয়। যদি সেট করা হয় যেখানে কাঙ্ক্ষিত প্রত্যাশিত কার্ডিনালিটি, এবং ম্যাট্রিক্সের মাত্রা (সাধারণতার ক্ষতি ছাড়াই), উচ্চ সম্ভাবনার মধ্যে থাকে, সুতরাং বার্নৌলি স্যাম্পলিং ইউনিফর্ম স্যাম্পলিংয়ের জন্য একটি ভাল আনুমানিক। আরেকটি সরলীকরণ হল অনুমান করা যে এন্ট্রিগুলি স্বাধীনভাবে এবং প্রতিস্থাপনের সাথে নমুনা করা হয়। পর্যবেক্ষিত এন্ট্রির সংখ্যার উপর নিম্ন সীমা ধরা যাক ম্যাট্রিক্স দ্বারা (সহ) আমরা পুনরুদ্ধার করার চেষ্টা করছি র্যাঙ্ক আছে। অনন্যভাবে পুনর্গঠন করার আগে কতগুলি এন্ট্রি পর্যবেক্ষণ করতে হবে তার উপর একটি তথ্য তাত্ত্বিক নিম্ন সীমা রয়েছে। এর চেয়ে কম বা সমান র্যাঙ্ক সহ ম্যাট্রিক্স দ্বারা সেটটি মাত্রা সহ একটি বীজগাণিতিক বৈচিত্র্য। এই ফলাফলটি ব্যবহার করে, কেউ দেখাতে পারে যে ম্যাট্রিক্স সমাপ্তির জন্য একটি অনন্য সমাধান পেতে কমপক্ষে এন্ট্রিগুলি অবশ্যই পর্যবেক্ষণ করতে হবে। দ্বিতীয়ত, প্রতিটি সারিতে এবং কলামে কমপক্ষে একটি পর্যবেক্ষিত এন্ট্রি থাকতে হবে। এর একক মান পচন দ্বারা দেওয়া হয়। যদি সারিটি পর্যবেক্ষিত না থাকে, তবে এর সঠিক একক ভেক্টরটি সহজেই দেখা যায়, কিছু নির্বিচারে মান পরিবর্তন করা যেতে পারে এবং এখনও পর্যবেক্ষিত এন্ট্রিগুলির সেটের সাথে মিলে যাওয়া একটি ম্যাট্রিক্স দেয়। একইভাবে, যদি কলামটি অবলোকন করা না থাকে, তবে এর বাম একবচন ভেক্টরটি নির্বিচারে হতে পারে। যদি আমরা পর্যবেক্ষিত এন্ট্রিগুলির সেটের বার্নৌলি স্যাম্পলিং ধরে নিই, তবে কুপন সংগ্রাহক প্রভাব বোঝায় যে প্রতিটি সারি এবং কলাম থেকে উচ্চ সম্ভাব্যতা সহ একটি পর্যবেক্ষণ রয়েছে তা নিশ্চিত করার জন্য ক্রমের এন্ট্রিগুলি অবশ্যই পর্যবেক্ষণ করা উচিত। প্রয়োজনীয় শর্তগুলির সংমিশ্রণ এবং ধরে নেওয়া যে (অনেক ব্যবহারিক প্রয়োগের জন্য একটি বৈধ অনুমান), ম্যাট্রিক্স সমাপ্তির সমস্যাটিকে অনির্ধারিত হওয়া থেকে রোধ করার জন্য প্রয়োজনীয় পর্যবেক্ষিত এন্ট্রিগুলির সংখ্যার উপর নিম্ন সীমাটি ক্রম অনুসারে রয়েছে। অসংলগ্নতা অসংলগ্নতার ধারণাটি সংকুচিত সংবেদনশীলতায় উদ্ভূত হয়েছিল। এটি ম্যাট্রিক্স সমাপ্তির প্রসঙ্গে চালু করা হয়েছে যাতে প্রতিটি একক ভেক্টরের সমস্ত স্থানাঙ্ক উল্লেখযোগ্যভাবে বড় আয়তনের মাত্র কয়েকটি স্থানাঙ্কের পরিবর্তে তুলনামূলক মাত্রার হয় এই অর্থে এর একক ভেক্টরগুলি খুব "বিরল" না হয়। স্ট্যান্ডার্ড বেসিস ভেক্টরগুলি তখন একক ভেক্টর হিসাবে অবাঞ্ছিত, এবং ভেক্টরটি কাম্য। যদি একক ভেক্টরগুলি যথেষ্ট পরিমাণে "বিরল" হয় তবে কী ভুল হতে পারে তার একটি উদাহরণ হিসাবে, একক মান পচন সহ ম্যাট্রিক্স দ্বারা বিবেচনা করুন। এটি পুনর্নির্মাণের আগে প্রায় সমস্ত এন্ট্রিগুলির নমুনা সংগ্রহ করা আবশ্যক। ক্যান্ডেস এবং রেচ্ট কলাম স্পেসের সাথে একটি ম্যাট্রিক্সের সঙ্গতিকে একটি মাত্রিক সাবস্পেস হিসাবে সংজ্ঞায়িত করেছেন, যেখানে অর্থোগোনাল অভিক্ষেপ রয়েছে। অসঙ্গতি তখন দাবি করে যে ম্যাট্রিক্স দ্বারা একক মান পচন দেওয়া হলে, এর এন্ট্রিগুলির মাত্রা কিছু জন্য উচ্চতর আবদ্ধ থাকে। শব্দ সহ নিম্ন র্যাঙ্ক ম্যাট্রিক্স সমাপ্তি বাস্তব বিশ্বের প্রয়োগে, কেউ প্রায়শই কমপক্ষে অল্প পরিমাণে গোলমাল দ্বারা দূষিত কয়েকটি এন্ট্রি পর্যবেক্ষণ করে। উদাহরণস্বরূপ, নেটফ্লিক্সের সমস্যায় রেটিং অনিশ্চিত। ক্যান্ডেস এবং প্ল্যান দেখিয়েছেন যে নিউক্লিয়ার নর্ম মিনিমাইজেশন দ্বারা মাত্র কয়েকটি কোলাহলপূর্ণ নমুনা থেকে বড় নিম্ন-পদমর্যাদার ম্যাট্রিক্সের অনেক অনুপস্থিত এন্ট্রি পূরণ করা সম্ভব। গোলমাল মডেলটি ধরে নেয় যে আমরা লক্ষ্য করি যে একটি গোলমাল শব্দ কোথায়। মনে রাখবেন যে শব্দটি অপ্রচলিত বা নির্ণায়ক হতে পারে। বিকল্পভাবে মডেলটিকে এমনভাবে প্রকাশ করা যেতে পারে যেখানে কিছু লোকের জন্য এটি ধরে নেওয়ার জন্য এন্ট্রি সহ একটি ম্যাট্রিক্স রয়েছে। অসম্পূর্ণ ম্যাট্রিক্স পুনরুদ্ধারের জন্য, আমরা নিম্নলিখিত অপ্টিমাইজেশন সমস্যাটি সমাধান করার চেষ্টা করিঃ তথ্যের সাথে সামঞ্জস্যপূর্ণ সমস্ত ম্যাট্রিক্সের মধ্যে, ন্যূনতম পারমাণবিক আদর্শ সহ একটি খুঁজে বের করুন। ক্যান্ডেস এবং প্ল্যান দেখিয়েছে যে এই পুনর্গঠন সঠিক। তারা প্রমাণ করেছে যে যখন নিখুঁত শব্দহীন পুনরুদ্ধার ঘটে, তখন ম্যাট্রিক্স সমাপ্তি একটি বিশৃঙ্খলার তুলনায় স্থিতিশীল হয়। ত্রুটিটি গোলমালের মাত্রার সাথে আনুপাতিক। অতএব, যখন শব্দের মাত্রা কম হয়, তখন ত্রুটিটি ছোট হয়। এখানে ম্যাট্রিক্স সমাপ্তি সমস্যা সীমাবদ্ধ আইসোমেট্রি সম্পত্তি (আরআইপি) মেনে চলে না। ম্যাট্রিক্সের জন্য, আরআইপি ধরে নেবে যে স্যাম্পলিং অপারেটর যথেষ্ট ছোট এবং যথেষ্ট ছোট র্যাঙ্ক সহ সমস্ত ম্যাট্রিক্সের জন্য মেনে চলে। পদ্ধতিগুলি বিরল সংকেত পুনরুদ্ধারের সমস্যাগুলির ক্ষেত্রেও প্রযোজ্য যেখানে আর. আই. পি ধারণ করে না। উচ্চ পদমর্যাদার ম্যাট্রিক্স সমাপ্তি সাধারণভাবে উচ্চ পদমর্যাদার ম্যাট্রিক্স সমাপ্তি হল এন. পি-হার্ড। যাইহোক, কিছু অনুমান সহ, কিছু অসম্পূর্ণ উচ্চ র্যাঙ্ক ম্যাট্রিক্স বা এমনকি পূর্ণ র্যাঙ্ক ম্যাট্রিক্স সম্পন্ন করা যেতে পারে। এরিকসন, বালজানো এবং নোভাক একটি ম্যাট্রিক্স সম্পূর্ণ করার সমস্যাটিকে এই অনুমানের সাথে বিবেচনা করেছেন যে ম্যাট্রিক্সের কলামগুলি একাধিক নিম্ন-র্যাঙ্কের সাবস্পেসের একটি ইউনিয়নের অন্তর্গত। যেহেতু কলামগুলি সাবস্পেসগুলির একটি ইউনিয়নের অন্তর্গত, তাই সমস্যাটিকে সাবস্পেস ক্লাস্টারিং সমস্যার একটি অনুপস্থিত-তথ্য সংস্করণ হিসাবে দেখা যেতে পারে। ধরা যাক এমন একটি ম্যাট্রিক্স যার (সম্পূর্ণ) কলামগুলি সর্বাধিক সাবস্পেসের একটি ইউনিয়নে থাকে, প্রতিটি, এবং ধরে নিন। এরিকসন, বালজানো এবং নোভাক দেখিয়েছেন যে হালকা অনুমানের অধীনে প্রতিটি কলাম একটি অসম্পূর্ণ সংস্করণ থেকে উচ্চ সম্ভাবনার সাথে নিখুঁতভাবে পুনরুদ্ধার করা যেতে পারে যতক্ষণ না কমপক্ষে এন্ট্রিগুলি এলোমেলোভাবে অভিন্নভাবে পর্যবেক্ষণ করা হয়, স্বাভাবিক অসঙ্গতিপূর্ণ অবস্থার উপর নির্ভর করে একটি ধ্রুবক সহ, উপস্থানগুলির জ্যামিতিক ব্যবস্থা এবং উপস্থানগুলির উপর কলামগুলির বিতরণ। অ্যালগরিদমটিতে বেশ কয়েকটি ধাপ রয়েছেঃ (1) স্থানীয় এলাকা; (2) স্থানীয় সাবস্পেস; (3) সাবস্পেস পরিশোধন; (4) সম্পূর্ণ ম্যাট্রিক্স সমাপ্তি। এই পদ্ধতিটি ইন্টারনেট দূরত্ব ম্যাট্রিক্স সমাপ্তি এবং টপোলজি সনাক্তকরণে প্রয়োগ করা যেতে পারে। নিম্ন-র্যাঙ্ক ম্যাট্রিক্স সমাপ্তির জন্য অ্যালগরিদম বিভিন্ন ম্যাট্রিক্স সমাপ্তি অ্যালগরিদম প্রস্তাব করা হয়েছে। এর মধ্যে রয়েছে উত্তল শিথিলকরণ-ভিত্তিক অ্যালগরিদম, গ্রেডিয়েন্ট-ভিত্তিক অ্যালগরিদম এবং বিকল্প ন্যূনতমকরণ-ভিত্তিক অ্যালগরিদম। কনভেক্স রিল্যাক্সেশন র্যাঙ্ক মিনিমাইজেশন সমস্যা হল এনপি-হার্ড। ক্যান্ডেস এবং রেচ্ট দ্বারা প্রস্তাবিত একটি পদ্ধতি হল সমস্যার একটি উত্তল শিথিলতা তৈরি করা এবং পারমাণবিক আদর্শকে (যা এর একক মানের যোগফল দেয়) হ্রাস করা (যা এর অ-শূন্য একক মানের সংখ্যা গণনা করে)। এটি ভেক্টরের জন্য L0-আদর্শের পরিবর্তে L1-আদর্শকে ন্যূনতম করার অনুরূপ। উত্তল শিথিলতা সেমিডিফাইনাইট প্রোগ্রামিং (এসডিপি) ব্যবহার করে সমাধান করা যেতে পারে এটি লক্ষ্য করে যে অপ্টিমাইজেশন সমস্যাটি উত্তল শিথিলতা সমাধানের জন্য এসডিপি ব্যবহারের জটিলতা হল সমতুল্য। এসডিপিটি3-এর মতো অত্যাধুনিক সমাধানকারী শুধুমাত্র 100 বাই 100 আকারের ম্যাট্রিক্স পরিচালনা করতে পারে একটি বিকল্প প্রথম ক্রম পদ্ধতি যা প্রায় উত্তল শিথিলকরণ সমাধান করে তা হল কাই, ক্যান্ডেস এবং শেন দ্বারা প্রবর্তিত একক মান সীমাবদ্ধতা অ্যালগরিদম। ক্যান্ডেস এবং রেক্ট বানাচ স্পেসে র্যান্ডম ভেরিয়েবলের অধ্যয়ন ব্যবহার করে দেখান যে, যদি পর্যবেক্ষিত এন্ট্রিগুলির সংখ্যা (সাধারণতা হ্রাস না করে ধরে নেওয়া) এর ক্রমে থাকে, তবে র্যাঙ্ক মিনিমাইজেশন সমস্যার একটি অনন্য সমাধান রয়েছে যা কিছু ধ্রুবকের সম্ভাব্যতা সহ তার উত্তল শিথিলতার সমাধানও হতে পারে। যদি এর র্যাঙ্ক ছোট হয় (), তবে পর্যবেক্ষণের সেটের আকার এর ক্রমে কমে যায়। এই ফলাফলগুলি প্রায় সর্বোত্তম, যেহেতু ম্যাট্রিক্স সমাপ্তির সমস্যাটি অনির্ধারিত না হওয়ার জন্য ন্যূনতম সংখ্যক এন্ট্রি অবশ্যই পর্যবেক্ষণ করতে হবে। এই ফলাফলটি ক্যান্ডেস এবং তাও দ্বারা উন্নত করা হয়েছে। তারা অনুমানগুলিকে শক্তিশালী করে কেবল পলিলোগারিদমিক ফ্যাক্টর দ্বারা সর্বোত্তম সীমা থেকে পৃথক সীমা অর্জন করে। অসঙ্গতি বৈশিষ্ট্যের পরিবর্তে, তারা প্যারামিটারের সাথে শক্তিশালী অসঙ্গতি বৈশিষ্ট্যটি ধরে নেয়। এই বৈশিষ্ট্যটি বলে যেঃ জন্য এবং জন্য এর প্রবেশগুলি স্বজ্ঞাতভাবে, একটি ম্যাট্রিক্সের শক্তিশালী অসঙ্গতি দ্বারা সীমাবদ্ধ যে একক ভেক্টরগুলি এলোমেলোভাবে বিতরণ করা হলে স্ট্যান্ডার্ড বেসিস ভেক্টরগুলির অর্থোগোনাল প্রজেকশনগুলির মাত্রা থাকার উচ্চ সম্ভাবনা রয়েছে। ক্যান্ডেস এবং তাও দেখেছেন যে কখন আছে এবং পর্যবেক্ষিত এন্ট্রির সংখ্যা ক্রমানুসারে রয়েছে, র্যাঙ্ক মিনিমাইজেশন সমস্যার একটি অনন্য সমাধান রয়েছে যা কিছু ধ্রুবকের সম্ভাবনার সাথে তার উত্তল শিথিলতার সমাধানও হতে পারে। নির্বিচারে, এই দাবির জন্য যথেষ্ট পর্যবেক্ষিত এন্ট্রিগুলির সংখ্যা সত্য বলে মনে করা হয় আরেকটি উত্তল শিথিলকরণ পদ্ধতি হল র্যাঙ্ক সীমাবদ্ধতার অধীনে ফ্রোবেনিয়াস বর্গ আদর্শকে হ্রাস করা। এটি সমাধানের সমতুল্য ভায়া-এর র্যাঙ্ক মডেল করার জন্য একটি অর্থোগোনাল প্রজেকশন ম্যাট্রিক্স (অর্থ) প্রবর্তন করে এবং এই সমস্যার উত্তল শিথিলতা গ্রহণ করে, আমরা নিম্নলিখিত সেমিডিফাইনাইট প্রোগ্রামটি পাই যদি এই শিথিলতায় ওয়াই একটি প্রজেকশন ম্যাট্রিক্স (অর্থাৎ, বাইনারি আইগেনভ্যালু থাকে) হয়, তবে শিথিলতা টাইট হয়। অন্যথায়, এটি সামগ্রিক উদ্দেশ্যের উপর একটি বৈধ নিম্ন সীমা দেয়। অধিকন্তু, লোভের সাথে ওয়াই-এর আইগেনভ্যালুগুলিকে বৃত্তাকার করে এটিকে (সামান্য) বৃহত্তর উদ্দেশ্য সহ একটি সম্ভাব্য সমাধানে রূপান্তরিত করা যেতে পারে। উল্লেখযোগ্যভাবে, এই উত্তল শিথিলকরণ কোনও এসডিপি সমাধান না করে এক্স এবং ওয়াই-তে পর্যায়ক্রমে ন্যূনতমকরণের মাধ্যমে সমাধান করা যেতে পারে এবং এইভাবে এটি এসডিপিটি3 বা মোসেক-এর মতো অত্যাধুনিক এসডিপি সমাধানকারীদের সাধারণ সংখ্যাসূচক সীমার বাইরে চলে যায়। এই পদ্ধতিটি আরও সাধারণ সংস্কার কৌশলের একটি বিশেষ ক্ষেত্রে, যা ট্রেস-ম্যাট্রিক্স-কনভেক্স উদ্দেশ্য সহ যে কোনও নিম্ন-র্যাঙ্কের সমস্যার বৈধ নিম্ন সীমা অর্জনের জন্য প্রয়োগ করা যেতে পারে। গ্রেডিয়েন্ট ডিসেন্ট কেশবন, মন্টানারি এবং ওহ ম্যাট্রিক্স সমাপ্তির একটি বৈকল্পিক বিবেচনা করে যেখানে ম্যাট্রিক্স দ্বারা র্যাঙ্ক, যা পুনরুদ্ধার করা হবে, তা জানা যায়। তারা অনুমান করে যে বার্নৌলি এন্ট্রিগুলির নমুনা, ধ্রুবক দিক অনুপাত, এন্ট্রিগুলির সীমাবদ্ধ মাত্রা (উপরের সীমাটি হতে দিন), এবং ধ্রুবক শর্ত সংখ্যা (যেখানে এবং যথাক্রমে বৃহত্তম এবং ক্ষুদ্রতম একক মান)। উপরন্তু, তারা ধরে নেয় যে দুটি অসঙ্গতি শর্ত সন্তুষ্ট এবং কোথায় এবং ধ্রুবক। ধরা যাক এমন একটি ম্যাট্রিক্স যা পর্যবেক্ষিত এন্ট্রিগুলির সেটের সাথে মেলে এবং অন্য কোথাও 0 হয়। তারপরে তারা নিম্নলিখিত অ্যালগরিদমটি প্রস্তাব করেঃ কলামগুলিতে এন্ট্রিগুলি 0-তে সেট করার চেয়ে বড় ডিগ্রি সহ কলামগুলি থেকে সমস্ত পর্যবেক্ষণ সরিয়ে ছাঁটাই করুন। একইভাবে এর চেয়ে বড় ডিগ্রি সহ সারি থেকে সমস্ত পর্যবেক্ষণ সরিয়ে ফেলুন। এর প্রথম প্রধান উপাদানগুলির উপর প্রকল্প করুন। ফলস্বরূপ ম্যাট্রিক্স কল করুন। লাইন অনুসন্ধানের মাধ্যমে গ্রেডিয়েন্ট ডিসেন্ট দ্বারা কিছু নিয়মিতকরণ ফাংশন কোথায় তা সমাধান করুন। কোথায় শুরু করুন। কিছু ফাংশন হিসাবে সেট করুন যা গ্রেডিয়েন্ট ডিসেন্ট জুড়ে অসঙ্গতিপূর্ণ থাকতে বাধ্য করে যদি এবং অসঙ্গতিপূর্ণ হয়। ম্যাট্রিক্স ফিরিয়ে দিন। অ্যালগরিদমের ধাপ 1 এবং 2 উচ্চ সম্ভাব্যতা সহ সত্য ম্যাট্রিক্সের (মূল গড় বর্গ ত্রুটি (আরএমএসই) দ্বারা পরিমাপ করা) খুব কাছাকাছি একটি ম্যাট্রিক্স দেয়। বিশেষ করে, সম্ভাবনার সাথে, কিছু ধ্রুবকের জন্য। এটি ফ্রোবেনিয়াস আদর্শকে বোঝায়। মনে রাখবেন যে এই ফলাফল ধরে রাখার জন্য অনুমানের সম্পূর্ণ স্যুট প্রয়োজন হয় না। উদাহরণস্বরূপ, অসঙ্গতিপূর্ণ অবস্থা শুধুমাত্র সঠিক পুনর্গঠনের ক্ষেত্রে কার্যকর হয়। পরিশেষে, যদিও ছাঁটাই করা বিপরীত স্বজ্ঞাত বলে মনে হতে পারে কারণ এটি তথ্য নিক্ষেপ করার সাথে জড়িত, এটি নিশ্চিত করে যে তার প্রথম প্রধান উপাদানগুলিতে প্রজেক্ট করা পর্যবেক্ষিত এন্ট্রির চেয়ে অন্তর্নিহিত ম্যাট্রিক্স সম্পর্কে আরও তথ্য দেয়। ধাপ 3-এ, প্রার্থী ম্যাট্রিক্সের স্থান হ্রাস করা যেতে পারে এটি লক্ষ্য করে যে অভ্যন্তরীণ ন্যূনতমকরণ সমস্যার সমাধান কোথায় এবং ম্যাট্রিক্স দ্বারা অর্থোনরমাল। তারপর দুটি গ্রাসম্যান ম্যানিফোল্ডের ক্রস প্রোডাক্টের উপর গ্রেডিয়েন্ট ডিসেন্ট করা যেতে পারে। যদি এবং পর্যবেক্ষিত এন্ট্রি সেটটি এর ক্রমে থাকে, তবে ধাপ 3 দ্বারা ফেরত দেওয়া ম্যাট্রিক্সটি ঠিক। তারপর অ্যালগরিদমটি অর্ডার অপ্টিমাল, যেহেতু আমরা জানি যে ম্যাট্রিক্স সমাপ্তি সমস্যাটি অনির্ধারিত না হওয়ার জন্য এন্ট্রির সংখ্যা অবশ্যই এর ক্রমে থাকতে হবে। বিকল্প ন্যূনতম বর্গ হ্রাসকরণ বিকল্প ন্যূনতম হ্রাসকরণ প্রদত্ত তথ্যের সাথে সবচেয়ে উপযুক্ত নিম্ন-পদমর্যাদার ম্যাট্রিক্সগুলি খুঁজে বের করার জন্য একটি ব্যাপকভাবে প্রযোজ্য এবং অভিজ্ঞতাগতভাবে সফল পদ্ধতির প্রতিনিধিত্ব করে। উদাহরণস্বরূপ, নিম্ন-পদমর্যাদার ম্যাট্রিক্স সমাপ্তির সমস্যার জন্য, এই পদ্ধতিটি সবচেয়ে সঠিক এবং দক্ষ বলে মনে করা হয় এবং নেটফ্লিক্স সমস্যায় বিজয়ী প্রবেশের একটি প্রধান উপাদান গঠন করে। পর্যায়ক্রমে ন্যূনতমকরণ পদ্ধতিতে, নিম্ন-পদমর্যাদার লক্ষ্য ম্যাট্রিক্স একটি দ্বিমাত্রিক আকারে লেখা হয়ঃ অ্যালগরিদম তারপর সেরা এবং সেরা খুঁজে বের করার মধ্যে পরিবর্তিত হয়। যদিও সামগ্রিক সমস্যাটি অ-উত্তল, প্রতিটি উপ-সমস্যা সাধারণত উত্তল এবং দক্ষতার সাথে সমাধান করা যেতে পারে। জৈন, নেত্রপল্লী এবং সাংঘাভি ম্যাট্রিক্স সমাপ্তি এবং ম্যাট্রিক্স সেন্সিং উভয়ের জন্য পর্যায়ক্রমে মিনিমাইজেশন সম্পাদনের জন্য প্রথম গ্যারান্টি দিয়েছেন। বিকল্প ন্যূনতমকরণ অ্যালগরিদমকে নিম্নলিখিত অ-উত্তল সমস্যা সমাধানের আনুমানিক উপায় হিসাবে দেখা যেতে পারেঃ জৈন, নেত্রপল্লী এবং সাংঘাভি দ্বারা প্রস্তাবিত অল্টমিনকম্প্লিট অ্যালগরিদমটি এখানে তালিকাভুক্ত করা হয়েছেঃ ইনপুটঃ পর্যবেক্ষিত সেট, সমান সম্ভাব্যতা সহ (প্রতিস্থাপনের সাথে নমুনা) অর্থাৎ, ক্লিপিংয়ের উপরের-বাম একক ভেক্টরগুলির সাথে সম্পর্কিত প্রতিটি উপাদানের সাথে উপসেটগুলিতে বিভাজনের মান নির্ধারণ করেঃ শূন্যের চেয়ে বেশি মাত্রার সমস্ত উপাদান সেট করুন এবং রিটার্নের জন্য ডু এন্ডের কলামগুলিকে অর্থোনর্মালাইজ করুন তারা দেখিয়েছেন যে একটি অসঙ্গত ম্যাট্রিক্সের এলোমেলো এন্ট্রি পর্যবেক্ষণ করে, অল্টমিনকম্প্লিট অ্যালগরিদম ধাপে ধাপে পুনরুদ্ধার করতে পারে। নমুনা জটিলতার () পরিপ্রেক্ষিতে, তাত্ত্বিকভাবে, বিকল্প ন্যূনতমকরণের জন্য কনভেক্স রিল্যাক্সেশনের চেয়ে বড় প্রয়োজন হতে পারে। তবে পরীক্ষামূলকভাবে এটি এমন নয় বলে মনে হয় যা বোঝায় যে নমুনা জটিলতার সীমা আরও শক্ত করা যেতে পারে। সময়ের জটিলতার পরিপ্রেক্ষিতে, তারা দেখিয়েছেন যে অল্টমিনকম্প্লিটের সময় প্রয়োজন। এটি লক্ষণীয় যে, যদিও উত্তল শিথিলকরণ ভিত্তিক পদ্ধতিগুলির কঠোর বিশ্লেষণ রয়েছে, তবে বিকল্প ন্যূনতমকরণ ভিত্তিক অ্যালগরিদমগুলি অনুশীলনে আরও সফল। অ্যাপ্লিকেশন ম্যাট্রিক্স সমাপ্তির বেশ কয়েকটি অ্যাপ্লিকেশন ক্যান্ডেস এবং প্ল্যান দ্বারা নিম্নরূপ সংক্ষিপ্ত করা হয়েছেঃ সহযোগিতামূলক ফিল্টারিং সহযোগিতামূলক ফিল্টারিং হল অনেক ব্যবহারকারীর কাছ থেকে স্বাদের তথ্য সংগ্রহ করে ব্যবহারকারীর আগ্রহ সম্পর্কে স্বয়ংক্রিয় ভবিষ্যদ্বাণী করার কাজ। অ্যাপল, অ্যামাজন, বার্নস অ্যান্ড নোবেল এবং নেটফ্লিক্সের মতো সংস্থাগুলি আংশিক জ্ঞান থেকে তাদের ব্যবহারকারীর পছন্দগুলি পূর্বাভাস দেওয়ার চেষ্টা করছে। এই ধরনের ম্যাট্রিক্স সমাপ্তি সমস্যায়, অজানা পূর্ণ ম্যাট্রিক্সকে প্রায়শই নিম্ন র্যাঙ্ক হিসাবে বিবেচনা করা হয় কারণ শুধুমাত্র কয়েকটি কারণ সাধারণত একজন ব্যক্তির স্বাদ বা পছন্দের ক্ষেত্রে অবদান রাখে। সিস্টেম আইডেন্টিফিকেশন নিয়ন্ত্রণে, কেউ ইনপুট এবং আউটপুটগুলির একটি ক্রমের সাথে একটি বিচ্ছিন্ন-সময় রৈখিক সময়-অপরিবর্তনীয় রাজ্য-স্থান মডেল ফিট করতে চায়। ভেক্টর হল সেই সময়ে সিস্টেমের অবস্থা এবং সিস্টেম মডেলের ক্রম। ইনপুট/আউটপুট জোড়া থেকে, একজন ম্যাট্রিক্স এবং প্রাথমিক অবস্থা পুনরুদ্ধার করতে চাইবে। এই সমস্যাটিকে নিম্ন-পদমর্যাদার ম্যাট্রিক্স সমাপ্তি সমস্যা হিসাবেও দেখা যেতে পারে। ইন্টারনেট অফ থিংস (আইওটি) স্থানীয়করণ আইওটি সেন্সর নেটওয়ার্কগুলিতে স্থানীয়করণ (বা গ্লোবাল পজিশনিং) সমস্যা স্বাভাবিকভাবেই উদ্ভূত হয়। সমস্যাটি হল স্থানীয় বা আংশিক জোড়া দূরত্বের সেট থেকে ইউক্লিডীয় স্থানে সেন্সর মানচিত্রটি পুনরুদ্ধার করা। সুতরাং এটি একটি ম্যাট্রিক্স সমাপ্তি সমস্যা যদি সেন্সরগুলি 2-ডি সমতলে অবস্থিত হয় এবং তিনটি যদি তারা 3-ডি স্থানে থাকে। সামাজিক নেটওয়ার্ক পুনরুদ্ধার বাস্তব-বিশ্বের বেশিরভাগ সামাজিক নেটওয়ার্কে নিম্ন-পদমর্যাদার দূরত্বের ম্যাট্রিক্স রয়েছে। যখন আমরা সম্পূর্ণ নেটওয়ার্ক পরিমাপ করতে সক্ষম হই না, যা ব্যক্তিগত নোড, সীমিত সঞ্চয় বা গণনা সংস্থানগুলির মতো কারণে হতে পারে, তখন আমাদের কাছে কেবল দূরত্বের এন্ট্রির একটি ভগ্নাংশ জানা থাকে। অপরাধমূলক নেটওয়ার্কগুলি এই ধরনের নেটওয়ার্কগুলির একটি ভাল উদাহরণ। এই অবলোকন করা দূরত্বগুলি পুনরুদ্ধার করতে নিম্ন-পদমর্যাদার ম্যাট্রিক্স সমাপ্তি ব্যবহার করা যেতে পারে। আরও দেখুন ম্যাট্রিক্স নিয়মিতকরণ নেটফ্লিক্স পুরস্কার সহযোগিতামূলক ফিল্টারিং সিস্টেম আইডেন্টিফিকেশন কনভেক্স অপ্টিমাইজেশন ইম্প্যুটেশন রেফারেন্স ম্যাট্রিক্স তত্ত্ব