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.
Seznam odborné literatury
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.
Předběžná náplň práce
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.
Předběžná náplň práce v anglickém jazyce
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.
- zadáno a potvrzeno stud. odd.