تحديث الأوزان الضربية، وتقعر المنطقة، وانحدار الإحداثيات العشوائية لمشكلات الكثافة الفرعية

ندرس مشكلة الكثافة الفرعية الأكثر كثافة ونقدم خوارزميات عبر تحديث الأوزان الضربية وتقعر المنطقة التي تتقارب في O (m^{2}) و O (m) من التكرارات، على التوالي، مع وقت شبه خطي لكل تكرار. بالمقارنة مع عمل باهماني وزملائه (2014)، تستخدم خوارزمية MWU الخاصة بنا إجراءً مختلفًا وبسيطًا جدًا لاستعادة الكثافة الفرعية من الحل الكسري ولا تستعمل البحث الثنائي. مقارنةً بعمل بوب وزملائه (2019)، تقوم خوارزمية لدينا عبر تقعر المنطقة بتحسين تعقيد التكرار بعامل -- الحد الأقصى لدرجة في الرسم البياني، وتتناسب مع أسرع وقت نظري معروف حاليًا عبر التدفقات (شاكوري وزملائه، 2022) في الوقت الإجمالي. بعد ذلك، ندرس مشكلة تحليل الكثافة الفرعية ونقدم أول خوارزمية تكرارية عملية بمعدل تقارب خطي O (mn1) عبر انحدار الإحداثيات العشوائية المعجل. وهذا يحسن بشكل كبير عن الوقت O (mmn) لخوارزمية تعتمد على FISTA من هاربي وزملائه (2022). في نظام الدقة العالية 1n حيث يمكننا حتى استعادة الحل الدقيق، تمتلك خوارزمية لدينا وقت تشغيل إجمالي قدره O (mn n)، متطابقة مع الخوارزمية الدقيقة عبر التدفقات البارامترية (غالو وزملائه، 1989). بشكل تجريبي، نوضح أن هذه الخوارزمية عملية جدًا وتتناسب مع الرسوم البيانية الكبيرة جدًا، وأداؤها تنافسي مع الأساليب المستخدمة على نطاق واسع والتي تتمتع بضمانات نظرية أضعف بكثير.