CS: The Secrecy of CS Measurements, Counting faces of randomly-projected polytopes, Compressive wireless arrays, Compressive beamforming and Mapping.

Here is a paper by Yaron Rachlin and Dror Baron on The Secrecy of Compressive Sensing Measurements that is evaluating whether it is possible to estimate the measurement matrix when one is given the final CS measurements. Dror and Yaron have also gone through the pain of explaining the paper in a more user-friendly summary than an abstract, I am grateful for that and I am copying verbatim their commentary (Thanks Dror and Yaron!).

Several recent papers mention the possibility that compressed sensing measurements are encrypted. In this paper, we investigate this claim. We consider a scenario where Alice has a secret message (in our model the message is a real, K-sparse signal) that she would like to share with Bob. She encodes this signal using an M by N Gaussian measurement matrix. Bob receives the measurements, and can recover the signal, because he also knows the measurement matrix (in practice, Alice and Bob could share the seed of a random number generator used to produce
the measurement matrix). Can an eavesdropper (Eve), who intercepts the measurements, recover the signal without knowing the measurement matrix? We evaluate this question using two well-established approaches to encryption: information-theoretic and computational.

First, we consider the stronger information-theoretic notion of perfect secrecy. This notion requires the mutual information between signals and measurements to be zero. However, the signals and measurements are statistically dependent, which rules out perfect secrecy. Second, we consider the weaker notion of computational secrecy, which means that Eve can only recover the signal with a prohibitively large computational cost. We prove that compressed sensing achieves a computational notion of secrecy in the face of an adversary attempting to use either ell_0 or ell_1 minimization. Our result hinges on a theorem that shows that with probability one Eve will recover an M-sparse explanation instead of a K-sparse explanation when using the wrong measurement matrix.

The abstract itself reads:

Results in compressed sensing describe the feasibility of reconstructing sparse signals using a small number of linear measurements. In addition to compressing the signal, do these measurements provide secrecy? This paper considers secrecy in the context of an adversary that does not know the measurement matrix used to encrypt the signal. We demonstrate that compressed sensing based encryption does not achieve Shannon’s definition of perfect secrecy, but can provide a computational guarantee of secrecy.

Here is a paper in which some of the findings were presented by Jared Tanner at Texas A&M: David Donoho and Jared Tanner in Counting faces of randomly-projected polytopes when the projection radically lowers dimension. The first part of the introduction reads:

1.1. Three surprises of high dimensions. This paper develops asymptotic methods

to count faces of random high-dimensional polytopes; a seemingly dry and unpromising pursuit. Yet our conclusions have surprising implications - in statistics,

probability, information theory, and signal processing - with potential impacts in

practical subjects like medical imaging and digital communications. Before involving

the reader in our lengthy analysis of high-dimensional face counting, we describe

three implications of our results.

• 1.1.1 Convex Hulls of Gaussian Point Clouds.
  
• 1.1.2. Signal Recovery from Random Projections.
  
• 1.1.3. How many gross errors can we efficiently correct?
  

Also found are three more papers from the Rice Compressed Sensing Resources:

Volkan Cevher, Ali Gurbuz, James McClellan, and Rama Chellappa, Compressive wireless arrays for bearing estimation of sparse sources in angle domain. The abstract reads:

Joint processing of sensor array outputs improves the performance of parameter estimation and hypothesis testing problems beyond the sum of the individual sensor processing results. When the sensors have high data sampling rates, arrays are tethered, creating a disadvantage for their deployment and also limiting their aperture size. In this paper, we develop the signal processing algorithms for randomly deployable wireless sensor arrays that are severely constrained in communication bandwidth. We focus on the acoustic bearing estimation problem and show that when the target bearings are modeled as a sparse vector in the angle space, functions of the low dimensional random projections of the microphone signals can be used to determine multiple source bearings as a solution of an ℓ1-norm minimization problem. Field data results are shown where only 10bits of information is passed from each microphone to estimate multiple target bearings.

Ali Gurbuz, James McClellan, and Volkan Cevher, A compressive beamforming method. The abstract reads:

Compressive Sensing (CS) is an emerging area which uses a relatively small number of non-traditional samples in the form of randomized projections to reconstruct sparse or compressible signals. This paper considers the direction-of-arrival (DOA) estimation problem with an array of sensors using CS. We show that by using random projections of the sensor data, along with a full waveform recording on one reference sensor, a sparse angle space scenario can be reconstructed, giving the number of sources and their DOA’s. The number of projections can be very small, proportional to the number sources. We provide simulations to demonstrate the performance and the advantages of our compressive beamformer algorithm.

Yasamin Mostofi and Pradeep Sen, Compressed mapping of communication signal strength. The abstract reads:

In this paper we consider a mobile cooperative network that is tasked with building a map of the received signal strength to a fixed station. By using the recent results in the area of compressed sensing, we show how the nodes can exploit the sparse representation of the channel’s spatial variations to build a map of the signal strength with minimal sensing. We furthermore propose a successive interference cancellation method for signal reconstruction based on a considerably incomplete set of measurements. The proposed method is an extension of the existing signal reconstruction strategies but with a considerably better performance. Finally, we present simulation results that show the performance of the proposed framework.

Credit: NASA/JPL/University of Arizona, Unconformity in Mars North Polar Layered Deposits (PSP_009390_2595) as taken by the HiRiSE camera