Residual Expansion Algorithm: Fast and Effective Optimization for
Nonconvex Least Squares Problems
Abstract
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 highdimensional optimization. The RE algorithm exhibits excellent empirical performance in terms of k-means clustering,
point-set registration, optimized product quantization, and
blind image deblurring.