Exact optimization conditions for discrete linear inverse problems

Recently, graph cut methods have been used with great success on discrete-label problems occurring in computer vision. Unfortunately, the presence of linear image mappings prevents the use of these techniques in image deconvolution. This work aims to expand the application of the successful graph-cut framework to linear inverse problems and deconvolution. We analyze the structure of linear inverse problems, showing the relationship of the sensing structure to graph non-representability of the problem and use insights from our analysis to present a class of linear operators that is graph representable. We propose a new method of variable relabeling that can transform a class of non-representable problems of this type to corresponding ones which are graph representable, thus allowing the use of graph-cut techniques for these problems.