cvpr cvpr2013 cvpr2013-9 cvpr2013-9-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Peng Wang, Chunhua Shen, Anton van_den_Hengel
Abstract: Many computer vision problems can be formulated as binary quadratic programs (BQPs). Two classic relaxation methods are widely used for solving BQPs, namely, spectral methods and semidefinite programming (SDP), each with their own advantages and disadvantages. Spectral relaxation is simple and easy to implement, but its bound is loose. Semidefinite relaxation has a tighter bound, but its computational complexity is high for large scale problems. We present a new SDP formulation for BQPs, with two desirable properties. First, it has a similar relaxation bound to conventional SDP formulations. Second, compared with conventional SDP methods, the new SDP formulation leads to a significantly more efficient and scalable dual optimization approach, which has the same degree of complexity as spectral methods. Extensive experiments on various applications including clustering, image segmentation, co-segmentation and registration demonstrate the usefulness of our SDP formulation for solving large-scale BQPs.
[1] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[2] T. Cour and J. Bo. Solving markov random fields with spectral relaxation. In Proc. Int. Conf. Artificial Intelligence & Statistics, 2007.
[3] T. Cour, P. Srinivasan, and J. Shi. Balanced graph matching. In Proc. Adv. Neural Info. Process. Systems, pages 3 13–320, 2006.
[4] M. X. Goemans and D. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42:1 115–1 145, 1995.
[5] S. Guattery and G. Miller. On the quality of spectral separators. SIAM J. Matrix Anal. Appl., 19:701–719, 1998.
[6] M. Heiler, J. Keuchel, and C. Schnorr. Semidefinite clustering for image segmentation with a-priori knowledge. In Proc. DAGM Symp. Pattern Recogn., pages 309–317, 2005.
[7] A. Joulin, F. Bach, and J. Ponce. Discriminative clustering for image cosegmentation. In Proc. IEEE Conf. Comput. Vis. & Pattern Recogn., 2010.
[8] M. Journee, F. Bach, P.-A. Absil, and R. Sepulchre. Low-rank optimization on the cone of positive semidefinite matrices. SIAM J. Optimization, 20(5), 1999.
[9] R. Kannan, S. Vempala, and A. Vetta. On clusterings: Good, bad and spectral. J. ACM, 51:497–515, 2004.
[10] J. Keuchel, C. Schnoerr, C. Schellewald, and D. Cremers. Binary partitioning, perceptual grouping and restoration with semidefinite programming. IEEE Trans. Pattern Analysis & Machine Intelligence, 25(1 1): 1364–1379, 2003.
[11] N. Krislock, J. Malick, and F. Roupin. Improved semidefinite bounding procedure for solving max-cut problems to optimality. Math. Program. Ser. A, 2013. Published online 13 Oct. 2012 at http : / /doi . org/ k2 q.
[12] K. J. Lang. Fixing two weaknesses of the spectral method. In Proc. Adv. Neural Info. Process. Systems, pages 715–722, 2005.
[13] F. Lauer and C. Schnorr. Spectral clustering of linear subspaces for motion segmentation. In Proc. Int. Conf. Comput. Vis., 2009.
[14] S. Maji, N. K. Vishnoi, and J. Malik. Biased normalized cuts. In Proc. IEEE
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26] Conf. Comput. Vis. & Pattern Recogn., pages 2057–2064, 2011. J. Malick. The spherical constraint in boolean quadratic programs. J. Glob. Optimization, 39(4):609–622, 2007. D. Martin, C. Fowlkes, D. Tal, and J. Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In Proc. IEEE Conf. Comput. Vis. & Pattern Recogn., volume 2, pages 416–423, 2001. C. Olsson, A. Eriksson, and F. Kahl. Solving large scale binary quadratic problems: Spectral methods vs. semidefinite programming. In Proc. IEEE Conf. Comput. Vis. & Pattern Recogn., pages 1–8, 2007. C. Schellewald and C. Schn o¨rr. Probabilistic subgraph matching based on convex relaxation. In Proc. Int. Conf. Energy Minimization Methods in Comp. Vis. & Pattern Recogn., pages 171–186, 2005. C. Shen, J. Kim, and L. Wang. A scalable dual approach to semidefinite metric learning. In Proc. IEEE Conf. Comput. Vis. & Pattern Recogn., pages 2601 2608, 2011. J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Analysis & Machine Intelligence, 22(8):888–905, 8 2000. J. F. Sturm. Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimizat. Methods & Softw., 11:625–653, 1999. K. C. Toh, M. Todd, and R. H. Ttnc. SDPT3—a MATLAB software package for semidefinite programming. Optimizat. Methods & Softw., 11:545–581, 1999. P. Torr. Solving markov random fields using semi definite programming. In Proc. Int. Conf. Artificial Intelligence & Statistics, 2007. A. Vedaldi and B. Fulkerson. VLFeat: An open and portable library of computer vision algorithms. http : / /www .vlfeat . org/, 2008. S. X. Yu and J. Shi. Segmentation given partial grouping constraints. IEEE Trans. Pattern Analysis & Machine Intelligence, 26(2): 173–183, 2004. C. Zhu, R. H. Byrd, P. Lu, and J. Nocedal. Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization. ACM Trans. Mathematical Software, 23(4):550–560, 1997. 3http . : / / cs ade laide . edu . au / ˜chhshen BQP / 1 1 13 3 3 1 1 179 7 /pro j ect s /