Title: Compressed sensing and optimal denoising of monotone signals,
Abstract: We consider the problems of compressed sensing and optimal denoising for
signals $\mathbf{x_0}\in\mathbb{R}^N$ that are monotone, i.e.,
$\mathbf{x_0}(i+1) \geq \mathbf{x_0}(i)$, and sparsely varying, i.e.,
$\mathbf{x_0}(i+1) > \mathbf{x_0}(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 $A\mathbf{x_0}$. For random
Gaussian sensing matrices $A\in\mathbb{R}^{m\times 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 $\mathbf{x_0}$. We obtain our results using the statistical dimension
tool.