Power Allocation in Compressed Sensing of Non-uniformly Sparse Signals

Xiaochen Zhao, Wei Dai

Abstract: This paper studies the problem of power allocation in compressed sensing when different components in the unknown sparse signal have different probability to be non-zero. Given the prior information of the non-uniform sparsity and the total power budget, we are interested in how to optimally allocate the power across the columns of a Gaussian random measurement matrix so that the mean squared reconstruction error is minimized. Based on the state evolution technique originated from the work by Donoho, Maleki, and Montanari, we revise the so called approximate message passing (AMP) algorithm for the reconstruction and quantify the MSE performance in the asymptotic regime. Then the closed form of the optimal power allocation is obtained. The results show that in the presence of measurement noise, uniform power allocation, which results in the commonly used Gaussian random matrix with i.i.d. entries, is not optimal for non-uniformly sparse signals. Empirical results are presented to demonstrate the performance gain.

Introduction

In standard Compressed Sensing (CS), we typically assume a signal is uniformly sparse—meaning any given entry is just as likely to be non-zero as any other. Consequently, standard practice involves using measurement matrices, such as i.i.d. Gaussian matrices, that allocate sensing power uniformly across all signal components.

However, real-world signals—from natural images to sensor network data—are rarely uniformly sparse. If we know a priori that certain parts of a signal are more likely to be non-zero (less sparse) than others, using a "one-size-fits-all" measurement matrix is inefficient. This research addresses how to optimally distribute a fixed power budget across the columns of a measurement matrix to minimize the Mean Squared Error (MSE) of the reconstructed signal.

Methodology

The authors build upon the Approximate Message Passing (AMP) algorithm, an iterative method for signal recovery. The study introduces several key methodological steps:

  1. Revised AMP (AMP.P): The standard AMP algorithm is modified to accommodate measurement matrices where columns have different variances, representing varying power levels.
  2. State Evolution Analysis: The researchers utilize state evolution to track the MSE behavior over iterations in the asymptotic regime (where signal size $n$ and measurement count $m$ approach infinity).
  3. Optimization Framework: A constrained optimization problem is formulated to minimize the total reconstruction MSE subject to a total power constraint ($\sum \sigma_i^2 = n$).
  4. Closed-Form Derivation: Using the Cauchy-Schwarz inequality, the authors derive an explicit formula for the optimal power $\sigma_i^2$ for each column.

Key Insights

  • Power Follows Density: The most critical insight is that more sensing power should be allocated to signal components that are less sparse. If a component is highly likely to be non-zero, the measurement matrix requires a "stronger" column to capture it accurately.
  • The Square Root Rule: The optimal power for a column is proportional to the square root of the minimax MSE associated with that component's specific sparsity level.
  • The Role of Noise: Interestingly, the benefits of non-uniform power allocation only manifest when measurement noise is present. In noiseless settings, power allocation does not alter the "phase transition" point where perfect recovery becomes possible.

Empirical Validation and Results

The theory was validated using synthetic datasets, including block-sparse signals where one block is significantly denser than another.

Reconstruction MSE as a function of the sparsity ratio between signal blocks. The red curves (optimized) show a clear advantage over the blue curves (uniform), with empirical results (solid) matching theoretical predictions (dashed).

As shown in the figure above, optimized power allocation consistently outperforms uniform allocation. This performance gain becomes more pronounced as the "sparsity ratio" between signal blocks increases. Furthermore, the empirical results from simulations (solid lines) match the theoretical state evolution predictions (dashed lines) almost perfectly.

Reconstruction MSE vs. noise variance. The linear relationship and the consistent gap between optimized (red) and uniform (blue) strategies demonstrate the robustness of the power allocation framework.

Additional results confirm a linear relationship between reconstruction MSE and noise variance. This proves that the optimized sensing strategy scales predictably and maintains its advantage across various noise levels.

Conclusion and Future Work

This work provides a rigorous mathematical framework for optimizing sensing power in non-uniform environments. While the results are promising, the current framework assumes that non-uniform sparsity statistics are known a priori. Future research may explore adaptive sensing methods where these statistics are estimated dynamically. Additionally, while the asymptotic assumptions hold well for large signals ($n=4000$), further study is needed to determine the effectiveness of this approach for small-scale signal processing.

Summary updated

Abstract

This paper studies the problem of power allocation in compressed sensing when different components in the unknown sparse signal have different probability to be non-zero. Given the prior information of the non-uniform sparsity and the total power budget, we are interested in how to optimally allocate the power across the columns of a Gaussian random measurement matrix so that the mean squared reconstruction error is minimized. Based on the state evolution technique originated from the work by Donoho, Maleki, and Montanari, we revise the so called approximate message passing (AMP) algorithm for the reconstruction and quantify the MSE performance in the asymptotic regime. Then the closed form of the optimal power allocation is obtained. The results show that in the presence of measurement noise, uniform power allocation, which results in the commonly used Gaussian random matrix with i.i.d. entries, is not optimal for non-uniformly sparse signals. Empirical results are presented to demonstrate the performance gain.
BibTeX
@misc{zhao2014power,
  author = {Xiaochen Zhao and Wei Dai},
  title = {{Power Allocation in Compressed Sensing of Non-uniformly Sparse Signals}},
  year = {2014},
  eprint = {1402.4612},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1402.4612},
}
Figure