We study the problem of estimating the covariance matrix of a
high-dimensional distribution when a small constant fraction of the samples can
be arbitrarily corrupted. Recent work gave the first polynomial time algorithms
for this problem with near-optimal error guarantees for several natural
structured distributions. Our main contribution is to develop faster algorithms
for this problem whose running time nearly matches that of computing the
empirical covariance.
Given $N = \tilde{\Omega}(d^2/\epsilon^2)$ samples from a $d$-dimensional
Gaussian distribution, an $\epsilon$-fraction of which may be arbitrarily
corrupted, our algorithm runs in time
$\tilde{O}(d^{3.26})/\mathrm{poly}(\epsilon)$ and approximates the unknown
covariance matrix to optimal error up to a logarithmic factor. Previous robust
algorithms with comparable error guarantees all have runtimes
$\tilde{\Omega}(d^{2 \omega})$ when $\epsilon = \Omega(1)$, where $\omega$ is
the exponent of matrix multiplication. We also provide evidence that improving
the running time of our algorithm may require new algorithmic techniques.

本文研究了协方差矩阵的估计问题，当仅有小部分样本被恶意更改时，我们提出了一种运行时间接近计算经验协方差且具有最佳误差保证的算法，该算法适用于高维分布，能处理高斯分布等深度分布结构及矩阵乘法指数中的病态情形。

高维稳健协方差估计的快速算法

Faster Algorithms for High-Dimensional Robust Covariance Estimation

Tracking-by-detection methods have demonstrated competitive performance in
recent years. In these approaches, the tracking model heavily relies on the
quality of the training set. Due to the limited amount of labeled training
data, additional samples need to be extracted and labeled by the tracker
itself. This often leads to the inclusion of corrupted training samples, due to
occlusions, misalignments and other perturbations. Existing
tracking-by-detection methods either ignore this problem, or employ a separate
component for managing the training set.
We propose a novel generic approach for alleviating the problem of corrupted
training samples in tracking-by-detection frameworks. Our approach dynamically
manages the training set by estimating the quality of the samples. Contrary to
existing approaches, we propose a unified formulation by minimizing a single
loss over both the target appearance model and the sample quality weights. The
joint formulation enables corrupted samples to be down-weighted while
increasing the impact of correct ones. Experiments are performed on three
benchmarks: OTB-2015 with 100 videos, VOT-2015 with 60 videos, and Temple-Color
with 128 videos. On the OTB-2015, our unified formulation significantly
improves the baseline, with a gain of 3.8% in mean overlap precision. Finally,
our method achieves state-of-the-art results on all three datasets. Code and
supplementary material are available at
this http URL .

提出了一种用于跟踪的检测框架的新方法，该方法通过估计样本质量来动态地管理训练集并降低损坏样本的影响，并通过在目标外观模型和样本质量权重上最小化单个损失的统一公式实现，最终在三个数据集上实现了最新的结果提升。