On the complexity of Mumford-Shah type regularization, viewed as a relaxed sparsity constraint
On the complexity of Mumford-Shah type regularization, viewed as a relaxed sparsity constraintWe 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.
Boris Alexeev and Rachel Ward
On the complexity of Mumford-Shah type regularization, viewed as a relaxed sparsity constraint
IEEE Transactions on Image Processing 19 (2010), no. 10, 2787–2789.
| | Direct PDF link |
 | Published journal version |
 | Persistent document object identifier (DOI) |
 | arXiv online preprint server version |