The classical iteratively reweighted least-squares (IRLS) algorithm aims to
recover an unknown signal from linear measurements by performing a sequence of
weighted least squares problems, where the weights are recursively updated at
each step. Varieties of this algorithm have been shown to achieve favorable
empirical performance and theoretical guarantees for sparse recovery and
$\ell_p$-norm minimization. Recently, some preliminary connections have also
been made between IRLS and certain types of non-convex linear neural network
architectures that are observed to exploit low-dimensional structure in
high-dimensional linear models. In this work, we provide a unified asymptotic
analysis for a family of algorithms that encompasses IRLS, the recently
proposed lin-RFM algorithm (which was motivated by feature learning in neural
networks), and the alternating minimization algorithm on linear diagonal neural
networks. Our analysis operates in a "batched" setting with i.i.d. Gaussian
covariates and shows that, with appropriately chosen reweighting policy, the
algorithm can achieve favorable performance in only a handful of iterations. We
also extend our results to the case of group-sparse recovery and show that
leveraging this structure in the reweighting scheme provably improves test
error compared to coordinate-wise reweighting.

在这项工作中，我们对一类算法进行了统一的渐近性分析，其中包括了经典的迭代重新加权最小二乘（IRLS）算法、最近提出的用于线性神经网络的 lin-RFM 算法和线性对角神经网络上的交替最小化算法。我们的分析在一个 “批处理” 情境中进行，使用 i.i.d. 高斯协变量，并表明在适当选择重新加权策略的情况下，算法只需少数几次迭代就能取得良好的性能。我们还将我们的结果推广到了群稀疏恢复的情况，并证明利用这种结构在重新加权方案中比坐标加权明显改善了测试误差。