Paper Review: Cost-Aware Compressive Sensing for Networked Sensing Systems

The major issue addressed by this paper is to design algorithms in compressed sensing systems where each samples has a different cost, such algorithmic goal is to minimize the total cost subject to recovery accuracy. Introducing the concept of cost in samples is novel and really filling the gap between theory of compressive sensing and practical systems of crowed sensing, especially systems with limited resources.

The paper is creative while using Regularized Column Sum (RCS) to predict recovery accuracy, which is equivalent to Statistical RIP (Restricted Isometry Property) condition, to formulate the RCS-constrained Optimization (RO) to fund an optimal randomized sampling strategy $\pi$. In order to make RO solvable, the paper uses two relaxation methods:

$$ \sigma (F_\Omega) \leq \alpha \to \mathbb{E}[\sigma (F_\Omega)] \leq \alpha $$

$$ \pi \in \{0,1\}^n \to \pi \in [0,1]^n $$

However, RO is centralized algorithm since it requires global information of the cost map, which makes it impractical. The paper further provides two decentralized algorithm that only uses partial information.

The paper is very well written in structure. It first gives a very intuitive example of how greedy algorithm could failed in real-world applications with spatially correlated cost map, then clearly state all the challenges for solving such problem, including challenge of predicting accuracy, computational complexity, etc. Paper gives solution with proofs as the foundation of proposed algorithms. Finally, the evaluation is comprehensive with two types of application and cost.

Critiques

(1) Both proposed algorithm assumes a fixed sampling size m, then calculate the sample strategy $\pi$, but didn’t discuss how would a crowd sensing application estimate the m value in the first place.

(2) The cost map $c = \{c_1, c_2, …, c_n\}$ in CACS is represented by vector of real numbers where $0 \leq c_i \leq 1$. However, as the paper stated, there exists more complicated scenarios where the cost can exist in many forms. The paper only consider a linear combination of spatial cost maps and the battery penalty as the overall sensing cost.

(3) It seems in evaluation section Figure 7, most of the cost map choices, the proposed distributed algorithms exhibit a similar cost ratio as the base line greedy algorithm, even through the RO algorithm performs much better in all situations. I think this is due to the partial information limitation in PW and DWS leads to a poor estimation for better strategy exists in RO. It also makes one wonder if it is worth to use PW/DWS instead of simple greedy strategy. The distributed algorithm of CACS definitely requires an improvements.