RANDOM SENSINGReturning to the RIP,

RANDOM SENSING
Returning to the RIP, we would like to find sensing matrices
with the property that column vectors taken from arbitrary
subsets are nearly orthogonal. The larger these
subsets, the better.
This is where randomness re-enters the picture. Consider
the following sensing matrices: i) form A by sampling n column
vectors uniformly at random on the unit sphere of Rm;
ii) form A by sampling i.i.d. entries from the normal distribution
with mean 0 and variance 1/m; iii) form A by sampling
a random projection P as in “Incoherent Sampling”
and normalize: A =
√
n/mP; and iv) form A by sampling
i.i.d. entries from a symmetric Bernoulli distribution
(P(Ai, j= ±1/
√
m) = 1/2) or other sub-gaussian distribution.
With overwhelming probability, all these matrices obey
the RIP (i.e. the condition of our theorem) provided that
m ≥ C · Slog(n/S), (13)
where C is some constant depending on each instance. The
claims for i)–iii) use fairly standard results in probability theory;
arguments for iv) are more subtle; see [23] and the work of Pajor
and his coworkers, e.g., [24]. In all these examples, the probability
of sampling a matrix not obeying the RIP when (13) holds is
exponentially small in m. Interestingly, there are no measurement
matrices and no reconstruction algorithm whatsoever
which can give the conclusions of Theorem 2 with substantially
fewer samples than the left-hand side of (13) [2], [3]. In that
sense, using randomized matrices together with 1 minimization
is a near-optimal sensing strategy.
One can also establish the RIP for pairs of orthobases as in
“Incoherence and the Sensing of Sparse Signals.” With
A = R where R extracts m coordinates uniformly at random,
it is sufficient to have
m ≥ C · S(log n)
4
, (14)
for the property to hold with large probability; see [25] and [2].
If one wants a probability of failure no larger than O(n−β) for
some β > 0, then the best known exponent in (14) is five
instead of four (it is believed that (14) holds with just log n).

ผลลัพธ์ (ไทย) 1:

