छोटी 𝓁1‐नॉर्म समाधान अधिकांश बड़े अंडरडिटर्मिनेड रेखीय समीकरण प्रणालियों के लिए सबसे विरल समाधान भी होता है

सारांश हम रेखीय समीकरणों y = Φ x पर विचार करते हैं जहां y ℝ n में एक दिया गया वेक्टर है और Φ n × m मैट्रिक्स है जिसमें n 0 है। इसलिए बड़े n के लिए और सभी Φ के लिए, छोड़कर एक नगण्य अंश के, निम्नलिखित विशेषता होती है: हर y जिसका प्रतिनिधित्व y = Φ x 0 द्वारा एक गुणांक वेक्टर x 0 ∈ ℝ m के माध्यम से होता है जिसमें ρ · n से कम गैर-शून्य होते हैं, 𝓁1-न्यूनतमकरण समस्या का समाधान x 1 अद्वितीय होता है और x 0 के बराबर होता है। इसके विपरीत, ऐसी प्रणालियों को विरलता से हल करने के लिए हीयुरिस्टिक प्रयास—लालच से भरे एल्गोरिदम और थ्रेशोल्डिंग—इस चुनौतीपूर्ण स्थिति में खराब प्रदर्शन करते हैं। तकनीकों में बानच स्पेस सिद्धांत में यादृच्छिक आनुपातिक एम्बेडिंग और लगभग-गेंदीय अनुभागों का उपयोग शामिल है, और यादृच्छिक विशार्ट मैट्रिक्स के विशेष मानों के लिए विचलन सीमाएँ शामिल हैं। © 2006 विले पीरियडिकल्स, इंक.