PDF logo On the complexity of Mumford-Shah type regularization, viewed as a relaxed sparsity constraint

by Boris Alexeev and Rachel Ward

Abstract

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.

Approximate citation

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.

Useful links

PDF logoDirect PDF link
Journal icon Published journal version
DOI icon Persistent document object identifier (DOI)
arXiv icon arXiv online preprint server version
MathSciNet icon Math Reviews (MathSciNet) review
Google Scholar icon Google Scholar entry
BiBTeX icon Individual BiBTex entry