Efficient Inference of Continuous Markov Random Fields with Polynomial Potentials
In this paper, we prove that every multivariate polynomial with even degree can be decomposed into a sum of convex and concave polynomials. Motivated by this property, we exploit the concave-convex procedure to perform inference on continuous Markov random fields with polynomial potentials. In particular, we show that the concave-convex decomposition of polynomials can be expressed as a sum-of-squares optimization, which can be efficiently solved via semidefinite programing. We demonstrate the effectiveness of our approach in the context of 3D reconstruction, shape from shading and image denoising, and show that our method significantly outperforms existing techniques in terms of efficiency as well as quality of the retrieved solution.
This is a very interesting and substantially novel paper that introduces an approach to solving continuous Markov random field energies with polynomial potentials.  An insightful and well-motivated approach towards this end (ADMM-Poly) was published at CVPR 2013 [20] and is the obvious baseline to compare against.  The present approach is convincingly shown to be preferable, as it is both elegant and computationally efficient.The main idea underlying the approach is to decompose the polynomials into a difference of convex functions.  Towards this end, a constructive approach is introduced for polynomials of even degree, one of the main contributions of the paper. As the authors show, the decomposition problem has a formulation as a semi-definite program and can be solved using standard solvers.  Given that decomposition, the overall inference task reduces to a DC programming problem, which the authors approach using the convex-concave procedure (CCCP).The main weakness of the approach seems to be that the semi-definite program for finding a DC decomposition of the polynomials may not have a solution, as it is only an approximation to the exact but NP-hard problem.  Even though the authors mention that the approach works well for polynomials of low degree in practice (confirmed by experiments), this point is somewhat worrisome. I would encourage the authors to elaborate on this point, as it seems like a potential barrier to adoption of the approach.  How often does this situation occur in practice (if at all)? For which polynomials? Are there any workarounds?  Clearly, an alternative strategy is needed in case this situation occurs.As the authors show, in some cases, for some continuous energies, a DC decomposition is apparent even without having to resort to the above construction algorithm.  The approach then basically becomes an application of CCCP to continuous energies.Quality:The paper is technically sound, though, as mentioned above, a more in-depth discussion of the potential failure to construct the decomposition of the polynomials would be appreciated.  The experiments are impressively diverse and the results are very convincing.  The proposed approach clearly works better than ADMM-Poly, the main baseline to compare against.  It is faster and often obtains solutions of better quality.Clarity:The paper is well-written, though not always easy to read, owing to the technical depth of the material.  One aspect that the authors may wish to clarify is the claimed global convergence of their approach (inherited from CCCP).  I assume that this is meant to be interpreted as "the algorithm converges, for *any* initialization", rather than "the algorithm converges to a global optimum".  As far as I am aware, the convergence properties of CCCP only guarantee convergence to either an optimum or a saddle point.  As it stands, readers might misinterpret the manuscript to assume that the proposed approach always finds a global optimum.Along the same line, the authors claim in lines 039ff that Gaussian belief propagation "retrieves the optimum for arbitrary graphs when the potentials are Gaussian".  This is not true.  There are two known convergence conditions relating to the diagonal dominance, and the spectral radius, of the system matrix, respectively.Originality:The proposed approach is novel to this reviewer, and substantial theory is developed along the way.Significance:The proposed approach has broad and important applications in computer vision and imaging.  The experimental results are impressive, and the approach hence has the potential to significantly benefit many members of these communities.