On the Complexity of Mumford–Shah-Type Regularization, Viewed as a Relaxed Sparsity Constraint

DOI10.1109/TIP.2010.2048969MaRDI QIDQ5366556zbMATH OpenWikidataFDO

Authors Boris Alexeev, Rachel Ward

Publication date 9 October 2017

Published in IEEE Transactions on Image Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1001.2952

Mathematics Subject Classification ID

Quadratic programming (90C20) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Computing methodologies for image processing (68U10)

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.

Cited in

(7)

• Sparse Legendre expansions via _1-minimization
• Iterative thresholding meets free-discontinuity problems
• Mumford-Shah and Potts regularization for manifold-valued data
• Non-smooth variational regularization for processing manifold-valued data
• An algorithmic framework for Mumford-Shah regularization of inverse problems in imaging
• Existence of minimizers of the Mumford-Shah functional with singular operators and unbounded data
• An algorithm for second order Mumford-Shah models based on a Taylor jet formulation

This page was built for publication: On the Complexity of Mumford–Shah-Type Regularization, Viewed as a Relaxed Sparsity Constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366556)