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

DOI10.1109/TIP.2010.2048969zbMATH Open1371.94020arXiv1001.2952WikidataQ84114377 ScholiaQ84114377MaRDI QIDQ5366556FDOQ5366556

Boris Alexeev, Rachel Ward

Publication date: 9 October 2017

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

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.

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)

Cited In (7)

• An algorithmic framework for Mumford–Shah regularization of inverse problems in imaging
• Sparse Legendre expansions via \(\ell_1\)-minimization
• Non-smooth Variational Regularization for Processing Manifold-Valued Data
• Iterative thresholding meets free-discontinuity problems
• Mumford-Shah and Potts regularization for manifold-valued data
• An Algorithm for Second Order Mumford--Shah Models Based on a Taylor Jet Formulation
• Existence of minimizers of the Mumford-Shah functional with singular operators and unbounded data

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)