Residual Expansion Algorithm: Fast and Effective Optimization for Nonconvex Least Squares Problems
This addresses optimization challenges in nonconvex settings for researchers and practitioners in machine learning and computer vision, though it appears incremental as it builds on existing nonconvex optimization methods.
The paper tackles nonconvex least squares problems by proposing the residual expansion (RE) algorithm, which achieves fast global optimization without stochastic or multi-point searches and demonstrates excellent empirical performance in applications like k-means clustering and blind image deblurring.
We propose the residual expansion (RE) algorithm: a global (or near-global) optimization method for nonconvex least squares problems. Unlike most existing nonconvex optimization techniques, the RE algorithm is not based on either stochastic or multi-point searches; therefore, it can achieve fast global optimization. Moreover, the RE algorithm is easy to implement and successful in high-dimensional optimization. The RE algorithm exhibits excellent empirical performance in terms of k-means clustering, point-set registration, optimized product quantization, and blind image deblurring.