สุ่มตรวจความคัดลอก เราต้องการหาเมทริกซ์การตรวจด้วยคุณสมบัติคอลัมน์จากกำหนดเวกเตอร์ย่อยเป็น orthogonal เกือบ ใหญ่เหล่านี้ชุดย่อย ดีกว่าที่ randomness ใหม่ใส่รูปภาพได้ พิจารณาเมทริกซ์ sensing ดังต่อไปนี้: ฉัน) แบบกเชน n คอลัมน์เวกเตอร์สม่ำเสมอเมื่อเทียบเคียงสุ่มในเรื่องหน่วย Rmii) แบบ โดยสุ่มตัวอย่างรายการ i.i.d. จากการแจกแจงปกติมีค่าเฉลี่ย 0 และความแปรปรวน 1/m iii) แบบ โดยสุ่มตัวอย่างฉายแบบสุ่ม P ใน "สุ่มไม่ติดต่อกัน"และปกติ: =การ√n/mP และ iv) แบบก โดยสุ่มตัวอย่างรายการ i.i.d. จากการกระจายของ Bernoulli สมมาตร(P (Ai, j = ±1 /√m) = 1/2) หรือกระจายย่อย gaussian อื่น ๆด้วยการครอบงำความน่าเป็น เมทริกซ์เหล่านี้ฟังริพ (เช่นเงื่อนไขของทฤษฎีบทของเรา) มาที่m ≥ C · Slog(n/S), (13)โดยที่ C คือ บางขึ้นอยู่คงที่ในแต่ละอินสแตนซ์ ที่เรียกร้องหา) – iii) ใช้ผลลัพธ์ค่อนข้างมาตรฐานในทฤษฎีความน่าเป็นอาร์กิวเมนต์สำหรับ iv) มีรายละเอียดเพิ่มเติม ดู [23] และการทำงานของ Pajorและของเพื่อนร่วม งาน เช่น, [24] ในทุกตัวอย่างเหล่านี้ ความน่าเป็นของเมทริกซ์ไม่ก็ RIP เมื่อถือ (13)สร้างเล็กม.เป็นเรื่องน่าสนใจ มีวัดเมทริกซ์และอัลกอริทึมฟื้นฟูที่ไม่เลยซึ่งสามารถให้ข้อสรุปของทฤษฎีบทที่ 2 มากตัวอย่างน้อยกว่าด้านซ้ายของ (13) [2], [3] ในที่ความรู้สึก การใช้เมทริกซ์ randomized พร้อมลดภาระ 1คือกลยุทธ์การ sensing ใกล้ดีที่สุดหนึ่งยังสามารถสร้างการคัดลอกสำหรับคู่ของ orthobases ใน"Incoherence และตรวจวัดสัญญาณเบาบาง" ด้วยA = R ซึ่ง R แยกพิกัด m สม่ำเสมอเมื่อเทียบเคียงสุ่มก็เพียงพอให้m ≥ C · S (บันทึก n)4, (14สำหรับคุณสมบัติให้กดค้างไว้ ด้วยความน่าเป็นขนาดใหญ่ ดู [25] และ [2]หนึ่ง ต้องการความน่าเป็นของเหลวไม่มากกว่า O(n−β) สำหรับβ > 0 บาง แล้วยกรู้จักกันดีใน (14) มี 5แทนสี่ (เชื่อว่า ถือ (14) มีเพียงระบบ n)

ผลลัพธ์ (ไทย) 2:

RANDOM SENSING
กลับไป RIP เราต้องการที่จะหาการฝึกอบรมการตรวจจับ
กับทรัพย์สินที่เป็นพาหะนำมาจากคอลัมน์พล
ย่อยมีฉากเกือบ ขนาดใหญ่เหล่านี้
ย่อยที่ดีกว่า.
ซึ่งเป็นที่ที่สุ่มใหม่เข้าสู่ภาพ พิจารณา
การฝึกอบรมการตรวจจับต่อไปนี้: i) รูปแบบโดยการสุ่มตัวอย่างคอลัมน์ n
เวกเตอร์สม่ำเสมอที่สุ่มบนทรงกลมหน่วย Rm;
ii) รูปแบบโดยการสุ่มตัวอย่างรายการ IID จากการแจกแจงปกติ
ที่มีค่าเฉลี่ย 0 และความแปรปรวน 1 / เมตร iii) รูปแบบโดยการสุ่มตัวอย่าง
P ฉายแบบสุ่มในขณะที่ "การเก็บตัวอย่างต่อเนื่องกัน"
และปกติ: =
√
n MP /; และ iv) รูปแบบโดยการสุ่มตัวอย่าง
จากรายการ i.id กระจาย Bernoulli สมมาตร
(P (Ai, J = ± 1 /
√
เมตร) = 1/2) หรือการกระจายย่อย gaussian อื่น ๆ .
ด้วยความน่าจะเป็นที่ครอบงำการฝึกอบรมเหล่านี้เชื่อฟัง
RIP (เช่นสภาพของทฤษฎีบทของเรา) ระบุว่า
ม. ≥ c ·หวด (N / S) (13)
ที่ C เป็นค่าคงที่ขึ้นอยู่กับแต่ละกรณี
เรียกร้องสำหรับ i) -III) การใช้อย่างเป็นธรรมผลมาตรฐานในทฤษฎีความน่าจะเป็น
ข้อโต้แย้ง iv) เป็นที่ลึกซึ้งยิ่งขึ้น; ดู [23] และการทำงานของ Pajor
และเพื่อนร่วมงานของเขาเช่น [24] ในทุกตัวอย่างเหล่านี้น่าจะเป็น
ของการสุ่มตัวอย่างเมทริกซ์ไม่เชื่อฟัง RIP เมื่อ (13) ถือเป็น
ขนาดเล็กชี้แจงใน m ที่น่าสนใจไม่มีวัด
เมทริกซ์และไม่มีขั้นตอนวิธีการฟื้นฟูบูรณะใด ๆ
ที่สามารถให้ข้อสรุปของทฤษฎีบท 2 พร้อมด้วยอย่างมาก
ตัวอย่างน้อยกว่าด้านซ้ายมือของ (13) [2], [3] ในการที่
ความรู้สึก, การฝึกอบรมโดยใช้การสุ่มร่วมกับ? 1 ลด
เป็นกลยุทธ์การตรวจวัดที่อยู่ใกล้ที่ดีที่สุด.
หนึ่งยังสามารถสร้าง RIP สำหรับคู่ของ orthobases ในขณะที่
"เชื่อมโยงและการตรวจวัดสัญญาณเบาบาง." ด้วย
= R ?? ที่วิจัยสารสกัดจากม. พิกัดเหมือนกันที่สุ่ม
มันเพียงพอที่จะมี
ม. ≥ c · S (log N)
4
(14)
สำหรับคุณสมบัติที่จะถือด้วยความน่าจะเป็นขนาดใหญ่ ดู [25] และ [2].
หากต้องการความน่าจะเป็นของความล้มเหลวไม่ใหญ่กว่า O (n-β) สำหรับ
βบาง> 0 แล้วสัญลักษณ์ที่รู้จักกันดีที่สุดใน (14) เป็นห้า
แทนที่จะเป็นสี่ (มันมีความเชื่อว่า (14) ถือมีเพียง log n)

