خاصية المسافة الفارغة

في الاستشعار المضغوط ، توفر خاصية الفضاء الصفري شروطًا ضرورية وكافية لإعادة بناء الإشارات المتفرقة باستخدام تقنيات${\displaystyle \ell _{1}}$الاسترخاء . يعود مصطلح "خاصية الفضاء الصفري" إلى كوهين، داهمن، وديفور. ^{[ 1 ]} غالبًا ما يصعب التحقق من خاصية الفضاء الصفري عمليًا، وتُعد خاصية التساوي المقيد شرطًا أحدث في مجال الاستشعار المضغوط.

غير محدب${\displaystyle \ell _{0}}$- مسألة التصغير،

${\displaystyle \min \limits _{x}\|x\|_{0}}$ رهناً بـ${\displaystyle Ax=b}$،

تُعدّ هذه مشكلة شائعة في الاستشعار المضغوط. ومع ذلك،${\displaystyle \ell _{0}}$من المعروف أن تقليل قيمة λ يمثل مشكلة من نوع NP-hard بشكل عام. ^{[ 2 ]} ولذلك، فإن تقنية${\displaystyle \ell _{1}}$يُستخدم الاسترخاء أحيانًا لتجاوز صعوبات إعادة بناء الإشارة باستخدام${\displaystyle \ell _{0}}$-norm. في${\displaystyle \ell _{1}}$الاسترخاء،${\displaystyle \ell _{1}}$مشكلة،

${\displaystyle \min \limits _{x}\|x\|_{1}}$ رهناً بـ${\displaystyle Ax=b}$،

يتم حلها بدلاً من${\displaystyle \ell _{0}}$المشكلة. لاحظ أن هذا التقريب محدب، وبالتالي فهو قابل للتطبيق على التقنيات القياسية للبرمجة الخطية - وهي ميزة مرغوبة حسابيًا. بطبيعة الحال، نرغب في معرفة متى${\displaystyle \ell _{1}}$-الاسترخاء سيعطي نفس الإجابة التي يعطيها${\displaystyle \ell _{0}}$مشكلة. خاصية الفراغ الصفري هي إحدى طرق ضمان التوافق.

أن${\displaystyle m\times n}$مصفوفة معقدة ${\displaystyle A}$يتمتع بخاصية الفضاء الصفري من الدرجة${\displaystyle s}$، إذا كان ذلك لجميع مجموعات الفهرس${\displaystyle S}$مع${\displaystyle s=|S|\leq n}$لدينا ذلك:${\displaystyle \|\eta _{S}\|_{1}<\|\eta _{S^{C}}\|_{1}}$ للجميع${\displaystyle \eta \in \ker {A}\setminus \left\{0\right\}}$.

تُقدّم النظرية التالية شرطًا ضروريًا وكافيًا لإمكانية استعادة شيء مُعطى${\displaystyle s}$متجه متفرق في${\displaystyle \mathbb {C} ^{n}}$إن برهان النظرية هو برهان قياسي، والبرهان المقدم هنا هو ملخص من هولجر راوهوت. ^{[ 3 ]}

${\displaystyle {\textbf {نظرية:}}}$يترك${\displaystyle A}$ كن ${\displaystyle m\times n}$المصفوفة المعقدة. ثم كل${\displaystyle s}$إشارة متفرقة${\displaystyle x\in \mathbb {C} ^{n}}$هو الحل الفريد لـ${\displaystyle \ell _{1}}$مشكلة الاسترخاء مع${\displaystyle b=Ax}$إذا وفقط إذا${\displaystyle A}$يحقق خاصية الفضاء الصفري بالترتيب${\displaystyle s}$.

${\displaystyle {\textit {الإثبات:}}}$لاحظ فيما يتعلق بالاتجاه الأمامي ما يلي:${\displaystyle \eta _{S}}$و${\displaystyle -\eta _{S^{C}}}$هي متجهات متميزة${\displaystyle A(-\eta _{S^{C}})=A(\eta _{S})}$بسبب خطية${\displaystyle A}$وبالتالي، بحكم التفرد، يجب أن يكون لدينا${\displaystyle \|\eta _{S}\|_{1}<\|\eta _{S^{C}}\|_{1}}$حسب الرغبة. أما بالنسبة للاتجاه العكسي، فليكن${\displaystyle x}$يكون${\displaystyle s}$-متفرق و${\displaystyle z}$آخر (ليس بالضرورة)${\displaystyle s}$متجه (متفرق) بحيث${\displaystyle z\neq x}$و${\displaystyle Az=Ax}$عرّف المتجه (غير الصفري)${\displaystyle \eta =xz}$ولاحظ أنها تقع في الفضاء الصفري لـ${\displaystyle A}$. يتصل${\displaystyle S}$دعم${\displaystyle x}$ثم تأتي النتيجة من تطبيق بسيط لمتباينة المثلث :${\displaystyle \|x\|_{1}\leq \|x-z_{S}\|_{1}+\|z_{S}\|_{1}=\|\eta _{S}\|_{1}+\|z_{S}\|_{1}<\|\eta _{S^{C}}\|_{1}+\|z_{S}\|_{1}=\|-z_{S^{C}}\|_{1}+\|z_{S}\|_{1}=\|z\|_{1}}$، مما يحدد الحد الأدنى من${\displaystyle x}$.${\displaystyle \square }$