Globally Optimal Least Squares Solutions for Quasiconvex 1D Vision Problems
(2009) 16th Scandinavian Conference on Image Analysis 5575. p.686-695- Abstract
- Solutions to non-linear least squares problems play an essential role in structure and motion problems in computer vision. The predominant approach for solving these problems is a Newton like scheme which uses the: hessian of the function to iteratively find a, local solution. Although fast, this strategy inevitably leeds to issues with poor local minima, and missed global minima. In this paper rather than trying to develop all algorithm that is guaranteed to always work, we show that it is often possible to verify that a local solution is in fact; also global. We present a simple test that verifies optimality of a solution using only a few linear programs. We show oil both synthetic and real data that for the vast majority of cases we are... (More)
- Solutions to non-linear least squares problems play an essential role in structure and motion problems in computer vision. The predominant approach for solving these problems is a Newton like scheme which uses the: hessian of the function to iteratively find a, local solution. Although fast, this strategy inevitably leeds to issues with poor local minima, and missed global minima. In this paper rather than trying to develop all algorithm that is guaranteed to always work, we show that it is often possible to verify that a local solution is in fact; also global. We present a simple test that verifies optimality of a solution using only a few linear programs. We show oil both synthetic and real data that for the vast majority of cases we are able to verify optimality. Further more we show even if the above test fails it is still often possible to verify that the local solution is global with high probability. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1460148
- author
- Olsson, Carl LU ; Byröd, Martin LU and Kahl, Fredrik LU
- organization
- publishing date
- 2009
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Image Analysis, Proceedings
- volume
- 5575
- pages
- 686 - 695
- publisher
- Springer
- conference name
- 16th Scandinavian Conference on Image Analysis
- conference location
- Oslo, Norway
- conference dates
- 2009-06-15 - 2009-06-18
- external identifiers
-
- wos:000268661000070
- scopus:70350626791
- ISSN
- 1611-3349
- 0302-9743
- language
- English
- LU publication?
- yes
- id
- a20253bd-6ed9-4391-a93b-7f7976b594ff (old id 1460148)
- date added to LUP
- 2016-04-01 11:56:27
- date last changed
- 2024-07-30 06:56:22
@inproceedings{a20253bd-6ed9-4391-a93b-7f7976b594ff, abstract = {{Solutions to non-linear least squares problems play an essential role in structure and motion problems in computer vision. The predominant approach for solving these problems is a Newton like scheme which uses the: hessian of the function to iteratively find a, local solution. Although fast, this strategy inevitably leeds to issues with poor local minima, and missed global minima. In this paper rather than trying to develop all algorithm that is guaranteed to always work, we show that it is often possible to verify that a local solution is in fact; also global. We present a simple test that verifies optimality of a solution using only a few linear programs. We show oil both synthetic and real data that for the vast majority of cases we are able to verify optimality. Further more we show even if the above test fails it is still often possible to verify that the local solution is global with high probability.}}, author = {{Olsson, Carl and Byröd, Martin and Kahl, Fredrik}}, booktitle = {{Image Analysis, Proceedings}}, issn = {{1611-3349}}, language = {{eng}}, pages = {{686--695}}, publisher = {{Springer}}, title = {{Globally Optimal Least Squares Solutions for Quasiconvex 1D Vision Problems}}, volume = {{5575}}, year = {{2009}}, }