  This work is about the total variation (TV) minimization which is used for
recovering gradient-sparse signals from compressed measurements. Recent studies
indicate that TV minimization exhibits a phase transition behavior from failure
to success as the number of measurements increases. In fact, in large
dimensions, TV minimization succeeds in recovering the gradient-sparse signal
with high probability when the number of measurements exceeds a certain
threshold; otherwise, it fails almost certainly. Obtaining a closed-form
expression that approximates this threshold is a major challenge in this field
and has not been appropriately addressed yet. In this work, we derive a tight
lower-bound on this threshold in case of any random measurement matrix whose
null space is distributed uniformly with respect to the Haar measure. In
contrast to the conventional TV phase transition results that depend on the
simple gradient-sparsity level, our bound is highly affected by generalized
notions of gradient-sparsity. Our proposed bound is very close to the true
phase transition of TV minimization confirmed by simulation results.
