Iterative hard thresholding (IHT) has gained in popularity over the past decades in large-scale optimization. However, convergence properties of this method have only been explored recently in non-convex settings. In matrix completion, existing works often focus on the guarantee of global convergence of IHT via standard assumptions such as incoherence property and uniform sampling. While such analysis provides a global upper bound on the linear convergence rate, it does not describe the actual performance of IHT in practice. In this paper, we provide a novel insight into the local convergence of a specific variant of IHT for matrix completion. We uncover the exact linear rate of IHT in a closed-form expression and identify the region of convergence in which the algorithm is guaranteed to converge. Furthermore, we utilize random matrix theory to study the linear rate of convergence of IHTSVD for large-scale matrix completion. We find that asymptotically, the rate can be expressed in closed form in terms of the relative rank and the sampling rate. Finally, we present various numerical results to verify the aforementioned theoretical analysis.
翻译:过去几十年来,在大规模优化中,迭代硬阈值(IHT)越来越受欢迎,然而,这种方法的趋同特性只是在最近才在非混凝土环境中得到探讨,在完成矩阵时,现有工作往往侧重于通过标准假设,如不一致属性和统一抽样等标准假设,保证IHT的全球趋同。虽然这种分析提供了线性趋同率的全球上限,但并未描述IHT实际的实际表现。在本文件中,我们提供了一种新颖的洞察力,了解了IHT具体变异物在当地的趋同率,以便完成矩阵。我们以封闭式表达方式发现了IHT的确切线性比率,并确定了保证算法汇合的区域。此外,我们利用随机矩阵理论研究IHTSVD大规模完成矩阵的线性趋同率。我们发现,从理论上看,该比率可以以封闭式形式以相对等级和抽样率表示。最后,我们提出了各种数字结果,以核实上述理论分析。