Compressed sensing and optimal denoising of monotone signals

We consider the problems of compressed sensing and optimal denoising for signals x<inf>0</inf> ∈ ℝ^N that are monotone, i.e., x<inf>0</inf>(i + 1) ≥ x<inf>0</inf>(i), and sparsely varying, i.e., x<inf>0</inf>(i + 1) > x<inf>0</inf>(i) only for a small number k of indices i. We approach the compressed sensing problem by minimizing the total variation norm restricted to the class of monotone signals subject to equality constraints obtained from a number of measurements Ax<inf>0</inf>. For random Gaussian sensing matrices A ∈ ℝ^m×N we derive a closed form expression for the number of measurements m required for successful reconstruction with high probability. We show that the probability undergoes a phase transition as m varies, and depends not only on the number of change points, but also on their location. For denoising we regularize with the same norm and derive a formula for the optimal regularizer weight that depends only mildly on x<inf>0</inf>. We obtain our results using the statistical dimension tool.