On the Sample Complexity of Robust PCA
On the Sample Complexity of Robust PCA
复制标题
鲁棒PCA的样本复杂度
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Gilad Lerman
中科院分区：
文献类型：
--
作者：
Matthew Coudron;Gilad Lerman
我们估计的收敛速度和样本的复杂性最近的鲁棒估计的广义版本的逆协方差矩阵。该估计器被用在用于鲁棒子空间恢复的凸算法中（即，鲁棒PCA）。我们的模型假设一个亚高斯的基本分布和一个独立同分布。我们的主要结果表明，与高概率的广义逆协方差的基础分布和它的估计从独立同分布之间的差异的范数。对于任意小的e > 0（影响概率估计），大小为N的样本的数量级为O（N-0.5+e）;这种收敛速度接近直接协方差估计的收敛速度，即，O（N-0.5）。我们的精确概率估计意味着对于某些自然设置，当使用Frobenius范数时，广义逆协方差估计的样本复杂度为O（D2+δ），对于任意小的δ > 0（而使用Frobenius范数的直接协方差估计的样本复杂度为O（D2））。这些结果为相应的鲁棒子空间恢复算法提供了相似的收敛速度和样本复杂度。据我们所知，这是分析任何鲁棒PCA算法的样本复杂度的唯一工作。
We estimate the rate of convergence and sample complexity of a recent robust estimator for a generalized version of the inverse covariance matrix. This estimator is used in a convex algorithm for robust subspace recovery (i.e., robust PCA). Our model assumes a sub-Gaussian underlying distribution and an i.i.d. sample from it. Our main result shows with high probability that the norm of the difference between the generalized inverse covariance of the underlying distribution and its estimator from an i.i.d. sample of size N is of order O(N-0.5+e) for arbitrarily small e > 0 (affecting the probabilistic estimate); this rate of convergence is close to the one of direct covariance estimation, i.e., O(N-0.5). Our precise probabilistic estimate implies for some natural settings that the sample complexity of the generalized inverse covariance estimation when using the Frobenius norm is O(D2+δ) for arbitrarily small δ > 0 (whereas the sample complexity of direct covariance estimation with Frobenius norm is O(D2)). These results provide similar rates of convergence and sample complexity for the corresponding robust subspace recovery algorithm. To the best of our knowledge, this is the only work analyzing the sample complexity of any robust PCA algorithm.