Editing Potts model (section)

=== Signal and image processing ===
The Potts model has applications in signal reconstruction. Assume that we are given noisy observation of a piecewise constant signal ''g'' in '''R'''<sup>''n''</sup>. To recover ''g'' from the noisy observation vector ''f'' in '''R'''<sup>''n''</sup>, one seeks a minimizer of  the corresponding inverse problem, the ''L<sup>p</sup>''-Potts functional ''P''<sub>γ</sub>(''u''), which is defined by
: <math> P_\gamma(u) = \gamma \| \nabla u \|_0 + \| u-f\|_p^p = \gamma \# \{ i : u_i \neq u_{i+1} \} + \sum_{i=1}^n  |u_i - f_i|^p</math>

The jump penalty <math>\| \nabla u \|_0</math> forces piecewise constant solutions and the data term <math>\| u-f\|_p^p</math> couples the minimizing candidate ''u'' to the data ''f''. The parameter γ > 0 controls the tradeoff between regularity and [[data fidelity]]. There are fast algorithms for the exact minimization of the ''L''<sup>1</sup> and the ''L''<sup>2</sup>-Potts functional.<ref>{{Cite journal |last1=Friedrich |first1=F. |last2=Kempe |first2=A. |last3=Liebscher |first3=V. |last4=Winkler |first4=G. |date=2008 |title=Complexity Penalized M-Estimation: Fast Computation |jstor=27594299 |journal=Journal of Computational and Graphical Statistics |volume=17 |issue=1 |pages=201–224 |doi=10.1198/106186008X285591 |s2cid=117951377 |issn=1061-8600}}</ref>

In image processing, the Potts functional is related to the segmentation problem.<ref>{{Cite journal |last1=Krähenbühl |first1=Philipp |last2=Koltun |first2=Vladlen |date=2011 |title=Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials |url=https://proceedings.neurips.cc/paper/2011/hash/beda24c1e1b46055dff2c39c98fd6fc1-Abstract.html |journal=Advances in Neural Information Processing Systems |publisher=Curran Associates, Inc. |volume=24|arxiv=1210.5644 }}</ref> However, in two dimensions the problem is NP-hard.<ref>{{Cite journal |last1=Boykov |first1=Y. |last2=Veksler |first2=O. |last3=Zabih |first3=R. |date=November 2001 |title=Fast approximate energy minimization via graph cuts |url=https://ieeexplore.ieee.org/document/969114 |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=23 |issue=11 |pages=1222–1239 |doi=10.1109/34.969114 |issn=1939-3539}}</ref>