Ullrich, Torsten ; Fellner, Dieter W. (2011)
Linear Algorithms in Sublinear Time - a Tutorial on Statistical Estimation.
In: IEEE Computer Graphics and Applications, 31 (2)
doi: 10.1109/MCG.2010.21
Artikel, Bibliographie
Kurzbeschreibung (Abstract)
This tutorial presents probability theory techniques for boosting linear algorithms. The approach is based on statistics and uses educated guesses instead of comprehensive calculations. Because estimates can be calculated in sublinear time, many algorithms can benefit from statistical estimation. Several examples show how to significantly boost linear algorithms without negative effects on their results. These examples involve a Ransac algorithm, an image-processing algorithm, and a geometrical reconstruction. The approach exploits that, in many cases, the amount of information in a dataset increases asymptotically sublinearly if its size or sampling density increases. Conversely, an algorithm with expected sublinear running time can extract the most information.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2011 |
| Autor(en): | Ullrich, Torsten ; Fellner, Dieter W. |
| Art des Eintrags: | Bibliographie |
| Titel: | Linear Algorithms in Sublinear Time - a Tutorial on Statistical Estimation |
| Sprache: | Englisch |
| Publikationsjahr: | 2011 |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | IEEE Computer Graphics and Applications |
| Jahrgang/Volume einer Zeitschrift: | 31 |
| (Heft-)Nummer: | 2 |
| DOI: | 10.1109/MCG.2010.21 |
| Kurzbeschreibung (Abstract): | This tutorial presents probability theory techniques for boosting linear algorithms. The approach is based on statistics and uses educated guesses instead of comprehensive calculations. Because estimates can be calculated in sublinear time, many algorithms can benefit from statistical estimation. Several examples show how to significantly boost linear algorithms without negative effects on their results. These examples involve a Ransac algorithm, an image-processing algorithm, and a geometrical reconstruction. The approach exploits that, in many cases, the amount of information in a dataset increases asymptotically sublinearly if its size or sampling density increases. Conversely, an algorithm with expected sublinear running time can extract the most information. |
| Freie Schlagworte: | Forschungsgruppe Semantic Models, Immersive Systems (SMIS), Business Field: Virtual engineering, Research Area: Confluence of graphics and vision, Research Area: Semantics in the modeling process, Computer graphics, Algorithms, Statistics, Optimization, Statistical computing, Algorithm boosting |
| Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik 20 Fachbereich Informatik > Graphisch-Interaktive Systeme |
| Hinterlegungsdatum: | 12 Nov 2018 11:16 |
| Letzte Änderung: | 04 Feb 2022 12:40 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum