An analysis of convex relaxations for MAP estimation
The problem of obtaining the maximum a posteriori estimate of a general discrete random field (i.e. a random field defined using a finite and discrete set of labels) is known to be NP-hard. However, due to its central importance in many applications, several approximate algorithms have been proposed...
| প্রধান লেখক: | , , |
|---|---|
| বিন্যাস: | Conference item |
| ভাষা: | English |
| প্রকাশিত: |
Curran Associates
2008
|
| _version_ | 1826315002168999936 |
|---|---|
| author | Kumar, MP Kolmogorov, V Torr, PHS |
| author_facet | Kumar, MP Kolmogorov, V Torr, PHS |
| author_sort | Kumar, MP |
| collection | OXFORD |
| description | The problem of obtaining the maximum a posteriori estimate of a general discrete random field (i.e. a random field defined using a finite and discrete set of labels) is known to be NP-hard. However, due to its central importance in many applications, several approximate algorithms have been proposed in the literature. In this paper, we present an analysis of three such algorithms based on convex relaxations: (i) LP-S: the linear programming (LP) relaxation proposed by Schlesinger [20] for a special case and independently in [4, 12, 23] for the general case; (ii) QP-RL: the quadratic programming (QP) relaxation by Ravikumar and Lafferty [18]; and (iii) SOCP-MS: the second order cone programming (SOCP) relaxation first proposed by Muramatsu and Suzuki [16] for two label problems and later extended in [14] for a general label set. We show that the SOCP-MS and the QP-RL relaxations are equivalent. Furthermore, we prove that despite the flexibility in the form of the constraints/objective function offered by QP and SOCP, the LP-S relaxation strictly dominates (i.e. provides a better approximation than) QP-RL and SOCP-MS. We generalize these results by defining a large class of SOCP (and equivalent QP) relaxations which is dominated by the LP-S relaxation. Based on these results we propose some novel SOCP relaxations which strictly dominate the previous approaches. |
| first_indexed | 2024-12-09T03:18:10Z |
| format | Conference item |
| id | oxford-uuid:3a1e21e9-44bb-4c6b-b14f-636e40906fc0 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:18:10Z |
| publishDate | 2008 |
| publisher | Curran Associates |
| record_format | dspace |
| spelling | oxford-uuid:3a1e21e9-44bb-4c6b-b14f-636e40906fc02024-10-31T12:17:50ZAn analysis of convex relaxations for MAP estimationConference itemhttp://purl.org/coar/resource_type/c_5794uuid:3a1e21e9-44bb-4c6b-b14f-636e40906fc0EnglishSymplectic Elements Curran Associates2008Kumar, MPKolmogorov, VTorr, PHSThe problem of obtaining the maximum a posteriori estimate of a general discrete random field (i.e. a random field defined using a finite and discrete set of labels) is known to be NP-hard. However, due to its central importance in many applications, several approximate algorithms have been proposed in the literature. In this paper, we present an analysis of three such algorithms based on convex relaxations: (i) LP-S: the linear programming (LP) relaxation proposed by Schlesinger [20] for a special case and independently in [4, 12, 23] for the general case; (ii) QP-RL: the quadratic programming (QP) relaxation by Ravikumar and Lafferty [18]; and (iii) SOCP-MS: the second order cone programming (SOCP) relaxation first proposed by Muramatsu and Suzuki [16] for two label problems and later extended in [14] for a general label set. We show that the SOCP-MS and the QP-RL relaxations are equivalent. Furthermore, we prove that despite the flexibility in the form of the constraints/objective function offered by QP and SOCP, the LP-S relaxation strictly dominates (i.e. provides a better approximation than) QP-RL and SOCP-MS. We generalize these results by defining a large class of SOCP (and equivalent QP) relaxations which is dominated by the LP-S relaxation. Based on these results we propose some novel SOCP relaxations which strictly dominate the previous approaches. |
| spellingShingle | Kumar, MP Kolmogorov, V Torr, PHS An analysis of convex relaxations for MAP estimation |
| title | An analysis of convex relaxations for MAP estimation |
| title_full | An analysis of convex relaxations for MAP estimation |
| title_fullStr | An analysis of convex relaxations for MAP estimation |
| title_full_unstemmed | An analysis of convex relaxations for MAP estimation |
| title_short | An analysis of convex relaxations for MAP estimation |
| title_sort | analysis of convex relaxations for map estimation |
| work_keys_str_mv | AT kumarmp ananalysisofconvexrelaxationsformapestimation AT kolmogorovv ananalysisofconvexrelaxationsformapestimation AT torrphs ananalysisofconvexrelaxationsformapestimation AT kumarmp analysisofconvexrelaxationsformapestimation AT kolmogorovv analysisofconvexrelaxationsformapestimation AT torrphs analysisofconvexrelaxationsformapestimation |