ในการตรวจจับแบบบีบอัด คุณสมบัติ ช่องว่างว่างให้เงื่อนไขที่จำเป็นและเพียงพอในการสร้างสัญญาณแบบเบาบางขึ้นใหม่โดยใช้เทคนิคการผ่อนคลายคำว่า "คุณสมบัติช่องว่างว่าง" มาจาก Cohen, Dahmen และ DeVore ^{[ 1 ]}คุณสมบัติช่องว่างว่างมักตรวจสอบได้ยากในทางปฏิบัติ และคุณสมบัติไอโซเมตรีแบบจำกัดเป็นเงื่อนไขที่ทันสมัยกว่าในสาขาการตรวจจับแบบบีบอัด ${\displaystyle \ell _{1}}$

ปัญหาการหาค่าต่ำ สุด ที่ไม่นูน${\displaystyle \ell _{0}}$

${\displaystyle \min \limits _{x}\|x\|_{0}}$ ขึ้นอยู่กับเงื่อนไข ${\displaystyle Ax=b}$

เป็นปัญหามาตรฐานในการตรวจจับแบบบีบอัด อย่างไรก็ตามการลดค่า -minimization เป็นที่ทราบกันดีว่าเป็นปัญหาNP-hardโดยทั่วไป^{[ 2 ]}ด้วยเหตุนี้ บางครั้งจึงใช้เทคนิคการผ่อนคลาย -relaxation เพื่อหลีกเลี่ยงความยากลำบากในการสร้างสัญญาณขึ้นใหม่โดยใช้-norm ในการผ่อนคลาย -relaxation ปัญหา ${\displaystyle \ell _{0}}$${\displaystyle \ell _{1}}$${\displaystyle \ell _{0}}$${\displaystyle \ell _{1}}$${\displaystyle \ell _{1}}$

${\displaystyle \min \limits _{x}\|x\|_{1}}$ ขึ้นอยู่กับเงื่อนไข ${\displaystyle Ax=b}$

ได้รับการแก้ไขแทนที่ปัญหา โปรดทราบว่าการผ่อนคลายนี้เป็นแบบนูน ดังนั้นจึงเหมาะสมกับเทคนิคมาตรฐานของการเขียนโปรแกรมเชิงเส้นซึ่งเป็นคุณสมบัติที่พึงประสงค์ในเชิงการคำนวณ โดยธรรมชาติแล้วเราต้องการทราบว่าเมื่อใดการผ่อนคลายจะให้คำตอบเดียวกันกับปัญหา คุณสมบัติของปริภูมิว่างเป็นวิธีหนึ่งที่จะรับประกันความสอดคล้องกัน ${\displaystyle \ell _{0}}$${\displaystyle \ell _{1}}$${\displaystyle \ell _{0}}$

เมทริกซ์เชิงซ้อน มีคุณสมบัติของปริภูมิว่างอันดับ n ถ้าสำหรับเซตดัชนีทั้งหมดที่มีเรามีว่า: สำหรับทุก ${\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\}}$

ทฤษฎีบทต่อไปนี้ให้เงื่อนไขที่จำเป็นและเพียงพอสำหรับการกู้คืนเวกเตอร์สปาร์สที่กำหนดใน การพิสูจน์ ทฤษฎีบทนี้เป็นแบบมาตรฐาน และการพิสูจน์ที่ให้ไว้ที่นี่สรุปมาจาก Holger Rauhut ^{[ 3 ]}${\displaystyle s}$${\displaystyle \mathbb {C} ^{n}}$

${\displaystyle {\textbf {ทฤษฎีบท:}}}$ให้ เป็น เมทริกซ์เชิงซ้อนสัญญาณ -sparse ทุกตัว จะเป็นคำตอบเฉพาะของปัญหา -relaxation ที่มีก็ต่อเมื่อสอดคล้องกับคุณสมบัติของปริภูมิว่างที่มีอันดับ ${\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 {หลักฐาน:}}}$สำหรับทิศทางไปข้างหน้า โปรดสังเกตว่าและเป็นเวกเตอร์ที่แตกต่างกัน โดยอาศัยความเป็นเชิงเส้นของและด้วยเหตุนี้โดยความไม่ซ้ำกัน เราจึงต้องได้ตามที่ต้องการ สำหรับทิศทางย้อนกลับ ให้เป็น เวกเตอร์แบบ -sparse และ อีก เวกเตอร์หนึ่ง (ไม่จำเป็นต้อง เป็น -sparse) โดยที่ และกำหนดเวกเตอร์ (ที่ไม่เป็นศูนย์) และสังเกตว่ามันอยู่ในปริภูมิว่างของ เรียกส่วนรองรับของ ว่าและจากนั้นผลลัพธ์จะตามมาจากการประยุกต์ใช้อสมการสามเหลี่ยม อย่างง่าย : ซึ่งเป็นการพิสูจน์ความน้อยที่สุดของ${\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 }$