用于P范数线性回归的快速，可证明收敛的IRLS算法

作者：Deeksha Adil,Richard Peng,Sushant Sachdeva

摘要：ℓp-norm中的线性回归是在若干应用中出现的规范优化问题，包括稀疏恢复，半监督学习和信号处理。用于求解ℓp-回归的通用凸优化算法在实践中是缓慢的。迭代重加权最小二乘法（IRLS）是一种易于实现的算法系列，用于解决已经研究了50多年的这些问题。然而，这些算法经常在p> 3时发生偏差，自从Osborne（1985）的工作以来，一直存在的问题是，是否有一个IRLS算法可以保证在p> 3时快速收敛。我们提出了p-IRLS，第一个IRLS算法，可以证明几何收敛于任何p∈[2，∞）。我们的算法易于实现，并且保证在O（p3.5mp-22（p-1）logmε）≤Op（m-√logmε）迭代中找到（1 +ε） - 近似解。我们的实验证明它的性能甚至优于我们的理论界限，超过标准的Matlab / CVX实现，以解决这些问题10-50倍，并且是高精度制度中可用实现中最快的。

原文标题：Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression

原文摘要：

地址：https://arxiv.org/abs/1907.07167