Aşırı az örneklemede ikili sinyal kurtarma: Çoğunluk oylaması ve ardışık girişim iptali ile birlikte SDP

Abstract

İkili Seyrek Algılama (BCS), n uzunluğundaki k-seyrek bir ikili vektörün m doğrusal ölçümden (m≪n) kurtarılması problemini ele alır. Aşırı örnekleme eksikliği rejiminde (m<2k), geleneksel seyrek algılama (CS) garantileri geçerliliğini yitirir ve rastgele ölçüm matrisleri kullanan mevcut BCS algoritmaları yetersiz performans sergiler. Bu makale, m≤k durumunda bile güvenilir kurtarma sağlamak için yarı-tanımlı programlama (SDP), çoğunluk oylaması (MV) ve özyinelemeli ardışık girişim iptali (SIC) tekniklerini birleştiren SDP-MVRSIC adlı yeni bir algoritma sunmaktadır. Yöntem, L≪n SIC katmanına sahip özyinelemeli bir ağaç yapısı kullanır. Her düğüm, rastgele SDP örneklemesiyle aday çözümler üretir, bunları MV ile rafine eder ve sonraki SIC aşamaları için dallar oluşturur. C(x ̂ )=‖y-Hx ̂ ‖_2^2 maliyet fonksiyonu, en uygun adayların seçimine rehberlik eder. SDP-MVRSIC, hesaplama karmaşıklığı ve kurtarma doğruluğu arasında ayarlanabilir bir denge sunar. Örneğin, n=128 için karmaşıklığın O(n^3.83 )'ten O(n^5.86 )'ya çıkarılması, seyreklik oranı s=k/n 0.5'ten 0.125'e düştükçe m/k∈[0.6,1.5] aralığında tam kurtarma sağlar. Bu esneklik, algoritmayı aşırı yüklenmiş MIMO sistemleri veya kaynak kısıtlı sensör ağları gibi zorlayıcı ölçüm kısıtlamaları olan uygulamalar için özellikle uygun hale getirir.

Binary compressive sensing (BCS) addresses the challenge of recovering a k-sparse binary vector of length n from m linear measurements, where m≪n. In the extreme undersampling regime (m<2k), traditional compressive sensing (CS) guarantees breakdown, and existing BCS algorithms with random sensing matrices exhibit suboptimal performance. This paper introduces SDP-MVRSIC, a novel algorithm that integrates semidefinite programming (SDP), majority voting (MV), and recursive successive interference cancellation (SIC) to achieve reliable recovery even when m≤k. The method employs a recursive tree structure with L≪n SIC layers, where each node generates candidate solutions via randomized SDP sampling, refine them using MV, and propagates branches for subsequent SIC stages. The cost function C(x ̂ )=‖y-Hx ̂ ‖_2^2 guides the selection of optimal candidates. SDP-MVRSIC offers a tunable trade-off between computational complexity and recovery accuracy. For instance, when n=128, increasing the complexity from O(n^3.83 ) to O(n^5.86 ) enables exact recovery for m/k∈[0.6,1.5] as the sparsity ratio s=k/n decreases from 0.5 to 0.125. This flexibility makes the algorithm particularly suited for applications with stringent measurement constraints, such as overloaded MIMO systems or resource-limited sensor networks.