Tuesday, November 10, 2009

CS: Xampling, Compressive Wide-Band Spectrum Sensing, An unconstrained lq minimization, Random matrices are democratic

http://www.technion.ac.il/~elron/
From the folks who brought us the Modulated Wideband Converter hardware, here is the design methodology underneath it called Xampling which in effect deals with Compressive Sensing for Analog signals: Xampling -- Part I: Practice by Moshe Mishali, Yonina Eldar and Asaf Elron . The abstract reads:

We introduce Xampling, a design methodology for sub-Nyquist sampling of continuous-time analog signals. The main principles underlying this framework are the ability to capture a broad signal model, low sampling rate, efficient analog and digital implementation and lowrate baseband processing. The main hypothesis of Xampling is that in order to break through the Nyquist barrier, one has to combine classic methods and results from sampling theory together with recent developments from the literature of compressed sensing. In this paper, we present the Xampling framework and examine several sub-Nyquist approaches in light of the four Xampling principles. It is shown that previous methods suffer from analog implementation issues, large computational loads in the digital domain, and have no baseband processing capabilities. An exception is the recently proposed modulated wideband converter (MWC) which satisfies the model, rate and implementation criteria, though lacking the baseband processing capability. Here, we extend the MWC by proposing a digital algorithm which extracts each band of the signal from the compressed measurements, thus enabling lowrate (baseband) processing. The converter with the proposed algorithm conforms with the Xampling desiderata. In addition, we describe two configurations of the converter for efficient spectrum sensing in wideband cognitive radio receivers. In the second part of this work we study theoretical aspects of rate and stability of sub-Nyquist systems, following the pragmatic theme of the Xampling methodology.

At the end of the paper, the author uses the example of the cognitive Radio which eventually led me to the following two papers and thesis: Distributed Compressive Wide-Band Spectrum Sensing by Ying Wang, Ashish Pandharipande, Yvan Lamelas Polo and Geert Leusy. The abstract reads:

—We consider a compressive wide-band spectrum sensing scheme for cognitive radio networks. Each cognitive radio (CR) sensing receiver transforms the received analog signal from the licensed system in to a digital signal using an analog-to-information converter. The autocorrelation of the compressed signal is then collected from each CR at a fusion center. A compressive sampling recovery algorithm that exploits joint sparsity is then employed to reconstruct an estimate of the signal spectrum and used to make a decision on signal occupancy. We compare the performance of this distributed compressive spectrum sensing scheme with a compressive spectrum sensing scheme at a single CR and show the performance gains obtained from spatial diversity.

and Compressive Wide-Band Spectrum Sensing by Ying Wang, Ashish Pandharipande, Yvan Lamelas Polo and Geert Leusy. The abstract reads:

We present a compressive wide-band spectrum sensing scheme for cognitive radios. The received analog signal at the cognitive radio sensing receiver is transformed in to a digital signal using an analog-to-information converter. The autocorrelation of this compressed signal is then used to reconstruct an estimate of the signal spectrum. We evaluate the performance of this scheme in terms of the mean squared error of the power spectrum density estimate and the probability of detecting signal occupancy.

And finally, to Yvan Lamelas Polo's thesis entitled: Compressive Wideband Spectrum Sensing for Cognitive Radio Applications with the following abstract:

It has been widely recognized that utilization of radio spectrum by licensed wireless systems, e.g., TV broadcasting, aeronautical telemetry, is quite low. In particular, at any given time and spatial region, there are frequency bands where there is no signal occupancy. There has been recent interest in improving spectrum utilization by permitting secondary usage using cognitive radios. Cognitive radios use spectrum sensing to determine frequency bands that are vacant of licensed signal transmissions and transmit on such portions to meet regulatory constraints of avoiding harmful interference to licensed systems. Future cognitive radios will be capable of scanning a wide band of frequencies, in the order of a few GHz, and employ adaptive waveforms for transmission depending on the estimated spectrum of licensed systems. In this thesis, we address the problem of estimating the spectrum of the wide-band signal received at the cognitive radio sensing receiver using compressive sampling coupled with a multiband spectrum detector to determine the spectrum occupancy of the licensed system. Since individual cognitive radios might not be able to reliably detect weak primary signals due to channel fading/shadowing, we also propose a distributed compressive scheme based on joint recovery of the license occupancy for application scenarios involving geographically distributed radios. In such a distributed approach, the spectrum occupancy is determined by the joint work of cognitive radios (exploiting spatial diversity), as opposed to being determined individually by each cognitive radio.


In a different direction, here is another intriguing paper on a reweighted algorithm dealing with l_q problems: An unconstrained lq minimization for sparse solution of under determined linear systems by Ming-Jun Lai and Jingyue Wang. The abstract reads:

We study an unconstrained version of the ℓq minimization for the sparse solution of under-determined linear systems for 0 \lt q \le 1. Although the minimization is nonconvex, we introduce a regularization and develop an iterative algorithm. We show that the iterative solutions converge to the sparse solution. Numerical experiments will be demonstrated to show that our approach works very well.
I note the following from their paper:
According to our theory, we can completely determine a sparse solution without any conditions, e.g., the restricted isometry property (RIP) on matrix A. This is an another advantage of the ℓq minimization for 0 \lt q \lt 1 over the classic ℓ1 minimization approach.



Their algorithm looks like a reweighted scheme and as one can read from the paper, it takes a long time to converge, much like the IRLS scheme. Finally, let us note the success of this algorithm with uniform random matrices.


And finally from the Rice Compressive Sensing Repository we have:

The recently introduced theory of compressive sensing (CS) enables the reconstruction of sparse or compressible signals from a small set of nonadaptive, linear measurements. If properly chosen, the number of measurements can be significantly smaller than the ambient dimension of the signal and yet preserve the significant signal information. Interestingly, it can be shown that random measurement schemes provide a near-optimal encoding in terms of the required number of measurements. In this report, we explore another relatively unexplored, though often alluded to, advantage of using random matrices to acquire CS measurements. Specifically, we show that random matrices are democractic, meaning that each measurement carries roughly the same amount of signal information. We demonstrate that by slightly increasing the number of measurements, the system is robust to the loss of a small number of arbitrary measurements. In addition, we draw connections to oversampling and demonstrate stability from the loss of significantly more measurements.


No comments:

Printfriendly