  We show that inverse problems with a truncated quadratic regularization are
NP-hard in general to solve, or even approximate up to an additive error. This
stands in contrast to the case corresponding to a finite-dimensional
approximation to the Mumford-Shah functional, where the operator involved is
the identity and for which polynomial-time solutions are known. Consequently,
we confirm the infeasibility of any natural extension of the Mumford-Shah
functional to general inverse problems. A connection between truncated
quadratic minimization and sparsity-constrained minimization is also discussed.
