Nonlinear residual minimization by iteratively reweighted least squares
Nonlinear residual minimization by iteratively reweighted least squares
复制标题
DOI：
10.1007/s10589-016-9829-x
复制
发表时间：
2015-04
影响因子：
2.2
通讯作者：
Juliane Sigl
中科院分区：
文献类型：
--
作者：
Juliane Sigl
本文研究有限维非线性方程最小范数残差的数值解。我们从使用基于范数中迭代残差最小化的贪婪算法寻找相位检索问题的稀疏向量解的问题中获得了特别的灵感，为。由于该问题的温和平滑性，特别是对于非线性问题，我们开发并分析了迭代加权最小二乘（IRLS）的广义版本。该算法简单有效地解决了涉及非二次可能非凸和非光滑代价函数的优化问题，这些优化问题可以转化为一系列常见的最小二乘问题。后者最终可以通过更有效的数值优化方法来解决。当模型方程为线性时，它的分析已经发展到许多不同的情况下（例如，稀疏向量，低秩矩阵优化，以及涉及p-拉普拉斯算子的PDE的解），但到目前为止还没有提供非线性情况下的结果。我们在这里精确地讨论了IRLS的收敛性和误差衰减率。该算法的收敛性分析是基于将其重新表述为能量泛函的交替最小化。实际上，它的主要变量是中间再加权最小二乘问题的解及其权值的竞争者。在实践中经常验证的矫顽力的特定条件和局部凸性假设下，我们能够证明IRLS对非线性残差问题的极小值的收敛性。对于缺乏局部凸性的情况，我们提出了一个适当的二次扰动凸性。最终，我们能够证明这个改进的过程收敛，至少可以很好地逼近原问题的平稳点。为了说明本文的理论结果，我们用几个数值实验对本文进行了总结。我们首先将IRLS与标准Matlab优化函数进行比较，以获得一个简单且易于呈现的示例。此外，我们在更复杂的相位恢复问题框架中对我们的理论结果进行了数值验证，这是我们的主要动机。最后，我们检验了该算法在被脉冲噪声破坏的情况下的恢复能力，在这种情况下，残差需要稀疏化。
In this paper we address the numerical solution of minimal norm residuals ofnonlinearequations in finite dimensions. We take particularly inspiration from the problem of finding a sparse vector solution of phase retrieval problems by using greedy algorithms based on iterative residual minimizations in the-norm, for. Due to the mild smoothness of the problem, especially for, we develop and analyze a generalized version of iteratively reweighted least squares (IRLS). This simple and efficient algorithm performs the solution of optimization problems involving non-quadratic possibly non-convex and non-smooth cost functions, which can be transformed into a sequence of common least squares problems. The latter can be tackled eventually by more efficient numerical optimization methods. While its analysis has been by now developed in many different contexts (e.g., for sparse vector, low-rank matrix optimization, and for the solution of PDE involvingp-Laplacians) when the model equation islinear, no results are up to now provided in case ofnonlinearones. We address here precisely the convergence and the rate of error decay of IRLS for such nonlinear problems. The analysis of the convergence of the algorithm is based on its reformulation as an alternating minimization of an energy functional. In fact its main variables are the competitors to solutions of the intermediate reweighted least squares problems and their weights. Under a specific condition of coercivity often verified in practice and assumptions of local convexity, we are able to show convergence of IRLS to minimizers of the nonlinear residual problem. For the case where we are lacking the local convexity, we propose an appropriate convexification by quadratic perturbations. Eventually we are able to show convergence of this modified procedure to at least a very good approximation of stationary points of the original problem. In order to illustrate the theoretical results we conclude the paper with several numerical experiments. We first compare IRLS with standard Matlab optimization functions for a simple and easily presentable example. Furthermore we numerically validate our theoretical results in the more complicated framework of phase retrieval problems, which are our main motivation. Finally we examine the recovery capability of the algorithm in the context of data corrupted by impulsive noise where the sparsification of the residual is desired.