hidden - assigned and confirmed by the Study Dept.
Date of registration:
12.12.2016
Date of assignment:
20.12.2016
Confirmed by Study dept. on:
21.06.2018
Date and time of defence:
10.09.2018 09:00
Date of electronic submission:
19.07.2018
Date of submission of printed version:
19.07.2018
Date of proceeded defence:
10.09.2018
Opponents:
doc. RNDr. Iveta Hnětynková, Ph.D.
Guidelines
MCD odhad představuje populární nástroj k nalezení robustního odhadu vektoru středních hodnot a kovarianční matice v přítomnosti odlehlých hodnot. Je však výpočetně neproveditelný a je obvykle aproximován výstupem algoritmu FastMCD. Výpočetní náklady tohoto algoritmu mohou být popsány jako lineární v počtu vzorků a kvadratické v počtu proměnných, avšak s velmi velkým konstantním faktorem (alespoň ve stovkách). Cílem této práce je pokusit se snížit počet aritmetických operací potřebných k nalezení dobré aproximace odhadu MCD použitím především technik z lineární algebry. Důraz bude kladen na tzv. C-krok, který je základním kamenem algoritmu FastMCD a vyžaduje rychlé násobení s inverzí kovarianční matice.
References
P.J. Rousseeuw, K. van Driessen. A fast algorithm for the minimum covariance determinant estimator. Technometrics, 34:212–223, 1999.
L. Elden. Matrix methods in data mining and pattern recognition. SIAM, Philadelphia, 2007.
M.J. Todd, Minimum-Volume Ellipsoids, MOS/SIAM Series on Optimization, Vol. 23, SIAM, Philadelphia, 2016.
J. Duintjer Tebbens, J. Kalina. A computationally inexpensive modification of the C-step for the minimum covariance determinant estimator, submitted.
Preliminary scope of work
MCD odhad představuje populární nástroj k nalezení robustního odhadu vektoru středních hodnot a kovarianční matice v přítomnosti odlehlých hodnot. Je však výpočetně neproveditelné a je obvykle aproximována výstupem algoritmu FastMCD. Výpočetní náklady tohoto algoritmu mohou být popsány jako lineární v počtu vzorků a kvadratické v počtu proměnných, avšak s velmi velkým konstantním faktorem (alespoň ve stovkách). Cílem této práce je pokusit se snížit počet aritmetických operací potřebných k nalezení dobré aproximace odhadu MCD použitím především technik z lineární algebry. Důraz bude kladen na tzv. C-kroku, který je základním kamenem algoritmu FastMCD a vyžaduje rychlé násobení s inverzí kovarianční matice.
Preliminary scope of work in English
The MCD estimator is a popular tool to find robust estimates of the mean vector and the covariance matrix in the presence of outliers. It is, however, computationally infeasible and is usually approximated by the output of the FastMCD algorithm. The computational costs of this algorithm can be described as linear in the number of samples and quadratic in the number of variables, but with a very large constant factor (at least in the hundreds). The goal of this thesis is to attempt to reduce the number of arithmetic operations needed to find a good approximation of the MCD estimator using in particular techniques from linear algebra. The focus will be on the C-step, the cornerstone of the FastMCD algorithm, which requires fast multiplication with inverses of covariance matrices.
- assigned and confirmed by the Study Dept.