ผลลัพธ์ (ไทย) 3:

สุ่มตรวจจับ
กลับฉีก , เราต้องการที่จะค้นหาข้อมูลเมทริกซ์
กับทรัพย์สินที่ได้มาจากอำนาจเวกเตอร์คอลัมน์
ย่อยเกือบตั้งฉาก . ขนาดใหญ่เหล่านี้

ข้อมูลดีกว่า แล้วสุ่มอีกครั้งเข้าสู่ภาพ พิจารณาตามภาพ :
เมทริกซ์ ) รูปแบบคอลัมน์โดย n
เวกเตอร์จุดสุ่มบนหน่วยทรงกลมของ RM
) ;2 ) รูปแบบ โดยการสุ่มตัวอย่าง i.i.d. รายการจากการแจกแจงปกติที่มีค่าเฉลี่ยและความแปรปรวน
0 l / m ; 3 ) รูปแบบ 3
ฉายแบบ P ใน " แบบตัวอย่าง "
และปกติ : =
√
n / MP ; และ 4 ) รูปแบบ 3
i.i.d. รายการจาก สมมาตรการแจกแจงเบอร์นูลี
( P ( AI , J = ± 1 /
√
m ) = 1 / 2 ) หรืออื่น ๆเนื้อหาย่อยกระจาย .
กับความน่าจะเป็นที่ยุ่งยากเมทริกซ์ทั้งหมดเหล่านี้เชื่อฟัง
ฉีก ( เช่นสภาพของทฤษฎีบทของเรา ) ให้≥
M C ด้วยหวด ( N / S ) , ( 13 ) C
ที่เป็นค่าคงที่ขึ้นอยู่กับแต่ละอินสแตนซ์
เรียกร้องสำหรับฉัน ) – 3 ) ใช้ผลที่ค่อนข้างมาตรฐานในทฤษฎีความน่าจะเป็น ;
อาร์กิวเมนต์สำหรับ IV ) มากกว่า ดู [ 23 ] และการทำงานของ pajor
ของเขาและเพื่อนร่วมงาน เช่น [ 24 ] ในตัวอย่างเหล่านี้ทั้งหมด ความน่าจะเป็น
ของเมทริกซ์ไม่ต้องตัด ) เมื่อ ( 13 ) ถือเป็น
ชี้แจงเล็ก ๆ ใน ม. แต่ไม่มีการวัด
เมทริกซ์และไม่มีการฟื้นฟูขั้นตอนวิธีแต่ประการใด
ซึ่งสามารถให้ข้อสรุปของทฤษฎีบท 2 อย่างมาก
ตัวอย่างน้อยกว่าด้านซ้ายมือ ( 13 ) [ 2 ] , [ 3 ] ใน
ความรู้สึกแบบเมทริกซ์โดยใช้ร่วมกับ 
1 น้อยที่สุดเป็นใกล้ที่เหมาะสมจากกลยุทธ์ .
หนึ่งยังสามารถสร้างตัดสำหรับคู่ของ orthobases ในความไม่เชื่อมโยงกัน
" และตรวจจับสัญญาณหร็อมแหร็ม " ด้วย
= R   ที่ R M พิกัดจุดสกัดที่สุ่ม
ก็เพียงพอที่จะมี
M ≥ C ด้วย S ( log N )
4
,
( 14 ) สำหรับทรัพย์สินไว้กับความน่าจะเป็นขนาดใหญ่ ; เห็น [ 25 ] และ [ 2 ] .
หากต้องการความน่าจะเป็นของความล้มเหลวไม่ใหญ่กว่า O ( n
−β )บางบีตา > 0 แล้วที่รู้จักกันดีที่สุดของ ( 14 ) 5
แทนสี่ ( เชื่อกันว่า ( 14 ) ถือหุ้นเพียง log n )