On the Complexity of Mumford–Shah-Type Regularization, Viewed as a Relaxed Sparsity Constraint
Authors:
- 22 April 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Image Processing
- Vol. 19 (10) , 2787-2789
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.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Iterative Thresholding Meets Free-Discontinuity ProblemsFoundations of Computational Mathematics, 2010
- Reconstruction in the inverse crack problem by variational methodsEuropean Journal of Applied Mathematics, 2008
- An Introduction To Compressive SamplingIEEE Signal Processing Magazine, 2008
- A variational approach to the reconstruction of cracks by boundary measurementsJournal de Mathématiques Pures et Appliquées, 2007
- Thresholding implied by truncated quadratic regularizationIEEE Transactions on Signal Processing, 2000
- Image Segmentation by Variational Methods: Mumford and Shah Functional and the Discrete ApproximationsSIAM Journal on Applied Mathematics, 1995
- Simulated annealing in compound Gaussian random fields (image processing)IEEE Transactions on Information Theory, 1990
- Digital Image ProcessingJournal of Applied Statistics, 1989
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of ImagesIEEE Transactions on Pattern Analysis and Machine Intelligence, 1984