A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
复制标题
DOI：
--
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
Tyler Maunu;Teng Zhang;Gilad Lerman
中科院分区：
文献类型：
--
作者：
Tyler Maunu;Teng Zhang;Gilad Lerman
我们提出了一个用于鲁棒子空间恢复的非凸能量景观的数学分析。证明了在数据集的确定性条件下，底层子空间是给定邻域内唯一的驻点和局部最小值。在确定性条件满足的情况下，我们进一步证明了在格拉斯曼流形上的测地梯度下降法在初始化适当的情况下可以准确地恢复底层子空间。在一个简单的确定性条件下，保证了主成分分析的正确初始化。在稍强的假设条件下，采用分段常步长格式的梯度下降法实现了线性收敛。在一些数据统计模型上证明了确定性条件的实用性，对于不同的样本量和环境维数，该方法在干草堆模型上几乎达到了最先进的恢复保证。特别是，当环境维度是固定的并且样本量足够大时，我们表明我们的梯度方法可以精确地恢复任何固定分数的异常值（小于1）的底层子空间。
We present a mathematical analysis of a non-convex energy landscape for robust subspace recovery. We prove that an underlying subspace is the only stationary point and local minimizer in a specified neighborhood under a deterministic condition on a dataset. If the deterministic condition is satisfied, we further show that a geodesic gradient descent method over the Grassmannian manifold can exactly recover the underlying subspace when the method is properly initialized. Proper initialization by principal component analysis is guaranteed with a simple deterministic condition. Under slightly stronger assumptions, the gradient descent method with a piecewise constant step-size scheme achieves linear convergence. The practicality of the deterministic condition is demonstrated on some statistical models of data, and the method achieves almost state-of-the-art recovery guarantees on the Haystack Model for different regimes of sample size and ambient dimension. In particular, when the ambient dimension is fixed and the sample size is large enough, we show that our gradient method can exactly recover the underlying subspace for any fixed fraction of outliers (less than 1).